Skip to main navigation Skip to Content
Paper IPM / M / 15371  


Abstract:  
Let G be a simple graph on n vertices. An independent set in a
graph is a set of pairwise nonadjacent vertices. The independence
polynomial of G is the polynomial I(G,x)=∑_{k=0}^{n} s(G,k)x^{k}, where s(G,k) is the number of independent sets of G with
size k and s(G,0)=1. A unicyclic graph is a graph containing exactly one cycle.
Let C_{n} be the cycle on n vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs G on n vertices ( except two of them), I(G,t) > I(C_{n},t) for sufficiently large t. Finally for every n ≥ 3 we find all connected graphs H such that I(H,x)=I(C_{n},x).
Download TeX format 

back to top 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir