1. Upper Bounds for the Independence Polynomial of Graphs at -1
- Author
-
Fayun Cao and Han Ren
- Subjects
Polynomial (hyperelastic model) ,Degree (graph theory) ,General Mathematics ,010102 general mathematics ,Circuit rank ,Disjoint sets ,01 natural sciences ,Graph ,010101 applied mathematics ,Combinatorics ,Cardinality ,0101 mathematics ,Independence (probability theory) ,Mathematics ,Independence number - Abstract
The independence polynomial of a graph G is $$I(G;x)=\sum _{k=0}^{\alpha (G)} s_{k}\cdot x^{k}$$ , where $$s_{k}$$ and $$\alpha (G)$$ denote the number of independent sets of cardinality k and the independence number of G, respectively. We say that a cycle is a $$\tilde{3}$$ -cycle if its length is divisible by 3, otherwise a non- $$\tilde{3}$$ -cycle. Define $$\phi (G)$$ to be the decycling number of G. Engstrom proved that $$|I(G;-1)| \le 2^{\phi (G)}$$ for any graph G. In this paper, we first prove that $$|I(G;-1)|\le 2^{\beta (G)}-\beta (G)$$ for graphs with non- $$\tilde{3}$$ -cycles, where $$\beta (G)$$ is the cyclomatic number of G. Infinitely many examples show that there do exist graphs satisfying $$\beta (G)=\phi (G)$$ and containing non- $$\tilde{3}$$ -cycles. In such a case, it improves the Engstrom’s result. Furthermore, $$|I(G;-1)|\le 2^{k}$$ provided that all cycles of G are pairwise disjoint, where k is the number of $$\tilde{3}$$ -cycles of G. This provides a new perspective on estimating the independence polynomial at -1 of many special graphs. In the case G contains no vertices of degree 1, $$|I(G;-1)|\le 2^{\beta (G)}-1$$ if $$\beta (G)\ge 2$$ , and $$|I(G;-1)|\le 2^{\beta (G)-1}$$ if G contains a non- $$\tilde{3}$$ -cycle.
- Published
- 2021