A351393 - OEIS

%I #10 Mar 13 2022 19:04:00

%S 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,

%T 34,35,37,38,40,41,43,44

%N Maximum k for which the grid graph P_4 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-knightgrid4-strict.w">CWEB program</a>

%e a(6) = 4 because of the following strict embedding of P4 X P4 into N6:

%e - - 1 - 3 -

%e 1 - 3 - - -  where the vertices of P4 X P4 are

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

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

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

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

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

%K nonn,more

%O 3,3

%A _Don Knuth_, Feb 10 2022