On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike trees

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⪰H$ we mean that $I(H,x)\ge I(G,x)$ for every $x$ in the interval $[\xi (G),0]$. We note that $G⪰H$ implies that $\xi (G)\ge \xi (H)$. Also we let $G\succ H$ if and only if $G⪰H$ and $I(G,x)\ne I(H,x)$. We prove that for every tree $T$ of order $n$, $S_n⪰T⪰P_n$, where $S_n$ and $P_n$ are the star and the path of order n, respectively. By $T=T(n_1,\dots ,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},\dots ,P_{n_k-1}$. Let $X=(x_1,\dots ,x_k)$ and $Y=(y_1,\dots ,y_k)$, where $x_1\ge \cdots \ge x_k$ and $y_1\ge \cdots \ge y_k$ are real. By $X\succ Y$, we mean $x_1=y_1,\dots ,x_{t-1}=y_{t-1}$ and $x_t>y_t$ for some $t\in \{1,\dots ,k\}$. We let $X{\succ }_{d}Y$, if $X\ne Y$ and for every $j$, $1\le j\le k$, ${\sum }_{i=1}^j{x}_i\ge {\sum }_{i=1}^j{y}_i$. Among all trees with fixed number of vertices, we show that if $(m_1,\dots ,m_k){\succ }_d(n_1,\dots ,n_k)$, then $T(n_1,\dots ,n_k)\succ T(m_1,\dots ,m_k)$. We conjecture that $T(n_1,\dots ,n_k)\succ T(m_1,\dots ,m_k)$ if and only if $(m_1,\dots ,m_k)\succ (n_1,\dots ,n_k)$, where ${\sum }_{i=1}^k{n}_i={\sum }_{i=1}^k{m}_i$.

arXiv comment16 pages,5 figures