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.

Keywords

• matching-cut
• matching immune
• extremal graphs
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]