A characterization of extremal graphs with no matching-cut - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

A characterization of extremal graphs with no matching-cut

Résumé

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.
Fichier principal
Vignette du fichier
dmAE0127.pdf (118.65 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184354 , version 1 (14-08-2015)

Identifiants

Citer

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, ⟨10.46298/dmtcs.3398⟩. ⟨hal-01184354⟩

Collections

INSMI TDS-MACS
36 Consultations
538 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More