A351390 Maximum k for which the grid graph P_4 X P_k is a subgraph of the n X n knight graph.

1, 1, 2, 4, 5, 7, 10, 15, 18, 22, 25, 34, 37, 43, 52

Offset

3,3

Comments

a(18) >= 61.

Links

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

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

Donald Knuth, CWEB program

Example

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

Crossrefs

Cf. A351393 (considers induced subgraphs), A351388 (considers P2 X Pk), A351389 (considers P3 X Pk).

Sequence in context: A018598 A018756 A018301 * A218074 A241735 A092295

Adjacent sequences: A351387 A351388 A351389 * A351391 A351392 A351393

Keyword

nonn,more

Author

Don Knuth, Feb 10 2022

Status

approved