The Independece Polynomials Of Graphs

The independence polynomial I(G;x)of a graph G is defined as follows:(G;x)=∑k=0α(G)sk·xk,where sk is the number of k-independent sets and a(G)is the size of a maximum independent set of graph G.In this dissertation,we investigate some important conbinational properties of I(G;x)and obtain the following results:(1)For a graph G with at most one cycle,wtih the girth g≥6(g≥5)and G≠qC7(G≠gK2)for any integer q≥1,I(G;-1)=0 provided that G is well-covered(very well-covered).This implies the number of independent sets of even size equals that of odd size.(2)We construct a series G1,G2,…,Gn,…of graphs satisfying |I(Gn+1;-1)|—|I(Gn+1;-1)|=2n,with β(Gn+1)=β(Gn)+1(n=1,2,…).This implies that the difference of such two numbers may be exponentially large.On the other hand,there also exits a sequence H1,H2,…,Hn,…of graphs with β(Hn+1)=β(Hn)+1(n=1,2,…)such that |I(Hn;-1)|≤M for a fixed number M.(3)For a graph G(without pendant),|I(G;-1)|≤2β(G)-1 if G has exactly two cycles.Furthermore,there is a graph G satisfying I(G;-1)=q when |q|≤2β,where q is an integer and β(G)=β.This confirms a conjecture due to Levit.VE.and Mandrescu.E.