2009/08/10 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Computer Science · Mathematics · #05C69 (Primary) #05C76 (Secondary) #Advanced Operator Algebra Research #Algebraic structures and combinatorial models #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #cs.DM #math.CO #msc:05C69 #msc:05C76
paper · pdf · doi:10.48550/arxiv.0908.1313
12 pages, 9 figures
openalex publication_date 2009/08/10 · arxiv created 2009/08/25 · arxiv updated 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The stability number of a graph G, denoted by alpha(G), is the cardinality of a maximum stable set, and mu(G) is the cardinality of a maximum matching in G. If alpha(G)+mu(G) equals its order, then G is a Konig-Egervary graph. In this paper we deal with square-stable graphs, i.e., the graphs G enjoying the equality alpha(G)=alpha(G2), where G2 denotes the second power of G. In particular, we show that a Konig-Egervary graph is square-stable if and only if it has a perfect matching consisting of pendant edges, and in consequence, we deduce that well-covered trees are exactly the square-stable trees.