A357359 - OEIS

%I #9 Oct 01 2022 10:25:29

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

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

%C 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.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Induced_path">Induced path</a>.

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

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

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

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

%e Longest induced paths (with one end in the lower left corner) for 3 <= n <= 7:

%e   . X X   . X X .   . X X . X   . X X . X .   . . . X . X X

%e   X X .   X X . .   . X . X X   X X . X X .   X X . X X . X

%e   X . .   X . X .   X X . X .   X . X X . X   . X X . X X .

%e           X . X .   X . X X .   . X X . X X   X . X X . X X

%e                     X . X . .   X X . . X .   X X . X . . .

%e                                 X . X . X .   . X . X . X X

%e                                               X X . X . X .

%Y Cf. A331968, A357234, A357358.

%K nonn,more

%O 3,1

%A _Pontus von Brömssen_, Sep 25 2022