2000/08/01 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Computer Science · Mathematics · #05C05 #05C12 #05C69 (Primary) #05C70 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C05 #msc:05C12 #msc:05C69 #msc:05C70
paper · pdf · doi:10.48550/arxiv.math/0008009
11 pages, 7 figures
arxiv created 2000/08/01 · openalex publication_date 2000/08/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.