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

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

Cf. A331968, A357234, A357358.

Sequence in context: A314523 A325197 A314524 * A314525 A314526 A092590

Adjacent sequences: A357356 A357357 A357358 * A357360 A357361 A357362

Keyword

nonn,more

Author

Pontus von Brömssen, Sep 25 2022

Status

approved