2016/12/12 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +2 · 1 citation
Computer Science · Mathematics · #05C31 #05C69 (Primary) 05C30 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Graph theory and applications #Limits and Structures in Graph Theory #acm:05C30 #acm:05C31 #acm:05C69 #cs.DM #math.CO #msc:05C30 #msc:05C31 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1612.03736
9 pages
arxiv created 2016/12/12 · openalex publication_date 2016/12/12 · arxiv updated 2016/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is well-covered if all its maximal independent sets are of the same cardinality (Plummer, 1970). If G is a well-covered graph, has at least two vertices, and G-v is well-covered for every vertex v, then G is a 1-well-covered graph (Staples, 1975). We call G a λ-quasi-regularizable graph if λ |S| =< |N(S)| for every independent set S of G. The independence polynomial I(G;x) is the generating function of independent sets in a graph G (Gutman & Harary, 1983). The Roller-Coaster Conjecture (Michael & Travis, 2003), saying that for every permutation σ of the set (α/2),...,α there exists a well-covered graph G with independence number α such that the coefficients (sk) of I(G;x) are chosen in accordance with σ, has been validated in (Cutler & Pebody, 2017). In this paper, we show that independence polynomials of λ-quasi-regularizable graphs are partially unimodal. More precisely, the coefficients of an upper part of I(G;x) are in non-increasing order. Based on this finding, we prove that the domain of the Roller- Coaster Conjecture can be shortened for well-covered graphs and 1-well-covered graphs.