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

- ID: `P2556`
- Reference: `knight-strip-domination-period-six`
- Page: https://theoremdb.org/statements/P2556
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Problem setup

- **Definition.** A dominating set D has the property that each vertex lies in D or has a neighbor in D.
- **Remark.** Board rows are 0,1,2 and columns are 1,...,n. Knight moves have coordinate differences (1,2) or (2,1).

### What 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.

## The answer

The exact values satisfy gamma(n+6)=gamma(n)+4 for every n at least 9.

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### 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.

## Work

### Proof and evidence for the resolution

**Computation 1 (The period-six recurrence holds from n=9).** The exact values satisfy gamma(n+6)=gamma(n)+4 for every n at least 9.

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.

### Background and intake notes

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.

- Original intake status: Status unknown. No literature search was performed. Domination numbers of chessboard strip graphs may contain this case.
- The transfer state consists of selected and dominated 3-bit masks in the last two columns, so there are at most 4096 boundary states.
- A proof can export the reachable min-plus transfer graph and certify its transient and critical cycles. Equality of the relevant matrix powers after the transient makes the infinite recurrence a finite certificate.

- Recorded example: gamma(1),...,gamma(8)=3,4,4,4,4,4,6,8.

### Supporting results

- **Computation 2** (reproduced): The reachable min-plus cost vector obeys f_25=f_19+4, and transfer homogeneity propagates that identity forever.

### Prior approaches

- **Route 1** (supported): The search found work on square covers, efficient domination, and perfect domination, with no exact ordinary three-row formula located. [1](#reference-1) [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): Inline Python builds the full transfer, checks exact values through width 25, and verifies the vector identity that proves the infinite recurrence.

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `knight-strip-domination-period-six`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20knight-strip-domination-period-six%0A%0AExact%20title%3A%20A%20period-six%20recurrence%20for%20domination%20on%20the%20three-row%20knight%20graph%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Fknight-strip-domination-period-six%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>Todd Fenstermacher, Soumendra Ganguly, and Renu Laskar, “Perfect Domination in Knights Graphs”. arXiv:1805.03335 (2018). 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 https://arxiv.org/abs/1805.03335
   - preprint; reference source; arXiv:1805.03335, version checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - 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. <a id="reference-2"></a>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 https://combinatorialpress.com/ars-articles/volume-069-ars-articles/on-the-n-times-n-knight-cover-problem/
   - journal_article; primary source; publisher version of record; checked 2026-07-28
   - Source 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.