On \(\alpha^{+}\)-stable König-Egerváry graphs
type: Item
instance of: scholarly article
title: On \(\alpha^{+}\)-stable König-Egerváry graphs
zbMATH Open document ID: 1017.05086
DOI: 10.1016/S0012-365X(02)00528-9
author: Vadim E. Levit
author: Eugen Mandrescu
published in: Discrete Mathematics
publication date: 2003-04-09T00:00:00Z
review text: The stability number \(\alpha(G)\) of a graph \(G\) is the cardinality of a stable set of maximum size in \(G\). \(G\) is said to be \(\alpha^+\)-stable if its stability number remains the same upon the addition of any edge. \(G\) is called a König-Egeráry graph if its order equals \(\alpha(G)+ \mu(G)\), where \(\mu(G)\) is the size of a maximum matching in \(G\). The paper characterizes \(\alpha^+\)-stable König-Egeráry graphs, thereby generalizing some previously known results on bipartite graphs and trees. It is also shown that a certain equality is a necessary and sufficient condition for a König-Egeráry graph to have a perfect matching.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1895992
zbMATH Keywords: maximum stable set
zbMATH Keywords: maximum matching
zbMATH Keywords: perfect matching
zbMATH Keywords: blossom
zbMATH Keywords: \(\alpha^+\)-stable graph
zbMATH Keywords: stability number
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00528-9
OpenAlex ID: W46117055
description: scientific article; zbMATH DE number 1895992