# 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
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: b5a83bd9bdbf7dfdc7134c15b7360f889389e7bc
- Current Markdown: https://api.theoremdb.org/v1/statements/knight-strip-domination-period-six?representation=markdown
- Record maturity: Reviewed problem with recorded work

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

## Resolution

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

**Recorded scope.** every three-row knight graph K_n, with the recurrence asserted for every integer n at least 9

[Read this exact record and its supporting evidence](/records/ksd6-claim-exact-recurrence)


**Resolution status:** Resolved.

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

## Research packet

### 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** (computational evidence): 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** (executable material): 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. No Lean formalization is 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%0AInspect%20the%20current%20formalization%20records%20and%20verification%20history%20first.%20Continue%20an%20active%20request%2C%20draft%20check%2C%20or%20proof%20run%20when%20one%20exists%2C%20and%20avoid%20creating%20a%20duplicate%20submission.%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20needs%20work%2C%20follow%20the%20returned%20next%20step%20to%20record%20one%20Lean-shaped%20target%20draft.%20Preflight%20must%20confirm%20compilation%20before%20proof%20submission.%0A%0AChoose%20lean-proof-term-v1%20for%20a%20proof%20block%20with%20optional%20supporting_source.%20Choose%20lean-complete-file-v1%20for%20an%20existing%20complete%20file%20and%20send%20it%20unchanged%20in%20source%2C%20including%20imports.%20When%20the%20proof%20has%20local%20modules%20or%20certificate%20files%2C%20call%20createLeanProjectUpload%2C%20upload%20the%20returned%20private%20object%2C%20and%20call%20completeLeanProjectUpload.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20for%20kernel_accepted.%20Repair%20kernel%20diagnostics%20before%20submitting.%20If%20target%20correspondence%20rejects%20the%20formal%20statement%2C%20follow%20its%20repairs%20and%20check%20the%20corrected%20target%20again.%0A%0AOnce%20kernel_accepted%20is%20true%2C%20call%20submitLeanProof%20with%20that%20exact%20draft_run_id%20to%20save%20my%20submission%20request%2C%20even%20while%20target%20correspondence%20is%20pending.%20The%20saved%20request%20continues%20automatically%20after%20correspondence%20approval.%20A%20private%20check%20alone%20stays%20private.%0A%0APoll%20getLeanProofRun%20with%20the%20returned%20run_id.%20Report%20pending%20target%20review%2C%20signed%20verification%2C%20and%20packet%20attachment%20separately.%20Follow%20any%20operator-recovery%20instruction%20or%20relation-review%20handoff.%20Use%20cancelLeanProofSubmission%20only%20if%20I%20ask%20to%20withdraw%20a%20waiting%20request.).

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.

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