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

Author

Pontus von Brömssen, Sep 25 2022

Keywords

• nonn
• more

Examples

			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
		

Links

• 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.

Crossrefs

Main diagonal of A360915.

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

Formula

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

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

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