Skip to Main content Skip to Navigation
Conference papers

A characterization of extremal graphs with no matching-cut

Abstract : 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|≥\lceil 3(|V|-1)/2\rceil$ , and constructed a large class of immune graphs that attain this lower bound for every value of $|V(G)|$, called $ABC$ graphs. They conjectured that every immune graph that attains this lower bound is an $ABC$ graph. We present a proof of this conjecture.
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184354
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:37:02 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:45 AM

File

dmAE0127.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184354, version 1

Collections

Citation

Paul Bonsma. A characterization of extremal graphs with no matching-cut. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.135-138. ⟨hal-01184354⟩

Share

Metrics

Record views

118

Files downloads

646