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

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

1999-12-02

arxiv.org/abs/math/9912022v1

Mathematics

Combinatorics

A preliminary version of this paper has been presented at 9th SIAM Conference on Discrete Mathematics, July 1998, the Universi

Scientific paper

The stability number of a graph G, is the cardinality of a stable set of maximum size in G. If the stability number of G remains the same upon the addition of any edge, then G is called $\alpha ^{+}$-stable. G is a K\"{o}nig-Egervary graph if its order equals the sum of its stability number and the cardinality of a maximum matching. In this paper we characterize $\alpha ^{+}$-stable K\"{o}nig-Egervary graphs, generalizing some previously known results on bipartite graphs and trees. Namely, we prove that a K\"{o}nig-Egervary graph is $\alpha ^{+}$-stable if and only if either the set of vertices belonging to no maximum stable set is empty, or the cardinality of this set equals one, and G has a perfect matching. Using this characterization we obtain several new findings on general K\"{o}nig-Egervary graphs, for example, the equality between the cardinalities of the set of vertices belonging to all maximum stable sets and the set of vertices belonging to no maximum stable set of G is a necessary and sufficient condition for a K\"{o}nig-Egervary graph G to have a perfect matching.

Affiliated with

Also associated with

No associations

Rating

On $α^{+}$-Stable Koenig-Egervary 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 Koenig-Egervary Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On $α^{+}$-Stable Koenig-Egervary Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-262288