A351393 Maximum k for which the grid graph P_4 X P_k is an induced subgraph of the n X n knight graph.

1, 1, 2, 4, 4, 5, 6, 8, 8, 10, 12, 12, 14, 15, 17, 18, 20, 20, 22, 24, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44

Offset

3,3

Links

Table of n, a(n) for n=3..36.

Donald E Knuth, The Art of Computer Programming, exercises on "knight grids" in Section 7.2.2.3 (preliminary draft)

Don Knuth, CWEB program

Example

a(6) = 4 because of the following strict embedding of P4 X P4 into N6:
- - 1 - 3 -
1 - 3 - - -  where the vertices of P4 X P4 are
- - 1 2 3 4    1 2 3 4
1 2 3 4 - -    1 2 3 4
- - - 2 - 4    1 2 3 4
- 2 - 4 - -    1 2 3 4

Crossrefs

Cf. A351390 (considers not-necessarily-induced subgraphs), A351391 (considers P2 X Pk), A351392 (considers P3 X Pk).

Sequence in context: A308629 A100921 A140201 * A057861 A133143 A085898

Adjacent sequences: A351390 A351391 A351392 * A351394 A351395 A351396

Keyword

nonn,more

Author

Don Knuth, Feb 10 2022

Status

approved