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=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). | |
Keywords: independence polynomial, independent set, unicyclic graphs | |
Links: |