login
Maximum k for which the grid graph P_3 X P_k is a subgraph of the n X n knight graph.
3

%I #16 Feb 16 2022 04:11:45

%S 1,1,3,5,9,12,16,20,27,33,39,48

%N Maximum k for which the grid graph P_3 X P_k is a subgraph of the n X n knight graph.

%C a(15) >= 55.

%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-knightgrid3.w">CWEB program</a>

%e a(6) = 5 because of the following embedding of P3 X P5 into N6:

%e - - 3 - 1 -

%e - - 1 3 - - where the vertices of P3 X P5 are

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

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

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

%e - - - 4 - -

%Y Cf. A351392 (considers induced subgraphs), A351388 (considers P2 X Pk), A351390 (considers P4 X Pk).

%K nonn,more

%O 3,3

%A _Don Knuth_, Feb 10 2022