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.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!