Pandey parity conjecture for generalized Petersen graphs

Less than 1 year old · traced to 2026

Let $\operatorname{GP}(n,k)$ be the generalized Petersen graph, and let $\operatorname{I}(\operatorname{GP}(n,k),x)$ denote its independence polynomial. For all integers $n\geq 2k+1$ , Parity Conjecture. the polynomial $\operatorname{I}(\operatorname{GP}(n,k),x)$ has only real roots if and only if $k$ is even. The conjecture is motivated by computations showing exclusively real negative roots for even $k$ and complex conjugate root structures for odd $k$ ; a proof of the parity dichotomy is not provided.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Pandey parity conjecture for generalized Petersen graphs
For every $n\geq2k+1$ , is the independence polynomial of $GP(n,k)$ real-rooted if and only if $k$ is even?

References

Primary source

Rohan Pandey, “Parity-Dependent Real-Rootedness in Independence Polynomials of Generalized Petersen Graphs”, arXiv:2601.03293 (2026).

Posted 2 months ago

Progress summary

Refreshed 1 month ago

Open

A recent computation supports the parity pattern, but no proof or counterexample has been found.

The conjecture asks whether $I(GP(n,k),x)$ is real-rooted exactly for even $k$ , for every $n\ge 2k+1$ . It was formulated in a computational study of generalized Petersen graphs; no proposer or publication date is specified in the retrieved material.

Computational evidence

An exact transfer-matrix computation tested $k\in\\{1,2,3,4\\}$ and values of $n$ up to $30$ . Odd $k$ produced nonreal conjugate roots, while even $k$ produced apparently strictly negative real roots; the authors explicitly state that finite computation and numerical root-finding provide no proof or counterexample.

Current status (as of March 2026): The conjecture has computational support for tested cases, but remains completely open for general $n$ and $k$ .

Sources

No solutions have been posted yet.