Some Results on the Independence Polynomial of Unicyclic Graphs

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=0ns(G,k)xk$I(G,x) = \sum\nolimits_{k = 0}^n {s\left({G,k} \right)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 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
• 05c30
• 05c31
• 05c38
• 05c69