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