Operations on Well-Covered Graphs and the Roller-Coaster Conjecture

  • Philip Matchett

Abstract

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 will 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 will 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 will prove the Roller-Coaster Conjecture in full for independence number $\alpha \leq 11$. Finally, we will develop two new graph operations that preserve well-coveredness and have interesting effects on the independence polynomial.

Published
2004-07-01
Article Number
R45