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

1, 2, 5, 8, 8, 10, 12, 15, 19, 24, 28, 32, 36, 40, 46, 52

Offset

3,2

Links

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

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(5) = 5 because of the following strict embedding of P2 X P5 into N5:
- - 1 - -
1 - 4 - 2  where the vertices of P2 X P5 are
4 - 2 - 5      1 2 3 4 5
- - 5 3 -      1 2 3 4 5
- 3 - - -

Crossrefs

Cf. A351388 (considers not-necessarily-induced subgraphs), A351392 (considers P3 X Pk), A351393 (considers P4 X Pk).

Sequence in context: A284868 A019772 A356870 * A046825 A374442 A250320

Adjacent sequences: A351388 A351389 A351390 * A351392 A351393 A351394

Keyword

nonn,more

Author

Don Knuth, Feb 10 2022

Status

approved