Integer roots of graph domination polynomials
Follow the latest progress by email.
The integer domination-root conjecture restricts integer zeros of domination polynomials of graphs. The counterexample target is a connected graph with domination polynomial vanishing at −4; one reported witness has 33 vertices and 36 edges.
Why it matters and what counts as progress
Why it matters: It tests whether the proposed integer-root restriction holds even for connected finite graphs.
What counts as progress: An exact domination-polynomial factorization producing a forbidden integer root, or a valid root restriction for a specified graph class.
How the problem developed
- 2010 · Conjecture [1]
Akbari, Alikhani, Oboudi and Peng They proposed that the only integer roots of any graph’s domination polynomial are 0 and −2; earlier proofs covered trees, unicyclic graphs and restricted cases.
- 31 Jul 2026 · Counterexample [2]
Saeid Alikhani and Max Griswold Their preprint gives a connected 33-vertex graph whose domination polynomial has the integer root −4, with an explicit polynomial factorization.
AI contribution
On the Integer Domination Root Conjecture
A specified connected graph with 33 vertices and 36 edges has domination polynomial divisible by x+4. Its exact factorization includes x¹¹(x+2)(x+4)(x²+3x+1), so −4 is an integer domination root.
Sources
Website timeline
Publication dates and editorial changes.
Claude-origin construction gives an integer domination root of −4