← All problems

Pandey parity conjecture for generalized Petersen graphs

Less than 1 year old · traced to

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

Equivalent formulations
  1. For every n≥2k+1n\geq2k+1, is the independence polynomial of GP(n,k)GP(n,k) real-rooted if and only if kk is even?

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

Progress summary

Refreshed
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)I(GP(n,k),x) is real-rooted exactly for even kk, for every n≥2k+1n\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∈1,2,3,4k\in\\{1,2,3,4\\} and values of nn up to 3030. Odd kk produced nonreal conjugate roots, while even kk 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 nn and kk.

Sources

Solutions 0

No solutions have been posted yet.