login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #17 Feb 15 2022 02:42:54

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

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

%C a(18) >= 61.

%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 Donald Knuth, <a href="http://cs.stanford.edu/~knuth/programs/back-knightgrid4.w">CWEB program</a>

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

%e - - - 1 - -

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

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

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

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

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

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

%K nonn,more

%O 3,3

%A _Don Knuth_, Feb 10 2022