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
    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

    Identifiers