A360847 -id:A360847 - 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).

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

Original entry on oeis.org

1, 3, 3, 4, 8, 4, 4, 17, 17, 4, 4, 32, 65, 32, 4, 4, 66, 222, 222, 66, 4, 4, 130, 766, 1280, 766, 130, 4, 4, 262, 2685, 7629, 7629, 2685, 262, 4, 4, 522, 9450, 46032, 78981, 46032, 9450, 522, 4, 4, 1046, 33158, 278419, 820308, 820308, 278419, 33158, 1046, 4

Offset: 1

Andrew Howroyd, Feb 23 2023

A dominating induced tree in a graph is an acyclic connected induced subgraph whose vertices are a dominating set.

			Table starts:
=======================================================
m\n| 1   2    3      4       5         6          7 ...
---+---------------------------------------------------
1  | 1   3    4      4       4         4          4 ...
2  | 3   8   17     32      66       130        262 ...
3  | 4  17   65    222     766      2685       9450 ...
4  | 4  32  222   1280    7629     46032     278419 ...
5  | 4  66  766   7629   78981    820308    8520021 ...
6  | 4 130 2685  46032  820308  14605388  259809527 ...
7  | 4 262 9450 278419 8520021 259809527 7904828158 ...
  ...

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

Main diagonal is A360847.
Rows 1..2 are A113311(n-1), A360848.
Cf. A291872 (connected dominating sets), A360202 (induced trees).

T(n,m) = T(m,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