A357357 - OEIS

%I #38 Feb 27 2023 11:15:49

%S 0,4,8,12,16,20,32,40,50,62,76,90,104,120,140,160,180

%N Length of the longest induced cycle in the n X n grid graph.

%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 Elijah Beregovsky, <a href="/A357357/a357357.png">Illustration of initial terms</a>.

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

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

%F a(n) <= A331968(n)+1.

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

%e For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).

%e Longest induced cycles for 6 <= n <= 8:

%e   X X X X X X   X X X X X X X   X X X X X X X X

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

%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

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

%e                                 X X X . X X X X

%Y Main diagonal of A360915.

%Y Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).

%K nonn,more

%O 1,2

%A _Pontus von Brömssen_, Sep 25 2022

%E a(9)-a(12) from _Elijah Beregovsky_, Nov 24 2022

%E a(13) from _Elijah Beregovsky_, Nov 25 2022

%E a(14)-a(17) from _Andrew Howroyd_, Feb 26 2023