cp's OEIS Frontend

A357501 Length of longest induced cycle in the n X n king graph.

%I A357501 #24 Mar 03 2023 20:24:19
%S A357501 0,3,4,8,12,16,24,31,38,47,60,71,82,95,112,127,142
%N A357501 Length of longest induced cycle in the n X n king graph.
%C A357501 The largest number of nodes of an induced path (instead of cycle) in the n X n king graph is A000982(n) = ceiling(n^2/2) (Beluhov 2023). - _Pontus von Brömssen_, Jan 30 2023
%D A357501 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 A357501 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 A357501 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>.
%H A357501 Wikipedia, <a href="https://en.wikipedia.org/wiki/Induced_path">Induced path</a>
%F A357501 From _Pontus von Brömssen_, Jan 30 2023: (Start)
%F A357501 Beluhov (2023) proves that
%F A357501   a(n) = n^2/2-1 if n == 0 (mod 4) and n >= 8;
%F A357501   a(n) = (n^2-1)/2 if n == 3 (mod 4);
%F A357501 and says that experimental data suggests that perhaps
%F A357501   a(n) = (n^2-5)/2 if n == 1 (mod 4) and n >= 13;
%F A357501   a(n) = n^2/2-3 if n == 2 (mod 4) and n >= 14.
%F A357501 (End)
%e A357501 Longest induced cycles for 6 <= n <= 8:
%e A357501   . X X X X .   . X X X X X .   . X X X X X X .
%e A357501   X . . . . X   X . . . . . X   X . . . . . . X
%e A357501   X . . . . X   X . . X . . X   X . . X X . . X
%e A357501   X . . . . X   X . X . X . X   X . X . . X . X
%e A357501   X . . . . X   X . X . X . X   X . . X . X . X
%e A357501   . X X X X .   X . X . X . X   X . . X . X . X
%e A357501                 . X . . . X .   X . . X . X . X
%e A357501                                 . X X . . . X .
%Y A357501 Cf. A000982, A165143, A357357, A361171.
%K A357501 nonn,more
%O A357501 1,2
%A A357501 _Pontus von Brömssen_, Oct 01 2022
%E A357501 a(9)-a(17) from _Andrew Howroyd_, Mar 03 2023