第322回研究講演会開催案内
情報処理学会東北支部 第322回研究講演会開催案内
日時： 2005年12月2日（金）１６：００−１７：００
会場： 東北大学工学部 電気情報系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)