A357357 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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

Eric Weisstein's World of Mathematics, Grid Graph.

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

KEYWORD

nonn,more

AUTHOR

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