2000/03/09 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1
Mathematics · #05C69 #05C70 (Primary) 05C05 #05C75 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C69 #msc:05C70 #msc:05C75
paper · pdf · doi:10.48550/arxiv.math/0003057
11 pages, 3 figures
arxiv created 2000/03/09 · arxiv updated 2009/11/30
The stability number of a graph G, denoted by alpha(G), is the cardinality of a stable set of maximum size in G. A graph is well-covered if every maximal stable set has the same size. G is a Koenig-Egervary graph if its order equals alpha(G) + mu(G), where mu(G) is the cardinality of a maximum matching in G. In this paper we characterize α++-stable graphs, namely, the graphs whose stability numbers are invariant to adding any two edges from their complements. We show that a König-Egerváry graph is α++-stable if and only if it has a perfect matching consisting of pendant edges and no four vertices of the graph span a cycle. As a corollary it gives necessary and sufficient conditions for α++-stability of bipartite graphs and trees. For instance, we prove that a bipartite graph is α++-stable if and only if it is well-covered and C4-free.