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

Details On $α^{++}$-Stable Graphs On $α^{++}$-Stable Graphs

2000-03-09

arxiv.org/abs/math/0003057v1

Mathematics

Combinatorics

11 pages, 3 figures

Scientific paper

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 $\alpha ^{++}$-stable graphs, namely, the graphs whose stability numbers are invariant to adding any two edges from their complements. We show that a K\"{o}nig-Egerv\'{a}ry graph is $\alpha ^{++}$-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 $\alpha ^{++}$-stability of bipartite graphs and trees. For instance, we prove that a bipartite graph is $\alpha ^{++}$-stable if and only if it is well-covered and C4-free.

Affiliated with

Also associated with

No associations

Rating

On $α^{++}$-Stable Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On $α^{++}$-Stable Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On $α^{++}$-Stable Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-654097