Koch–Narayan edge bound for uniquely dominated graphs
Follow the latest progress by email.
What edge bound holds for a bipartite graph with a unique minimum dominating set of size four? The focused Koch–Narayan conjecture proposes m(13,4)=21; a counterexample target has thirteen vertices and twenty-two edges.
Why it matters and what counts as progress
Why it matters: It tests a proposed extremal relation between domination uniqueness and graph density.
What counts as progress: A graph exceeding the proposed unique-dominating-set edge bound, or a corrected sharp inequality for an identified graph class.
How the problem developed
- 3 Nov 2025 · Conjecture and partial result [1]
Garrison Koch and Darren Narayan Proposed a sharp edge bound for bipartite graphs with a unique minimum dominating set; proved it for domination number two and for order three times the domination number.
- 12 Jun 2026 · Counterexample [2]
Demonstrandum research campaign Reported a graph with 13 vertices, domination number 4, and 22 edges, exceeding the conjectured bound of 21; independent checkers and certificates are documented.
AI contribution
AI-found graph refutes a Koch–Narayan domination bound
A bipartite graph on 13 vertices has 22 edges and a unique minimum dominating set of size 4, exceeding the proposed bound m(13,4)=21 in Koch–Narayan Conjecture 1.
Sources
Website timeline
Publication dates and editorial changes.