Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903074 | Discrete Mathematics | 2018 | 6 Pages |
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 Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
J.I. Brown, B. Cameron,