A331968 -id:A331968 - cp's OEIS frontend

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

0, 4, 8, 12, 16, 20, 32, 40, 50, 62, 76, 90, 104, 120, 140, 160, 180

Offset: 1

Pontus von Brömssen, Sep 25 2022

			For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
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   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.
Elijah Beregovsky, Illustration of initial terms.
Eric Weisstein's World of Mathematics, Grid Graph.
Wikipedia, Induced path.

Main diagonal of A360915.

Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).

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

a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

a(9)-a(12) from Elijah Beregovsky, Nov 24 2022
a(13) from Elijah Beregovsky, Nov 25 2022
a(14)-a(17) from Andrew Howroyd, Feb 26 2023

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Original entry on oeis.org

1, 4, 8, 84, 56, 136, 52, 216, 16, 1504, 2352, 1152, 1344, 123216, 82432, 11008, 308992

Offset: 1

Alain Goupil, Feb 03 2020

The maximum possible number of unit squares is given by A331968(n).
Equivalently, a(n) is the number of maximum length paths without chords in the n X n grid graph. A path without chords is an induced subgraph that is a path.
For n > 1, a(n) is a multiple of 4 since a solution can have at most one symmetry considering rotations and reflections. - Andrew Howroyd, Feb 04 2020

			For n = 4 the number of snake-like polyominoes with 11 cells is 84.

Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360916.
Cf. A331968, A059525 (connected induced subgraphs), A099155.
Cf. A332920 (non-isomorphic snakes), A332921 (symmetric snakes).

a(15) from Andrew Howroyd, Feb 04 2020

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

A357234 a(n) is the maximum length of a snake-like polyomino in an n X n square that starts and ends at opposite corners.

Original entry on oeis.org

1, 3, 5, 7, 17, 23, 31, 39, 51, 63, 75, 89, 105, 121, 139, 159

Offset: 1

Yi Yang, Sep 18 2022

Snake-like polyominoes have all cells with at most two neighbor cells, and have at least one cell that has only one neighbor cell, where neighbors are horizontal or vertical (not diagonal).

Lower bounds for a(10)-a(22) are 63, 75, 89, 105, 121, 139, 159, 179, 201, 225, 249, 275, 303. Is it true that a(n) = round((2*n*n-4*n+28)/3) for n >= 9?

			Longest snakes for 5 <= 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

Cf. A331968, A357516.

a(n) ~ 2*n^2/3. - Pontus von Brömssen, Sep 19 2022

a(n) <= A331968(n). - Pontus von Brömssen, Sep 21 2022

a(1)-a(9) confirmed by Pontus von Brömssen, Sep 21 2022. - N. J. A. Sloane, Sep 30 2022
a(10)-a(13) confirmed by Elijah Beregovsky, Nov 27 2022
a(14)-a(16) from Andrew Howroyd, Feb 28 2023

A360917 Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 6, 8, 9, 9, 8, 6, 7, 9, 11, 11, 11, 9, 7, 8, 11, 14, 14, 14, 14, 11, 8, 9, 12, 16, 17, 17, 17, 16, 12, 9, 10, 14, 18, 20, 21, 21, 20, 18, 14, 10, 11, 15, 20, 22, 24, 24, 24, 22, 20, 15, 11, 12, 17, 22, 25, 27, 29, 29, 27, 25, 22, 17, 12

Offset: 1

Andrew Howroyd, Feb 26 2023

Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.

			Array begins:
==============================================
  m\n|  1  2  3  4  5  6  7  8  9 10 11 12 ...
-----+----------------------------------------
   1 |  1  2  3  4  5  6  7  8  9 10 11 12 ...
   2 |  2  3  5  6  8  9 11 12 14 15 17 18 ...
   3 |  3  5  7  9 11 14 16 18 20 22 24 26 ...
   4 |  4  6  9 11 14 17 20 22 25 28 30 33 ...
   5 |  5  8 11 14 17 21 24 27 30 34 37 40 ...
   6 |  6  9 14 17 21 24 29 32 36 40 44 47 ...
   7 |  7 11 16 20 24 29 33 38 42 46 50 55 ...
   8 |  8 12 18 22 27 32 38 42 48 52 57 62 ...
   9 |  9 14 20 25 30 36 42 48 53 58 64 70 ...
  10 | 10 15 22 28 34 40 46 52 58 64 71 77 ...
  11 | 11 17 24 30 37 44 50 57 64 71 77 86 ...
  12 | 12 18 26 33 40 47 55 62 70 77 86 92 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
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 A331968.

Cf. A360199, A360915, A360916 (maximum induced paths), 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

A332920 Number of non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.

Original entry on oeis.org

1, 1, 2, 12, 8, 17, 8, 27, 3, 188

Offset: 1

Hugo Pfoertner, Mar 05 2020

Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.

			a(4) = 12 (L = A331968(4) = 11):
  A332921(4) = 3 symmetric snakes
  . X O .     . X O O     . X O O     X . X O     X . X .     X . X O
  X . O O     X . . O     X . . 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 O     O O O O     O O O .
.
  X . X O     X . X .     X . X O     . X O .     . O O O     . O O O
  O . . O     O . O O     O O . O     X . O O     . X . O     . X . O
  O O . O     O O . O     . O . O     O . . O     X . . O     X . O O
  . O O O     . O O O     . O O O     O O O O     O O O O     O O O .
.
a(5) = 8 (L = 17)
  A332921(5) = 2 symmetric snakes
  O O O O X       O O O O O       O O O O O       X . O O X
  O . . . .       O . . . O       O . . . O       O . O . .
  O O O O O       O O . O O       O O X . O       O . O O O
  . . . . O       . O . O .       . . . . O       O . . . O
  X O O O O       X O . O X       X O O O O       O O O O O
.
  O O O O .       O O O O O       X . O O X       O O O O .
  O . . O O       O . . . O       O . O . .       O . . O O
  O O X . O       O O X . O       O . O O O       O O X . O
  . . . . O       . . . O O       O O . . O       . . . O O
  X O O O O       X O O O .       . O O O O       X O O O .

Cf. A331968 (maximum length), A331986 (counts including isomorphisms), A332921 (subset of symmetric snakes).

A332921 Number of symmetric non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.

Original entry on oeis.org

1, 1, 2, 3, 2, 0, 3, 0, 2, 0

Offset: 1

Hugo Pfoertner, Mar 05 2020

Polyominoes only differing by any combination of translation, rotation and reflection are counted only once.

			a(1) = 1 (L = A331968(1) = 1):
  X
.
a(2) = 1 (L = 3):
  X O
  . X
.
a(3) = 2 (L = 7):
  X O O    . X O
  . . O    X . O
  X O O    O O O
.
a(4) = 3 (L = 11)
  . X O .     . X O O     . X O O
  X . O O     X . . O     X . . O
  O O . O     O . . O     O . O O
  . O O O     O O O O     O O O .
.
a(5) = 2 (L = 17)
  O O O O X      O O O O O
  O . . . .      O . . . O
  O O O O O      O O . O O
  . . . . O      . O . O .
  X O O O O      X O . O X
.
a(7) = 3 (L = 33)
  O O O . O O O     O O X . 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
  O O . . . O O     . O . O . O .     . O O . O O .
  . O O . O O .     O O . O . O O     X . O . O . x
  X . O . O . X     O . O O . . O     O . O . O . O
  O O O . O O O     O O O . X O O     O O O . O O O
.
a(9) = 2 (L = 53)
  . O X . O O O O O    O O X . 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 . . .
  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
  O . . . O O . O O    O . . . O O . . O
  O O O O O . X O .    O O O O O . X O O
.
Example for a(9) corrected by _Luke Murphy_, Oct 14 2024

Cf. A331968, A331986, A332920.

A360200 Number of induced paths in the n X n grid graph.

Original entry on oeis.org

0, 8, 94, 1004, 14864, 334536, 11546874, 629381852, 56094263348, 8343512638896, 2074276200162230, 853966325494701152, 578432462293854136504, 646135466408339553958096, 1200595044818176185884236342

Offset: 1

Andrew Howroyd, Jan 29 2023

Paths of length zero are not counted here.

Equivalently, a(n) is the number of snake-like polyominoes in an n X n square. Rotations, reflections and translations are counted separately.

			The a(2) = 8 induced paths are:
  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
Wikipedia, Induced path

Main diagonal of A360199.

Cf. A059525, A297664 (induced cycles), A331968, A331986 (of maximum length), A357516.

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

Original entry on oeis.org

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

Offset: 3

Pontus von Brömssen, Sep 25 2022

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.

			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 .

Wikipedia, Induced path.

Cf. A331968, A357234, A357358.

a(n) ~ 2*n^2/3.
a(n) <= (2*n^2-1)/3.
a(n) >= A357358(n) - 1.
a(n) >= A331968(n-1).

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

A357500 Largest number of nodes of an induced path in the n X n knight graph.

Original entry on oeis.org

1, 1, 7, 9, 15, 21, 24, 34

Offset: 1

Pontus von Brömssen, Oct 01 2022

			Longest paths 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 . .

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.
Eric Weisstein's World of Mathematics, Knight Graph.
Wikipedia, Induced path

Cf. A165143, A331968.

a(n) >= A165143(n) - 1 for n >= 3.
a(n) <= (4*(n^2+3*n-2)-1)/7 for n >= 4. - Elijah Beregovsky, Dec 22 2022
a(n) = n^2/2 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A331986 Number of snake-like polyominoes with the maximum possible number of unit squares in an n X n square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A357234 a(n) is the maximum length of a snake-like polyomino in an n X n square that starts and ends at opposite corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A360917 Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A332920 Number of non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

A332921 Number of symmetric non-isomorphic free unrooted snake-shaped polyominoes of maximum length on a quadratic board of n X n squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

A360200 Number of induced paths in the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A357500 Largest number of nodes of an induced path in the n X n knight graph.

Views

Author