第322回研究講演会開催報告
- 情報処理学会東北支部第322回研究講演会開催報告
- 日時: 2005年12月2日(金)16:00〜17:00
- 会場: 東北大学工学部 電気情報系1号館 614号室
- 講師: Professor Andrzej Proskurowski, University of Oregon, USA
- 演題: Extremal graphs with no disconnecting matching
- 概要:
We discuss a class of "disconnecting matching immune" graphs, those that
can lose connectivity by removing a matching (an independent set of edges,
no two of which are sharing end-vertices). For the given number of
vertices, n, the tight lower bound on the number of edges in an immune
graph is [3(n-1)/2]. An old conjecture (Farley and Proskurowski, 1984)
states that these extremal immune graphs are exactly the graphs obtained
from the single vertex by a finite number of three simple augmentation
operations. We prove the conjecture with the help of some novel techniques
of Bonsma (2003).
(Joint work with Art Farley, Oregon, and Paul Bonsma, Twente)
- 講演報告:
講演後は多数の質問が寄せられ,活発な質疑応答が行われた.講師Proskurowski教
授からの回答に加えて参加者の方からも貴重なコメントを頂くなど,大変充実した内
容であった.
-
- 参加者:50名
- 報告者:西関隆夫 (東北大学)