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

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,2

Comments

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)

Eric Weisstein's World of Mathematics, Grid Graph.

Formula

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

Example

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

Crossrefs

Main diagonal is A360847.

Rows 1..2 are A113311(n-1), A360848.

Cf. A291872 (connected dominating sets), A360202 (induced trees).

Sequence in context: A049927 A329216 A266616 * A340429 A147679 A339054

Adjacent sequences: A360843 A360844 A360845 * A360847 A360848 A360849

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 23 2023

Status

approved