On the Structure of $α$-Stable Graphs

Details On the Structure of $α$-Stable Graphs On the Structure of $α$-Stable Graphs

1999-11-28

arxiv.org/abs/math/9911227v1

Mathematics

Combinatorics

A preliminary version of this paper has been presented at The Third Krakow Conference On Graph Theory, September 15-19, 1997,

Scientific paper

The stability number of a graph G is the cardinality of a stability system of G (that is of a stable set of maximum size of G). A graph is alpha-stable if its stability number remains the same upon both the deletion and the addition of any edge. Trying to generalize some stable trees properties, we show that there does not exist any alpha-stable chordal graph, and we prove that: if G is a connected bipartite graph, then the following assertions are equivalent: G is alpha-stable; G can be written as a vertex disjoint union of connected bipartite graphs, each of them having exactly two stability systems covering its vertex set; G has perfect matchings and no edge belongs to all its perfect matchings; from each vertex of G are issuing at least two edges contained in some perfect matchings of G; any vertex of G lies on a cycle, whose edges are alternately in and not in some perfect matching; no vertex belongs to all stability systems of G, and no edge belongs to all its perfect matchings.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97351