A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.
|Place of Publication||Enschede|
|Publisher||University of Twente|
|Number of pages||40|
|Publication status||Published - 2005|
|Name||Memorandum Afdeling TW|
|Publisher||Department of Applied Mathematics, University of Twente|