A characterization of extremal graphs without matching-cuts

Rok vydání:	2005
Předmět:	MSC-05C75 MSC-05C35 EWI-3589 METIS-225440 IR-65953
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=dris___00893::b15b431c796ecc192934f114565cd957 Zobrazit plný text záznamu