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

%I #13 Feb 15 2022 08:11:16

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

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

%H Donald E Knuth, <a href="http://cs.stanford.edu/~knuth/fasc7a.ps.gz">The Art of Computer Programming, exercises on "knight grids" in Section 7.2.2.3</a> (preliminary draft)

%H Don Knuth <a href="http://cs.stanford.edu/~knuth/programs/back-knightgrid2-strict.w">CWEB program</a>

%e a(5) = 5 because of the following strict embedding of P2 X P5 into N5:

%e - - 1 - -

%e 1 - 4 - 2 where the vertices of P2 X P5 are

%e 4 - 2 - 5 1 2 3 4 5

%e - - 5 3 - 1 2 3 4 5

%e - 3 - - -

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

%K nonn,more

%O 3,2

%A _Don Knuth_, Feb 10 2022