A357358 -id:A357358 - cp's OEIS frontend

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

Pontus von Brömssen, Sep 25 2022

			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

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.

Main diagonal of A360915.

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

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

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

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

A357359 Maximum number of nodes in an induced path (or chordless path or snake path) in the n X n torus grid graph.

Original entry on oeis.org

5, 8, 14, 21, 28, 39, 50

Offset: 3

Pontus von Brömssen, Sep 25 2022

It is somewhat unclear how a(n) should be defined for n <= 2. If the 1 X 1 and 2 X 2 torus grid graphs are considered to have loops and multiple edges, respectively, we have a(1) = 0 and a(2) = 1 (unless loops and multiple edges are allowed in a path), otherwise a(1) = 1 and a(2) = 3.

			Longest induced paths (with one end in the lower left corner) for 3 <= n <= 7:
  . 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 .

Wikipedia, Induced path.

Cf. A331968, A357234, A357358.

a(n) ~ 2*n^2/3.
a(n) <= (2*n^2-1)/3.
a(n) >= A357358(n) - 1.
a(n) >= A331968(n-1).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions