Authors:
M.R. Oboudi
Title:
Some results on the independence polynomial of unicyclic graphs
Source:
Discussiones Mathematicae Graph Theory
Received 14.09.2016, Revised 10.01.2017, Accepted 10.01.2017, doi: 10.7151/dmgt.2022

Abstract:
Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)=∑k=0n s(G,k)xk, 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 Cn 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(Cn,t) for sufficiently large t. Finally for every n≥3 we find all connected graphs H such that I(H,x)=I(Cn,x).
Keywords:
independence polynomial, independent set, unicyclic graphs

Links:
PDF