Independence Polynomials of Graphs

Takayuki Hibi, Selvi Kara, Dalena Vien · 2026

Read Independence Polynomials of Graphs by Takayuki Hibi, Selvi Kara, Dalena Vien (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16695.txt.

Introduction

Hibi, Kara, and Vien study the independence polynomial of a finite simple graph. They focus on its value at x = -1 and its symmetry. The polynomial also links to the h-polynomial of the edge ideal. For big star graphs they pin down when the value is 0, 1, or -1. Only one big star has a symmetric polynomial, they show. Leaf-grafting formulas extend the results to caterpillar graphs. Symmetric cases for cochordal graphs are fully classified.

Catalog record

CREATORTakayuki Hibi, Selvi Kara, Dalena Vien
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51963
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16695

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Independence Polynomials of Graphs Thanks: The present paper was completed while the first author stayed at Bryn Mawr College, Pennsylvania, February 28 – March 21, 2026. Takayuki Hibi, Selvi Kara, Dalena Vien Abstract . In this paper, we study the independence polynomial P G ​ ( x ) P_{G}(x) of a finite simple graph G G , with emphasis on the evaluation at x = − 1 x=-1 , symmetry, and its connection with the h h -polynomial of the edge ideal of G G . For big star graphs, we determine exactly when P G ​ ( − 1 ) P_{G}(-1) is 0 0 , 1 1 , or − 1 -1 , characterize the pseudo-Gorenstein ∗ members, and show that there is a unique big star with symmetric independence polynomial. We also study graphs obtained from a graph H H by attaching leaves to selected vertices. We derive an explicit formula for the resulting independence polynomial, determine the corresponding value at − 1 -1 , and prove that if every vertex of H H receives at least one leaf, then the independence polynomial is symmetric if and only if each vertex receives exactly two leaves. As an application, we obtain exact criteria for the values of P G ​ ( − 1 ) P_{G}(-1) and for the pseudo-Gorenstein ∗ members of caterpillar graphs. For cochordal graphs, we classify all symmetric independence polynomials. Finally, for connected graphs on n n vertices with small independence numbers, we determine the exact range of possible values of P G ​ ( − 1 ) P_{G}(-1) . 2020 Mathematics Subject Classification 05C38,05C31 Introduction For a finite simple graph G , the independence polynomial of G is P_{G}(x)=\sum_{i=0}^{\alpha(G)}g_{i}(G)x^{i}, where g_{i}(G) denotes the number of independent sets of G of size i . This polynomial is one of the basic enumerative invariants attached to a graph. Beyond its purely combinatorial meaning, the independence polynomial appears as the partition function of the hard-core model in statistical physics [ 7 ] and its zeros play an important role in questions related to the Lovász local lemma and zero-free regions from probabilistic combinatorics [ 21 ] . Thus independence polynomials sit at the intersection of graph enumeration, statistical physics, probabilistic combinatorics, and commutative algebra; see, for example, [ 17 , 8 , 2 , 13 ] . In this paper, we focus on two aspects of P_{G}(x) : the evaluation at x=-1 and symmetry. The value P_{G}(-1) is the alternating count of independent sets, equivalently the negative of the reduced Euler characteristic of the independence complex \Ind(G) . This quantity has been studied from several points of view, including bounds in terms of graph structure, decycling number, and realizability problems; see [ 4 , 16 , 19 , 3 ] . The second theme, symmetry of the independence polynomial, belongs to the broader study of palindromicity, unimodality, log-concavity, and roots. There is a substantial literature on constructions that force symmetry, notably the two-whisker construction of Stevanović and its later extensions and refinements; see [ 22 , 18 , 20 ] . Even for trees, these questions remain subtle: for example, if T is a tree, then P_{T}(-1)\in\{-1,0,1\} by [ 16 ] , yet it is far from clear which trees realize which value. A second source of motivation to study independence polynomials comes from commutative algebra. Let I(G) be the edge ideal of G , and let h_{G}(t) denote the h -polynomial of S/I(G) . It was discussed by the authors in [ 13 ] that the value P_{G}(-1) controls the top coefficient of h_{G}(t) . Moreover, the multiplicity of -1 as a root of P_{G}(x) , denoted by M(G) , controls the degree of the h -polynomial by [ 2 , Theorem 4.4] , \deg h_{G}(t)=\alpha(G)-M(G). Thus the multiplicity of -1 as a root of P_{G}(x) determines the \mathfrak{a} -invariant of S/I(G) . Additionally, the condition that G be pseudo-Gorenstein ∗ , a new concept introduced and studied by the authors in [ 13 ] , is equivalent to the simple identity P_{G}(-1)=(-1)^{\alpha(G)}. This makes the evaluation at -1 a natural meeting point between the combinatorics of independent sets and the algebra of edge ideals. Our first focus is on big star graphs , obtained by gluing several paths at a common center. For these graphs, we show that the vanishing of P_{G}(-1) is completely determined by congruence classes modulo 3 , while the sign in the nonzero cases is controlled by congruence classes modulo 6 ; see 2.4 and 2.5 . We then obtain a complete description of pseudo-Gorenstein ∗ big stars in Section 2 . We also study symmetry and prove in 2.9 that, among all big stars, there is exactly one with symmetric independence polynomial. Our second focus is on the effects of whiskering , attaching leaves. In Section 3 we provide a general formula for the independence polynomial of a graph obtained from a base graph H by attaching f_{i} leaves to selected vertices x_{i} . When the polynomial is evaluated at -1 , a striking simplification occurs: only the set C\subseteq V(H) of vertices that actually receive leaves matters. More precisely, P_{G}(-1)=0 unless C is an independent set of H , and when C is independent we obtain P_{G}(-1)=(-1)^{|C|}P_{H-N_{H}[C]}(-1). We also prove in 3.2 that if every vertex of H receives at least one leaf, then the resulting graph has symmetric independence polynomial if and only if exactly two leaves are attached to each vertex. This recovers Stevanović’s two-whisker construction [ 22 ] , which was later shown to yield not only symmetry but also unimodality [ 20 ] , and shows that in our leaf-attachment setting it is in fact the unique symmetric case. As an application of the whiskering, we study caterpillar graphs , obtained by attaching leaves to paths. Encoding the locations of the legs along the path leads to a product formula for P_{G}(-1) in 3.5 . From this we determine when 0,\pm 1 occurs; see Sections 3.1 and 3.1 . In addition, we characterize pseudo-Gorenstein ∗ caterpillars in Section 3.1 . We also study cochordal graphs , equivalently graphs whose complements are chordal. This class is natural both combinatorially and algebraically: independent sets of G are cliques of \overline{G} , and cochordal graphs play a central role in the study of edge ideals with linear resolutions [ 6 , 10 ] . Since clique complexes of chordal graphs are quasi-forests [ 11 ] , the independence polynomial of a cochordal graph can be approached through the b -sequence description of quasi-forests from [ 9 ] . Using [ 9 ] , we prove that a cochordal graph G with d=\alpha(G)\geq 2 has symmetric independence polynomial if and only if P_{G}(x)=(1+x)^{d}+mx(1+x)^{d-2} for some m\geq 0 . In particular, every symmetric independence polynomial of a cochordal graph is automatically unimodal. We also recall that P_{G}(-1)=1-k where k is the number of connected components of \overline{G} ; see Section 4 . Finally, we investigate how large or small P_{G}(-1) can be when the independence number is small. For connected graphs on n vertices with \alpha(G)\leq 2 , 5.4 shows that every integer in the interval \left[-(n-1),\left\lfloor\frac{(n-2)^{2}}{4}\right\rfloor-1\right] occurs as P_{G}(-1) .

Read the complete text