A360920 -id:A360920 - cp's OEIS frontend

A360918 Array read by antidiagonals: T(m,n) is the number of maximum induced trees in the grid graph P_m X P_n.

1, 1, 1, 1, 4, 1, 1, 2, 2, 1, 1, 10, 10, 10, 1, 1, 4, 26, 26, 4, 1, 1, 24, 2, 32, 2, 24, 1, 1, 8, 10, 50, 50, 10, 8, 1, 1, 56, 50, 56, 22, 56, 50, 56, 1, 1, 16, 194, 64, 608, 608, 64, 194, 16, 1, 1, 128, 4, 72, 182, 4120, 182, 72, 4, 128, 1, 1, 32, 32, 80, 16, 208, 208, 16, 80, 32, 32, 1

Offset: 1

Andrew Howroyd, Feb 26 2023

A maximum induced tree is an induced tree of greatest size.

			Array begins:
===============================================
m\n| 1  2   3  4   5     6    7     8     9 ...
---+-------------------------------------------
1  | 1  1   1  1   1     1    1     1     1 ...
2  | 1  4   2 10   4    24    8    56    16 ...
3  | 1  2  10 26   2    10   50   194     4 ...
4  | 1 10  26 32  50    56   64    72    80 ...
5  | 1  4   2 50  22   608  182    16     2 ...
6  | 1 24  10 56 608  4120  208  1968 22716 ...
7  | 1  8  50 64 182   208  488   560  1050 ...
8  | 1 56 194 72  16  1968  560 65864 14340 ...
9  | 1 16   4 80   2 22716 1050 14340   166 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal is A360919.

Cf. A360202, A360847, A360913, A360916, A360920 (maximum sizes).

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

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

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

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

A360918 Array read by antidiagonals: T(m,n) is the number of maximum induced trees in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula