Operations on well-covered graphs and the Roller-Coaster conjecture (Q1883660)

Summary: A graph \(G\) is well covered if every maximal independent set has the same cardinality. Let \(s_k\) denote the number of independent sets of cardinality \(k\), and define the independence polynomial of \(G\) to be \(S(G,z) =\sum s_kz^k\). This paper develops a new graph theoretic operation called power magnification that preserves well-coveredness and has the effect of multiplying an independence polynomial by \(z^c\) where \(c\) is a positive integer. We apply power magnification to the recent Roller-Coaster conjecture of Michael and Traves, proving in our main theorem that for sufficiently large independence number \(\alpha,\) it is possible to find well-covered graphs with the last \((.17)\alpha\) terms of the independence sequence in any given linear order. Also, we give a simple proof of a result due to Alavi, Malde, Schwenk, and Erdős on possible linear orderings of the independence sequence of not necessarily well-covered graphs and we prove the Roller-Coaster conjecture in full for independence number \(\alpha\leq 11\). Finally, we develop two new graph operations that preserve well-coveredness and have interesting effects on the independence polynomial.