A302488 -id:A302488 - cp's OEIS frontend

A300358 Array read by antidiagonals: T(m,n) = total domination number of the grid graph P_m X P_n.

1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4, 3, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 5, 4, 4, 4, 6, 6, 8, 8, 6, 6, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 6, 6, 8, 10, 10, 10, 10, 8, 6, 6, 6, 8, 9, 12, 12, 12, 12, 12, 9, 8, 6, 6, 8, 10, 12, 14, 14, 14, 14, 12, 10, 8, 6, 7, 8, 11, 14, 15, 16, 15, 16, 15, 14, 11, 8, 7

Offset: 1

Andrew Howroyd, Apr 20 2018

			Table begins:
=======================================================
m\n| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
---+---------------------------------------------------
1  | 1  2  2  2  3  4  4  4  5  6  6  6  7  8  8  8 ...
2  | 2  2  2  4  4  4  6  6  6  8  8  8 10 10 10 12 ...
3  | 2  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
4  | 2  4  4  6  8  8 10 12 12 14 14 16 18 18 20 20 ...
5  | 3  4  5  8  9 10 12 14 15 16 18 20 21 22 24 26 ...
6  | 4  4  6  8 10 12 14 16 18 20 20 24 24 26 28 30 ...
7  | 4  6  7 10 12 14 15 18 20 22 24 26 27 30 32 34 ...
8  | 4  6  8 12 14 16 18 20 22 24 28 30 32 34 36 38 ...
9  | 5  6  9 12 15 18 20 22 25 28 30 32 35 38 40 42 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Alexandre Talon, Intensive use of computing resources for dominations in grids and other combinatorial problems, arXiv:2002.11615 [cs.DM], 2020. See Sec. 2.3.2.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Total Domination Number

Rows 1..2 are A004524(n+2), A302402.
Main diagonal is A302488.
Cf. A303111, A303118, A303293.

A369692 Connected domination number of the n X n grid graph.

Original entry on oeis.org

1, 2, 3, 7, 11, 14, 20, 26, 30, 39, 47, 52, 64, 74, 80, 95

Offset: 1

Alexander D. Healy, Feb 25 2024

			From _Andrew Howroyd_, Mar 06 2024: (Start)
a(16) = 95 = 16 + 5*14 + 4*2 + 1.
  . . . . . . . . . . . . . . . .
  X X X X X X X X X X X X X X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X X
  . X . . X . . X . . X . . X . .
  . X . . X . . X . . X . . X X .
(End)

Alexander D. Healy, Examples of (near-)optimal dominating sets for n <= 12
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Cf. A104519, A287690, A302488, A370428.

Cf. A381730 (numbers of minimum connected dominating sets).

a(3*n) <= n*(3*n+1); a(3*n-1) <= 3*n^2 - 1; a(3*n-2) <= (n-1)*(3*n+1). Conjecturally these inequalities hold with equality for n > 1. - Andrew Howroyd, Mar 06 2024

a(10)-a(16) from Andrew Howroyd, Feb 25 2024

A303142 Number of minimum total dominating sets in the n X n grid graph.

Original entry on oeis.org

0, 4, 2, 16, 160, 144, 4, 256, 1364, 484, 6, 784, 5032, 1444, 8, 2116, 12972, 3364, 10, 4624, 27376, 6724, 12, 8836, 50820, 12100, 14, 15376, 86264, 20164

Offset: 1

Eric W. Weisstein, Apr 19 2018

Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.

Main diagonal of A303293.

Cf. A133793, A302488, A303161.

a(6)-a(30) from Andrew Howroyd, Apr 22 2018

A157522 Triangle T(n, k) = f(n, k) + f(n, n-k) - 1, where f(n, k) = k if k <= floor(n/4), floor(n/2) - k if floor(n/4) < k <= floor(n/2), k - floor(n/2) if floor(n/2) < k <= floor(3*n/4), otherwise n-k, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 1, 3, 1, 1, 3, 2, 2, 3, 1, 1, 3, 3, 1, 3, 3, 1, 1, 3, 4, 2, 2, 4, 3, 1, 1, 3, 5, 3, 1, 3, 5, 3, 1, 1, 3, 5, 4, 2, 2, 4, 5, 3, 1, 1, 3, 5, 5, 3, 1, 3, 5, 5, 3, 1, 1, 3, 5, 6, 4, 2, 2, 4, 6, 5, 3, 1, 1, 3, 5, 7, 5, 3, 1, 3, 5, 7, 5, 3, 1, 1, 3, 5, 7, 6, 4, 2, 2, 4, 6, 7, 5, 3, 1

Offset: 0

Roger L. Bagula, Mar 02 2009

			Triangle begins as:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 2, 1;
  1, 3, 1, 3, 1;
  1, 3, 2, 2, 3, 1;
  1, 3, 3, 1, 3, 3, 1;
  1, 3, 4, 2, 2, 4, 3, 1;
  1, 3, 5, 3, 1, 3, 5, 3, 1;
  1, 3, 5, 4, 2, 2, 4, 5, 3, 1;
  1, 3, 5, 5, 3, 1, 3, 5, 5, 3, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A157523.

f[n_, k_]= 1 +If[k<=Floor[n/4], k, If[Floor[n/4]G. C. Greubel, Jan 22 2022 *)

def f(n, k):
    if (k <= (n//4)): return k+1
    elif ((n//4) < k <= (n//2)): return (n//2)-k+1
    elif ((n//2) < k <= (3*n//4)): return k+1-(n//2)
    else: return n-k+1
def T(n,k): return f(n,k) + f(n,n-k) - 1
flatten([[T(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jan 22 2022

T(n, k) = f(n, k) + f(n, n-k) - 1, where f(n, k) = k if k <= floor(n/4), floor(n/2) - k if floor(n/4) < k <= floor(n/2), k - floor(n/2) if floor(n/2) < k <= floor(3*n/4), otherwise n-k.
From G. C. Greubel, Jan 22 2022: (Start)
T(n, n-k) = T(n, k).
T(2*n, n) = 1.
T(2*n+1, n) = A040000(n).
Sum_{k=0..n} T(n, k) = A302488(n). (End)

Edited by N. J. A. Sloane, Mar 05 2009

cp's OEIS Frontend

A300358 Array read by antidiagonals: T(m,n) = total domination number of the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A369692 Connected domination number of the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A303142 Number of minimum total dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A157522 Triangle T(n, k) = f(n, k) + f(n, n-k) - 1, where f(n, k) = k if k <= floor(n/4), floor(n/2) - k if floor(n/4) < k <= floor(n/2), k - floor(n/2) if floor(n/2) < k <= floor(3*n/4), otherwise n-k, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions