An Identity for the Independence Polynomials of Trees


Ivan Gutman


The independence polynomial $\omega(G)$ of a graph $G$ is a polynomial whose $k$-th coefficient is the number of selections of $k$ independent vertices in $G$. The main result of the paper is the identity: $$ \omega(T-u)\omega(T-v)-\om(T)\omega(T-u-v) = -(-x)^{d(u,v)} \omega(T-P)\omega(T-[P]) $$ where $u$ and $v$ are distinct vertices of a tree $T$, $d(u,v)$ is the distance between them and $P$ is the path connecting them; the subgraphs $T-P$ and $T-[P]$ are obtained by deleting from $T$ the vertices of $P$ and the vertices of $P$ together with their first neighbors. A conjecture of Merrifield and Simmons is proved with the help of this identity, which is also compared to some previously known analogous results.