An identity for the independence polynomials of trees

Ivan Gutman

Abstract: The independence polynomial $\om(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: $$ \om(T-u)\om(T-v)-\om(T)\om(T-u-v) =-(-x)^{d(u,v)} \om(T-P)\om(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.

Classification (MSC2000): 05C05, 05A05, 05A10

Full text of the article:

• Compressed PostScript file (57 kilobytes)
• PDF file (197 kilobytes)