TheoremDB
All problems

[#P2556] A period-six recurrence for domination on the three-row knight graph

Checking solution status

Loading the current review decision.

Checking Lean verification
A mathematical schematic of A period-six recurrence for domination on the three-row knight graph.
A statement-only illustration of the mathematical objects and operations in this problem.
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 accessWork on this problem in ChatGPT
Definitions 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.

1Resolution

What counts as a solution

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

4 records

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemA period-six recurrence for domination on the three-row knight graph

All 4 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“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
BibTeX
@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}
}

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. No Lean formalization is attached.

Open TheoremDB Researcher

Upload a Lean project archive

Once 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

  1. 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
  2. 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

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.