On \(\alpha^{+}\)-stable König-Egerváry graphs (Q1869204): Difference between revisions

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.