Bencs Ferenc

Előadó: Bencs Ferenc

Cím: 

Absztrakt: The independence polynomial of a graph $G$ is $$I(G,x)=\sum\limits_{k\ge 0}i_k(G)x^k,$$ where  $i_k(G)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0(G)=1$). Denote by $\beta(G)$ its smallest real root. We will show that for any connected  graph $(G,u)$ there exists a tree $(T,r)$, such that $\frac{I(G-u,x)}{I(G,x)}=\frac{I(T-r,x)}{I(T,x)}$. We will give a simple construction for such a tree, and we will prove some its properties. As a corollary we will see some inequalities between the $\beta$ parameters, a method to prove the real-rootedness of some trees and graphs.