Operations on well-covered graphs and the Roller-Coaster conjecture (Q1883660)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Operations on well-covered graphs and the Roller-Coaster conjecture |
scientific article |
Statements
Operations on well-covered graphs and the Roller-Coaster conjecture (English)
0 references
13 October 2004
0 references
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.
0 references
independent set
0 references
independence polynomial
0 references
power magnification
0 references
well-covered graphs
0 references
independence sequence
0 references
Roller-Coaster conjecture
0 references