322񌤋uJÈē


񏈗wkx 322񌤋uJÈē
F 2005N122ijPUFOO|PVFOO
F kwHw@dCn1ف@614
utF Professor Andrzej Proskurowski, University of Oregon, USA
F Extremal graphs with no disconnecting matching
TvF
@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)