Geodesic
An Identity for the Independence Polynomials of Trees
Publications de l'Institut Mathématique, _N_S_50 (1991) no. 64, p. 19 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 05C05 05A05 05A10 
@article{PIM_1991_N_S_50_64_a3,
     author = {Ivan Gutman},
     title = {An {Identity} for the {Independence} {Polynomials} of {Trees}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {19 },
     publisher = {mathdoc},
     volume = {_N_S_50},
     number = {64},
     year = {1991},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PIM_1991_N_S_50_64_a3/}
}
TY  - JOUR
AU  - Ivan Gutman
TI  - An Identity for the Independence Polynomials of Trees
JO  - Publications de l'Institut Mathématique
PY  - 1991
SP  - 19 
VL  - _N_S_50
IS  - 64
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PIM_1991_N_S_50_64_a3/
LA  - en
ID  - PIM_1991_N_S_50_64_a3
ER  - 
%0 Journal Article
%A Ivan Gutman
%T An Identity for the Independence Polynomials of Trees
%J Publications de l'Institut Mathématique
%D 1991
%P 19 
%V _N_S_50
%N 64
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PIM_1991_N_S_50_64_a3/
%G en
%F PIM_1991_N_S_50_64_a3
Ivan Gutman. An Identity for the Independence Polynomials of Trees. Publications de l'Institut Mathématique, _N_S_50 (1991) no. 64, p. 19 . http://geodesic.mathdoc.fr/item/PIM_1991_N_S_50_64_a3/