{
  "id": "math/0406623",
  "version": "v1",
  "published": "2004-06-30T16:18:47.000Z",
  "updated": "2004-06-30T16:18:47.000Z",
  "title": "Very well-covered graphs and the unimodality conjecture",
  "authors": [
    "Vadim E. Levit",
    "Eugen Mandrescu"
  ],
  "comment": "10 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-06-30T16:18:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C17",
      "05A20",
      "11B83"
    ],
    "keywords": [
      "well-covered graph",
      "unimodality conjecture",
      "independence polynomial",
      "maximum stable set",
      "bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......6623L"
    }
  }
}