Parity-Dependent Real-Rootedness in Independence Polynomials of Generalized Petersen Graphs

Abstract

We investigate the distribution of zeros of the independence polynomial $\mathrm{I}(G,x)$ for the family of Generalized Petersen graphs $\mathrm{GP}(n,k)$ in the complex plane. While the independence numbers and coefficients of these graphs have been studied, the global behavior of their roots remains largely unexplored. Using an exact transfer matrix algorithm parameterized by $k$, we compute $\mathrm{I}(\mathrm{GP}(n,k),x)$ for $n$ up to $30$ and $k\in \{1,2,3,4\}$. Our numerical analysis reveals a striking parity-based dichotomy: for odd $k$, the roots exhibit complex conjugate structures accumulating on closed curves, whereas for even $k$, the roots appear to be strictly real and negative. Motivated by this evidence, we conjecture that $\mathrm{I}(\mathrm{GP}(n,k),x)$ is real-rooted, and hence log-concave, if and only if $k$ is even. This phenomenon connects algebraic properties of $\mathrm{GP}(n,k)$ to questions about zero-free regions and limiting behavior in the hard-core lattice gas model.

5 pages, 2 figures