A357357 -id:A357357 - cp's OEIS frontend

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182

Offset: 1

Alain Goupil, Feb 02 2020

These are similar to the snake-in-the-box problem for the hypercube Q_n (See A099155).
The number of solutions is given by A331986(n).
Equivalently, a(n) is the maximum number of vertices in a path without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
These numbers are part of the result of a computer program that counts the snake-like polyominoes in a rectangle of given size b X h by their length.
a(16) >= 161.

			For n=4, the maximum length of a snake-like polyomino that fits in a square of side 4 is 11 and there are 84 such snakes.
Maximum-length snakes for n = 1 to 4 are shown below.
   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.
Alain Goupil, Illustration of initial terms
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360917.

Cf. A099155, A047838, A122224, A331986, A332920, A332921, A357357, A357359.

a(n) >= A047838(n+1).
For n > 2: a(n) >= 2*floor(n/3)*(2n-3*floor(n/3)-2)+5. - Elijah Beregovsky, May 11 2020
a(n) <= (2*n*(n+1)-1)/3. - Elijah Beregovsky, Nov 09 2020
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(15) from Andrew Howroyd, Feb 04 2020

a(16)-a(17) from Yi Yang, Oct 03 2022

A360915 Array read by antidiagonals: T(m,n) is the length of the longest induced cycle in the grid graph P_m X P_n.

Original entry on oeis.org

4, 4, 4, 4, 8, 4, 4, 10, 10, 4, 4, 12, 12, 12, 4, 4, 14, 14, 14, 14, 4, 4, 16, 16, 16, 16, 16, 4, 4, 18, 20, 18, 18, 20, 18, 4, 4, 20, 22, 24, 20, 24, 22, 20, 4, 4, 22, 24, 26, 28, 28, 26, 24, 22, 4, 4, 24, 28, 28, 30, 32, 30, 28, 28, 24, 4, 4, 26, 30, 32, 32, 36, 36, 32, 32, 30, 26, 4

Offset: 2

Andrew Howroyd, Feb 26 2023

All terms are even since the grid graph is bipartite.

			Array begins:
==========================================
  m\n| 2  3  4  5  6  7  8  9 10 11 12 ...
-----+------------------------------------
   2 | 4  4  4  4  4  4  4  4  4  4  4 ...
   3 | 4  8 10 12 14 16 18 20 22 24 26 ...
   4 | 4 10 12 14 16 20 22 24 28 30 32 ...
   5 | 4 12 14 16 18 24 26 28 32 36 38 ...
   6 | 4 14 16 18 20 28 30 32 36 42 44 ...
   7 | 4 16 20 24 28 32 36 40 44 48 52 ...
   8 | 4 18 22 26 30 36 40 46 50 56 60 ...
   9 | 4 20 24 28 32 40 46 50 56 62 68 ...
  10 | 4 22 28 32 36 44 50 56 62 70 74 ...
  11 | 4 24 30 36 42 48 56 62 70 76 82 ...
  12 | 4 26 32 38 44 52 60 68 74 82 90 ...
  ...

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal is A357357.

Cf. A360196, A360913, A360917, A360920.

T(m,n) = T(n,m).

T(m,n) = 2*m*n/3 + O(m+n) (Beluhov 2023, Proposition 3). - Pontus von Brömssen, May 08 2023

A357501 Length of longest induced cycle in the n X n king graph.

Original entry on oeis.org

0, 3, 4, 8, 12, 16, 24, 31, 38, 47, 60, 71, 82, 95, 112, 127, 142

Offset: 1

Pontus von Brömssen, Oct 01 2022

The largest number of nodes of an induced path (instead of cycle) in the n X n king graph is A000982(n) = ceiling(n^2/2) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

			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 .

Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Eric Weisstein's World of Mathematics, King Graph.
Wikipedia, Induced path

Cf. A000982, A165143, A357357, A361171.

From Pontus von Brömssen, Jan 30 2023: (Start)
Beluhov (2023) proves that
  a(n) = n^2/2-1 if n == 0 (mod 4) and n >= 8;
  a(n) = (n^2-1)/2 if n == 3 (mod 4);
and says that experimental data suggests that perhaps
  a(n) = (n^2-5)/2 if n == 1 (mod 4) and n >= 13;
  a(n) = n^2/2-3 if n == 2 (mod 4) and n >= 14.
(End)

a(9)-a(17) from Andrew Howroyd, Mar 03 2023

A360914 Number of maximum induced cycles in the n X n grid graph.

Original entry on oeis.org

0, 1, 1, 7, 90, 1398, 23, 2100, 6840, 2912, 416, 1344, 102198, 1643968, 42592, 48128, 1120128

Offset: 1

Andrew Howroyd, Feb 26 2023

A maximum induced cycle is an induced cycle of longest length.

			The a(3) = 1 unique cycle of longest length is:
   O O O
   O   O
   O O O
.
The a(4) = 7 maximum induced cycles have length 12 and are the following subgraphs with their rotations and reflections.
   O O O O     O O O     O O O
   O     O   O O   O   O O   O
   O     O   O     O   O   O O
   O O O O   O O O O   O O O

Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal of A360913.

Cf. A297664, A357357 (lengths).

A165143 Length of longest cyclic knight path on an n X n chessboard that is determined (up to starting point and direction) by the fields visited.

Original entry on oeis.org

8, 10, 16, 20, 22, 32, 40, 48

Offset: 3

Hagen von Eitzen, Sep 05 2009

More mathematically, a(n) is also the biggest possible number of vertices (or edges) of a circular graph in the plane with all vertices being distinct and having integer coordinates between 1 and n, inclusive, and all edges having length sqrt(5).
Opinions on a(1) and a(2) may differ: The only possible circular path consists of staying at the starting field, hence we have 1 field visited (thus a(1) = a(2) = 1) or it takes 0 knight moves to complete the tour (thus a(1) = a(2) = 0). The graph with one vertex and no edges is not considered a cyclic graph since all vertices must have degree two; even adding a loop edge would produce an edge of length 0 (thus a(1) and a(2) are either undefined or = 0 if one accepts the empty graph as cyclic).
Put another way, a(n) is the length of a longest induced cycle in the n X n knight graph. - Pontus von Brömssen, Oct 02 2022

			The eight non-center fields of a 3 X 3 chessboard can be visited cyclically in a unique manner up to selection of starting point and clockwise vs. counterclockwise direction; since the center field cannot be part of a (longer) cycle, we have a(3) = 8.

Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.
Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.

Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
Sequence mentioned in the related Solution to problem #12, Missoury State Math Dept. Challenge Problem Archive, 2007/08.

Cf. A297666, A357357, A357500, A357501.

From Pontus von Brömssen, Jan 30 2023: (Start)
a(n) = n^2/2 + O(n) (Beluhov 2023).
a(n) <= A357500(n)+1.
(End)

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

Original entry on oeis.org

6, 8, 15, 20, 28, 40, 48, 58, 73, 88, 104, 126

Offset: 3

Pontus von Brömssen, Sep 25 2022

It is somewhat unclear how a(2) should be defined. If the 2 X 2 torus grid graph is considered to have multiple edges we have a(2) = 2 (a double edge between two nodes makes a 2-cycle), otherwise a(2) = 4.

			Longest induced cycles for 3 <= 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 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. A000937, A297669, A357357, A357359.

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

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

a(9)-a(12) from Elijah Beregovsky, Dec 11 2022

a(13)-a(14) from Elijah Beregovsky, Dec 13 2022

A360921 Maximum number of vertices in an induced tree in the n X n grid graph.

Original entry on oeis.org

1, 3, 7, 12, 19, 26, 36, 46, 59, 72, 87, 102, 120, 138, 159

Offset: 1

Andrew Howroyd, Feb 26 2023

			a(4) = 12:
   O O O O
   O     O
   O O   O
   O   O O

Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal of A360920.

Cf. A331968, A357357, A360919 (maximum induced trees).

a(n) >= A331968(n).

cp's OEIS Frontend

A331968 Maximum number of unit squares of a snake-like polyomino in an n X n square box.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A360915 Array read by antidiagonals: T(m,n) is the length of the longest induced cycle in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A357501 Length of longest induced cycle in the n X n king graph.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A360914 Number of maximum induced cycles in the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A165143 Length of longest cyclic knight path on an n X n chessboard that is determined (up to starting point and direction) by the fields visited.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A360921 Maximum number of vertices in an induced tree in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula