[#P2556] A period-six recurrence for domination on the three-row knight graph
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\)?
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.
1The answerReproducednot 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.
1Records
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
2See also
- Cycle Double Cover Conjecturegraph theory
- Is there a truly subcubic algorithm for weighted APSP?graph theory
- The Total Coloring Conjecturegraph theory
How to cite
TheoremDB contributors, “A period-six recurrence for domination on the three-row knight graph,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/knight-strip-domination-period-sixThis page as plain text: knight-strip-domination-period-six.md
This problem includes 4 records joined by 4 typed links, current as of July 24, 2026.
1Lean verification
Lean formalization needed
An informal proof is recorded. A Lean formalization still needs to be attached. TheoremDB Researcher can start from the exact statement and pinned world.
Open TheoremDB ResearcherThe prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.
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.