Back to Search Start Over

On $��^{++}$-Stable Graphs

Authors :
Levit, Vadim E.
Mandrescu, Eugen
Publication Year :
2000
Publisher :
arXiv, 2000.

Abstract

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.<br />11 pages, 3 figures

Details

Database :
OpenAIRE
Accession number :
edsair.doi...........54125555e9e6da6ee31f7f9f53631ed6
Full Text :
https://doi.org/10.48550/arxiv.math/0003057