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

Author

Pontus von Brömssen, Sep 25 2022

Keywords

• nonn
• more

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.

Examples

			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 .
		

Links

• Wikipedia, Induced path.

Crossrefs

Cf. A331968, A357234, A357358.

Formula

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

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

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

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