History

Please fill in your query. A complete syntax description you will find on the General Help page.
An identity for the independence polynomials of trees. (English)
Publ. Inst. Math., Nouv. Sér. 50(64), 19-23 (1991).
Summary: The independence polynomial \$ω(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 \$\$ω(T- u)ω(T-v)-ω(T)ω(T-u-v)=-(-x)\sp{d(u,v)}ω(T-P)ω(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 R. E. Merrifield and H. E. Simmons is proved with the help of this identity, which is also compared to some previously known analogous results.