A357359 - OEIS

A357359

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

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

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

OFFSET

3,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=3..9.

Wikipedia, Induced path.

FORMULA

a(n) ~ 2*n^2/3.

a(n) <= (2*n^2-1)/3.

a(n) >= A357358(n) - 1.

a(n) >= A331968(n-1).

EXAMPLE

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