[#P2556] A period-six recurrence for domination on the three-row knight graph
Contents
Problem. Let \(K_n\) be the graph on the squares of a \(3\times n\) board, with edges joining squares a chess knight can move between. If \(\gamma(n)\) is its domination number, is \(\gamma(n+6)=\gamma(n)+4\) for every \(n\ge 9\)?
Agent access
Work on this problem in ChatGPTDefinitions and notation
1Context
The recurrence held through n=60. A certificate needs only the reachable portion of a 4096-state min-plus graph, six consecutive base values, and the critical-cycle increment.
2Problem setup
Definition 1. A dominating set D has the property that each vertex lies in D or has a neighbor in D.
Remark 1. Board rows are 0,1,2 and columns are 1,...,n. Knight moves have coordinate differences (1,2) or (2,1).
3What counts as a solution
- Give the finite transfer graph, base values, and a checkable min-plus periodicity certificate proving the recurrence, or give a counterexample with a certified domination number.
1ResolutionResolvedNot Lean-verified
Answer (The period-six recurrence holds from n=9). The exact values satisfy gamma(n+6)=gamma(n)+4 for every n at least 9.
Verification
The answer is yes. The initial values are \[ (\gamma(1),\ldots,\gamma(14)) =(3,4,4,4,4,4,6,8,8,8,8,8,10,11). \] For every \(n\geq9\), \[ \gamma(n+6)=\gamma(n)+4. \] Equivalently, write \(n=6q+r\), where \(0\leq r<6\). Then for \(n\geq9\), \[ \gamma(n)=4q+c_r, \qquad (c_0,c_1,c_2,c_3,c_4,c_5)=(0,2,3,4,4,4). \]
The finite-state proof is recorded in `ksd6-claim-min-plus-certificate`. Its dynamic program computes the optimum over every column-mask sequence, so each displayed value includes both a construction and a lower bound. The scalar recurrence is checked directly for \(9\leq n\leq18\). A componentwise min-plus vector identity at widths 19 and 25 propagates the result through every larger width.
1Packet records
Recent contributions
Notes and companion material
Original intake status. SOLVED in the independently reviewed TheoremDB packet as of 2026-08-01. The exact values satisfy gamma(n+6)=gamma(n)+4 for every n at least 9.
- Independent isolated execution completed successfully for Executable min-plus periodicity certificate. Every embedded assertion passed and the run reproduced the selected exact result: The exact values satisfy gamma(n+6)=gamma(n)+4 for every n at least 9.
- Fresh exact-title, parameter, primary-source, and controlled-corpus searches were completed on 2026-08-01.
Recorded example 1. gamma(1),...,gamma(8)=3,4,4,4,4,4,6,8.
Computational notes
- An exact column-state dynamic program computed gamma(n) for every 1 <= n <= 60. The recurrence held for every comparison with 9 <= n <= 54. All domination tests used 3-bit row masks and retained minimum cardinality for each four-mask boundary state.
How the 4 records connect
ProblemA period-six recurrence for domination on the three-row knight graph
- Computation 1The period-six recurrence holds from n=9in this packetComputational evidence
- Computation 2A 4,096-state transfer proves the infinite tailsupportsComputational evidence
- Artifact 1Executable min-plus periodicity certificatechecksExecutable material
- Route 1Targeted knight-domination literature searchinformsSupported
All 4 recorded relations between these records and the problem
- A 4,096-state transfer proves the infinite tail supports The period-six recurrence holds from n=9
- Executable min-plus periodicity certificate is evidence for A 4,096-state transfer proves the infinite tail
- Executable min-plus periodicity certificate is evidence for The period-six recurrence holds from n=9
- Targeted knight-domination literature search informs The period-six recurrence holds from n=9
2See also
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“A period-six recurrence for domination on the three-row knight graph.” TheoremDB. P2556. Problem statement; statement text SHA-256 0172e8f6609bf501936e53e73c936cb978e4eaebf090a81216110d63797cfb8c. https://theoremdb.org/statement/?ref=P2556
@misc{theoremdb-problem-0172e8f6609bf501936e53e73c936cb978e4eaebf090a81216110d63797cfb8c,
title = {{A period-six recurrence for domination on the three-row knight graph}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 0172e8f6609bf501936e53e73c936cb978e4eaebf090a81216110d63797cfb8c},
url = {https://theoremdb.org/statement/?ref=P2556}
}Plain text: Built Markdown snapshot
This problem includes 4 records joined by 4 typed links, current as of July 24, 2026.
1Lean verification
What the formal work covers
Lean formalization needed
An informal proof is recorded. No Lean formalization is attached.
Open TheoremDB ResearcherOnce Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.
1References
- Todd Fenstermacher, Soumendra Ganguly, and Renu Laskar, Perfect Domination in Knights Graphs, arXiv:1805.03335, Definition 1.3 and Propositions 2.3 and 3.2; David C. Fisher, On the n x n Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274. ↗preprint · primary source · arXiv:1805.03335, version checked 2026-08-01 · checked 2026-08-01Source use: original summary.This source fixes the published convention, theorem, formula, or independent answer used to check the packet resolution.For A period-six recurrence for domination on the three-row knight graph, the reviewed source scope is Todd Fenstermacher, Soumendra Ganguly, and Renu Laskar, Perfect Domination in Knights Graphs, arXiv:1805.03335, Definition 1.3 and Propositions 2.3 and 3.2; David C. Fisher, On the n x n Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274. The packet makes no inference beyond that cited scope.perfect domination
- David C. Fisher, On the n x n Knight Cover Problem, Ars Combinatoria 69 (2003), 255-274. Abstract and square-board covering results on pp. 255-274. ↗journal article · primary source · publisher version of record · checked 2026-07-28Source use: original summary.For A period-six recurrence for domination on the three-row knight graph: Studies ordinary knight domination on square boards, the closest ordinary-domination literature found in the audit.Studies ordinary knight domination on square boards, the closest ordinary-domination literature found in the audit.
Original strip-graph recurrence extracted by an agent from an exact domination dynamic program.
Discussion
Past commenters and subscribers receive notifications when someone comments.