On the Unimodality of Independence Polynomials of Very Well-Covered Graphs

2017/09/24 by Brown, Jason I., Cameron, Ben
#05C31 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1709.08236

Abstract

The independence polynomial i(G,x) of a graph G is the generating function of the numbers of independent sets of each size. A graph of order n is very well-covered if every maximal independent set has size n/2. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.

Related

• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• A Family of Well-Covered Graphs with Unimodal Independence Polynomials
• Very well-covered graphs and the unimodality conjecture
• Very well-covered graphs with log-concave independence polynomials
• On Unimodality of Independence Polynomials of some Well-Covered Trees