The intersection of all maximum stable sets of a tree and its pendant vertices

DOI10.1016/J.DISC.2007.10.001zbMATH Open1229.05148arXivmath/0008009OpenAlexW2091949473MaRDI QIDQ998466FDOQ998466

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 28 January 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A stable set in a graph G is a set of mutually non-adjacent vertices, alpha(G) is the size of a maximum stable set of G, and core(G) is the intersection of all its maximum stable sets. In this paper we demonstrate that in a tree T, of order n greater than 1, any stable set of size greater or equal to n/2 contains at least one pendant vertex. Hence, we deduce that any maximum stable set in a tree contains at least one pendant vertex. Our main finding is the theorem claiming that if T does not own a perfect matching, then at least two pendant vertices an even distance apart belong to core(T). While it is proved by Levit and Mandrescu that if G is a connected bipartite graph of order at least 2, then the size of core(G) is different from 1, our new statement reveals an additional structure of the intersection of all maximum stable sets of a tree. The above assertions give refining of one result of Hammer, Hansen and Simeone, stating that if a graph G is of order less than 2*alpha(G), then core(G) is non-empty, and also of a result of Jamison, Gunter, Hartnel and Rall, and Zito, saying that for a tree T of order at least two, the size of core(G) is different from 1.

Full work available at URL: https://arxiv.org/abs/math/0008009

Recommendations

• Trees with given stability number and minimum number of stable sets
• Combinatorial properties of the family of maximum stable sets of a graph
• On the maximum orders of an induced forest, an induced tree, and a stable set
• On the number of vertices belonging to all maximum stable sets of a graph
• A new greedoid: The family of local maximum stable sets of a forest

zbMATH Keywords

treecorependant vertexmaximum stable set

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• Combinatorial properties of the family of maximum stable sets of a graph
• On the number of vertices belonging to all maximum stable sets of a graph
• Graphs with unique maximum independent sets

Cited In (2)

• On Sombor index of trees
• Trees with given stability number and minimum number of stable sets

This page was built for publication: The intersection of all maximum stable sets of a tree and its pendant vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q998466)