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

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

Offset

1,2

Links

Table of n, a(n) for n=1..17.

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.

Elijah Beregovsky, Illustration of initial terms.

Eric Weisstein's World of Mathematics, Grid Graph.

Wikipedia, Induced path.

Formula

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

a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

Example

For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
Longest induced cycles for 6 <= n <= 8:
  X X X X X X   X X X X X X X   X X X X X X X X
  X . . . . X   X . . . . . X   X . . . . . . X
  X . . . . X   X . X X X . X   X . X X X . X X
  X . . . . X   X . X . X . X   X . X . X . X .
  X . . . . X   X . X . X . X   X . X . X . X X
  X X X X X X   X . X . X . X   X . X . X . . X
                X X X . X X X   X . X . X . . X
                                X X X . X X X X

Crossrefs

Main diagonal of A360915.

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

Sequence in context: A311236 A311237 A102861 * A311238 A311239 A311240

Adjacent sequences: A357354 A357355 A357356 * A357358 A357359 A357360

Keyword

nonn,more

Author

Pontus von Brömssen, Sep 25 2022

Extensions

a(9)-a(12) from Elijah Beregovsky, Nov 24 2022

a(13) from Elijah Beregovsky, Nov 25 2022

a(14)-a(17) from Andrew Howroyd, Feb 26 2023

Status

approved