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/}
}
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/