scientific article; zbMATH DE number 1990727
The stability number \(\alpha(G)\) of the graph \(G\) is the cardinality of a maximum stable set in \(G\). If \(s_k\) denotes the number of stable sets of size \(k\) in graph \(G\), then \[ I(G; x)= \sum^{\alpha(G)}_{k=0} s_k x^k \] is the independence polynomial of \(G\). Hamidoune showed that for any claw-free graph \(G\) (i.e., a graph having no subgraph isomorphic to \(K_{1,3}\)), \(I(G; x)\) is unimodal, that is, there is some \(k\in \{0,1,\dots,\alpha(G)\}\) such that \(0\leq s_0\leq s_1\leq\cdots\leq s_k\geq s_{k+1}\geq\cdots\geq s_{\alpha(G)}\). \textit{J. I. Brown}, \textit{K. Dilcher} and \textit{R. J. Nowakowski} [J. Algebr. Comb. 11, 197-210 (2000; Zbl 0994.05109)] conjectured that \(I(G;x)\) is unimodal for any well-covered graph \(G\) (a graph is well covered if all its maximal stable sets have the same size). Ravindra proved that a tree \(T\) on \(n> 1\) is well covered if and only if \(T\) has a perfect matching \(M\) consisting of pendant edges. If the edges of \(M\) are incident to the vertices of a path, then we call \(T\) a centipede. In this paper we prove that the independence polynomial of any centipede is unimodal. Thus we give a positive, but partial, answer to the conjecture mentioned above and also to the question whether the independence polynomial of any tree is unimodal, formulated by \textit{Y. Alvi}, \textit{P. J. Malde}, \textit{A. J. Schwenk} and \textit{P. Erdős} [Congr. Numerantium 58, 15-23 (1987; Zbl 0679.05061)].
- On unimodality of independence polynomials of some well-covered trees
- Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
- scientific article; zbMATH DE number 2201892
- Unimodality of independence polynomials of very well-covered graphs.
- The unimodality of independence polynomials of some graphs
- Critical and maximum independent sets of a graph
- On the unimodality of independence polynomials of very well-covered graphs
- Counting Markov equivalence classes for DAG models on trees
- Log-concavity of independence polynomials of some kinds of trees
- On the independent set sequence of a tree
- On the roots of independence polynomials of almost all very well-covered graphs
- Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
- Clique cover products and unimodality of independence polynomials
- Some Wellfounded Trees in UniMath
- Graph operations and partial unimodality of independence polynomials
- Co-2-plex polynomials
- On unimodality of independence polynomials of some well-covered trees
- A way to construct independence equivalent graphs
- Unimodality of independence polynomials of rooted products of graphs
- Maximal-clique partitions and the roller coaster conjecture
- The independent set sequence of some families of trees
- On the modes of the independence polynomial of the centipede
- The unimodality of independence polynomials of some graphs
- On the unimodality of independence polynomials of some graphs
- On real-rootedness of independence polynomials of rooted products of graphs
- Trees with real rooted independence polynomials
- Independent sets of random trees and sparse random graphs
- Lorentzian polynomials and the independence sequences of graphs
- A symmetric function approach to log-concavity of independence polynomials
- Building graphs whose independence polynomials have only real roots
- The independence polynomial of rooted products of graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4430893)
