{
  "id": "1303.3222",
  "version": "v1",
  "published": "2013-03-13T17:32:03.000Z",
  "updated": "2013-03-13T17:32:03.000Z",
  "title": "On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike trees",
  "authors": [
    "Mohammad Reza Oboudi"
  ],
  "comment": "16 pages,5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a simple graph of order $n$. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of $G$ is the polynomial $I(G,x)=\\sum_{k=0}^{n} s(G,k) x^{k}$, where $s(G,k)$ is the number of independent sets of $G$ of size $k$ and $s(G,0)=1$. Clearly all real roots of $I(G,x)$ are negative. Let $\\xi(G)$ be the largest real root of $I(G,x)$. Let $H$ be a simple graph. By $G \\succeq H$ we mean that $I(H,x)\\geq I(G,x)$ for every $x$ in the interval $[\\xi(G),0]$. We note that $G\\succeq H$ implies that $\\xi(G)\\geq \\xi(H)$. Also we let $G\\succ H$ if and only if $G\\succeq H$ and $I(G,x)\\neq I(H,x)$. We prove that for every tree $T$ of order $n$, $S_n\\succeq T\\succeq P_n$, where $S_n$ and $P_n$ are the star and the path of order n, respectively. By $T=T(n_1,\\ldots,n_k)$ we mean a tree $T$ which has a vertex $v$ of degree $k$ such that $T\\setminus v=P_{n_1-1}+\\cdots+P_{n_k-1}$, that is $T\\setminus v$ is the disjoint union of the paths $P_{n_1-1},\\ldots,P_{n_k-1}$. Let $X=(x_1,\\ldots,x_k)$ and $Y=(y_1,\\ldots,y_k)$, where $x_1\\geq \\cdots\\geq x_k$ and $y_1\\geq\\cdots\\geq y_k$ are real. By $X\\succ Y$, we mean $x_1=y_1,\\ldots,x_{t-1}=y_{t-1}$ and $x_t>y_t$ for some $t\\in\\{1,\\ldots,k\\}$. We let $X\\succ_{d}Y$, if $X\\neq Y$ and for every $j$, $1\\leq j\\leq k$, $\\sum_{i=1}^{j}x_i\\geq \\sum_{i=1}^{j}y_i$. Among all trees with fixed number of vertices, we show that if $(m_1,\\ldots,m_k)\\succ_{d}(n_1,\\ldots,n_k)$, then $T(n_1,\\ldots,n_k)\\succ T(m_1,\\ldots,m_k)$. We conjecture that $T(n_1,\\ldots,n_k)\\succ T(m_1,\\ldots,m_k)$ if and only if $(m_1,\\ldots,m_k)\\succ (n_1,\\ldots,n_k)$, where $\\sum_{i=1}^kn_i=\\sum_{i=1}^km_i$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-03-13T17:32:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "largest real root",
      "independence polynomial",
      "starlike trees",
      "simple graph",
      "independent set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.3222O"
    }
  }
}