2000/02/10 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2
Chemistry · Computer Science · Mathematics · #05C69 #05C70 (Primary) 05C05 #05C75 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Metal-Organic Frameworks: Synthesis and Applications #math.CO #msc:05C05 #msc:05C69 #msc:05C70 #msc:05C75
paper · pdf · doi:10.48550/arxiv.math/0002070
15 pages, 10 figures
arxiv created 2000/02/10 · openalex publication_date 2000/02/10 · arxiv updated 2009/11/30 · 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 stable set of maximum size in G. If alpha(G-e) > alpha(G), then e is an alpha-critical edge, and if mu(G-e) < mu(G), then e is a mu-critical edge, where mu(G) is the cardinality of a maximum matching in G. G is a Koenig-Egervary graph if alpha(G) + mu(G) equals its order. Beineke, Harary and Plummer have shown that the set of alpha-critical edges of a bipartite graph is a matching. In this paper we generalize this statement to Koenig-Egervary graphs. We also prove that in a Koenig-Egervary graph alpha-critical edges are also mu-critical, and that they coincide in bipartite graphs. We obtain that for any tree its stability number equals the sum of the cardinality of the set of its alpha-critical vertices and the size of the set of its alpha-critical edges. Eventually, we characterize the Koenig-Egervary graphs enjoying this property.