Very well-covered graphs with log-concave independence polynomials

2004/11/10 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1 · 1 citation
Computer Science · Mathematics · #05A20 #05E99 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Primary 05C69 #Secondary 11B83 #cs.DM #math.CO #msc:05A20 #msc:05C69 #msc:05E99 #msc:11B83

paper · pdf · doi:10.48550/arxiv.math/0411239

8 pages, 4 figures

arxiv created 2004/11/10 · arxiv updated 2011/01/25

Abstract

If for any k the k-th coefficient of a polynomial I(G;x) is equal to the number of stable sets of cardinality k in the graph G, then it is called the independence polynomial of G (Gutman and Harary, 1983). Alavi, Malde, Schwenk and Erdos (1987) conjectured that I(G;x) is unimodal, whenever G is a forest, while Brown, Dilcher and Nowakowski (2000) conjectured that I(G;x) is unimodal for any well-covered graph G. Michael and Traves (2003) showed that the assertion is false for well-covered graphs with a(G) > 3 (a(G) is the size of a maximum stable set of the graph G), while for very well-covered graphs the conjecture is still open. In this paper we give support to both conjectures by demonstrating that if a(G) < 4, or G belongs to K_1,n, P_n: n > 0, then I(G*;x) is log-concave, and, hence, unimodal (where G* is the very well-covered graph obtained from G by appending a single pendant edge to each vertex).

Cited by

• Multiple breaks of log-concavity in the independence polynomials of trees

Related

• Very well-covered graphs and the unimodality conjecture
• A Family of Well-Covered Graphs with Unimodal Independence Polynomials
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• The independence polynomial of trees is not always log-concave starting from order 26
• On the Unimodality of Independence Polynomials of Very Well-Covered Graphs