An independent set in a graph G is a set of pairwise non-adjacent
vertices, and the independence number α(G) is the cardinality of a maximum stable set in G. The independence polynomial of G is
I(G;x)=s0+s1x+s2x2+...+sαxα, α=α(G),
where sk is the number of independent sets of size k in G (I. Gutman and F. Harary, 1983). The Fibonacci index Fib(G) of a graph G is the number of all its independent sets, i.e., Fib(G)=I( G;1). Tight lower and upper bounds for Fibonacci index are known for general graphs, connected or not, and the corresponding extremal graphs are characterized [6], [15].
In this paper, we give explicit formulae for independence polynomials of these extremal graphs, which we further use to analyze some of their properties (unimodality, log-concavity). |