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

1, 1, 3, 4, 5, 6, 7, 10, 11, 12, 14, 16, 20, 21, 25, 28, 32, 34, 41, 44, 49, 53

Offset

3,3

Links

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

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 P3 X P4 into N6:
- - - - - -
4 - 2 - - -  where the vertices of P3 X P4 are
- - 4 - 2 -     1 2 3 4
4 3 2 1 - -     1 2 3 4
- - - 3 - 1     1 2 3 4
- 3 - 1 - -

Crossrefs

Cf. A351389 (considers not-necessarly-induced subgraphs), A351391 (considers P2 X Pk), A351393 (considers P4 X Pk).

Sequence in context: A022555 A047308 A092860 * A112874 A159973 A359772

Adjacent sequences: A351389 A351390 A351391 * A351393 A351394 A351395

Keyword

nonn,more

Author

Don Knuth, Feb 10 2022

Status

approved