Very well-covered graphs and the unimodality conjecture
| dc.creator | Levit, Vadim E. | |
| dc.creator | Mandrescu, Eugen | |
| dc.date | 2004-06-30 | |
| dc.date.accessioned | 2026-07-07T05:09:51Z | |
| dc.date.available | 2026-07-07T05:09:51Z | |
| dc.description | If for any $k$ the $k$-th coefficient of a polynomial I(G;x) is equal to the number of stable sets of cardinality $k$ in the graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). Let $a$ be the size of a maximum stable set. Alavi, Malde, Schwenk and Erdos (1987)conjectured that I(T,x) is unimodal for any tree T, while, in general, they proved that for any permutation $p$ of {1,2,...,a} there is a graph such that s_{p(1)}<s_{p(2)}<...<s_{p(a)}. Brown, Dilcher and Nowakowski (2000) conjectured that I(G;x) is unimodal for any well-covered graph. Michael and Traves (2002) provided examples of well-covered graphs with non-unimodal independence polynomials. They proposed the "roller-coaster" conjecture: for a well-covered graph, the subsequence (s_{a/2},s_{a/2+1},...,s_{a}) is unconstrained in the sense of Alavi et al. The conjecture of Brown et al. is still open for very well-covered graphs. In this paper we prove that s_{(2a-1)/3}>=...>=s_{a-1}>=s_{a} are valid for any (a) bipartite graph $G$; (b) quasi-regularizable graph $G$ on $2a$ vertices. In particular, we infer that this is true for (a) trees, thus doing a step in an attempt to prove Alavi et al.' conjecture; (b) very well-covered graphs. Consequently, for this case, the unconstrained subsequence appearing in the roller-coaster conjecture can be shorten to (s_{a/2},s_{a/2+1},...,s_{(2a-1)/3}). We also show that the independence polynomial of a very well-covered graph $G$ is unimodal for a<10, and is log-concave whenever a<6. | |
| dc.description | 10 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/math/0406623 | |
| dc.identifier | http://arxiv.org/abs/math/0406623 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71738 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69, 05C17 (Primary) 05A20, 11B83 (Secondary) | |
| dc.title | Very well-covered graphs and the unimodality conjecture | |
| dc.type | text |