PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.) Vol. 50(64) Preimenovati datoteke, proveriti paginaciju!!!, pp. 1923 (1991) 

An identity for the independence polynomials of treesIvan GutmanPrirodnomatematicki fakultet, Kragujevac, YugoslaviaAbstract: 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(Tu)\om(Tv)\om(T)\om(Tuv) =(x)^{d(u,v)} \om(TP)\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 $TP$ 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:
Electronic fulltext finalized on: 2 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts
