A characterization of extremal graphs without matching-cuts

P.S. Bonsma

Research output: Book/ReportReportProfessional

52 Downloads (Pure)


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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages40
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-05C75
  • MSC-05C35
  • METIS-225440
  • IR-65953
  • EWI-3589

Cite this