%I #23 Jan 31 2023 01:13:15

%S 1,1,7,9,15,21,24,34

%N Largest number of nodes of an induced path in the n X n knight graph.

%D Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.

%D Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.

%H Nikolai Beluhov, <a href="https://arxiv.org/abs/2301.01152">Snake paths in king and knight graphs</a>, arXiv:2301.01152 [math.CO], 2023.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Induced_path">Induced path</a>

%F a(n) >= A165143(n) - 1 for n >= 3.

%F a(n) <= (4*(n^2+3*n-2)-1)/7 for n >= 4. - _Elijah Beregovsky_, Dec 22 2022

%F a(n) = n^2/2 + O(n) (Beluhov 2023). - _Pontus von Brömssen_, Jan 30 2023

%e Longest paths for 3 <= n <= 7:

%e X . X . . . . . X . X . . X X X . . X . X X X . .

%e X . X X . X X X X . X X X . . X X X X . X . . X .

%e X X X . X X . X . . . X X . . . X X . X X . . X .

%e X X X X X X . X X X X . . . X . . X . . X X

%e . X X X . . X X . X X . . . . . . X

%e . X X X X . . X X X X X X

%e X X . X X . .

%Y Cf. A165143, A331968.

%K nonn,more

%O 1,3

%A _Pontus von Brömssen_, Oct 01 2022