A332401 -id:A332401 - cp's OEIS frontend

A263284 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs on n vertices with domination number k.

1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 11, 16, 5, 1, 1, 34, 94, 21, 5, 1, 1, 156, 708, 152, 21, 5, 1, 1, 1044, 9384, 1724, 166, 21, 5, 1, 1, 12346, 221135, 38996, 1997, 166, 21, 5, 1, 1, 274668, 9877969, 1800340, 49961, 2036, 166, 21, 5, 1, 1

Offset: 1

Christian Stump, Oct 13 2015

The domination number of a graph is given by the minimum size of a dominating set of vertices. A dominating set of vertices is a subset of the vertex set of such that every vertex is either in this subset or adjacent to an element of this subset.

For any graph the domination number is greater than or equal to the irredundance number (A332404) and less than or equal to the independent domination number (A332402). - Andrew Howroyd, Feb 13 2020

			Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       4,       5,       1,     1;
      11,      16,       5,     1,    1;
      34,      94,      21,     5,    1,   1;
     156,     708,     152,    21,    5,   1,  1;
    1044,    9384,    1724,   166,   21,   5,  1, 1;
   12346,  221135,   38996,  1997,  166,  21,  5, 1, 1;
  274668, 9877969, 1800340, 49961, 2036, 166, 21, 5, 1, 1;
  ...

FindStat - Combinatorial Statistic Finder, The domination number of a graph.
Eric Weisstein's World of Mathematics, Domination Number

Row sums are A000088.
Columns k=1..2 are A000088(n-1), A332625.
Cf. A263341, A332400, A332401, A332402, A332403, A332404, A332405.

T(n,k) = T(n-1,k-1) for 2*(k-1) >= n. - Andrew Howroyd, Feb 17 2020

Extended to 10 rows by Eric W. Weisstein, May 18 2017

A339833 Irregular triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with domination number k, n >= 1, 1 <= k <= A065033(n+1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 5, 5, 1, 7, 13, 2, 1, 8, 27, 11, 1, 10, 47, 45, 3, 1, 11, 72, 124, 27, 1, 13, 103, 287, 141, 6, 1, 14, 140, 553, 528, 65, 1, 16, 182, 966, 1537, 446, 11, 1, 17, 230, 1538, 3712, 2080, 163, 1, 19, 284, 2323, 7788, 7516, 1366, 23

Offset: 1

Andrew Howroyd, Dec 19 2020

A star graph has a domination number of 1 and for n > 1 a path on n nodes has domination number floor(n/2) which is the maximum possible for a connected graph.

A minimum dominating set can be found in a tree using a greedy algorithm. First choose any node to be the root and perform a depth first search from the root. Exclude all leaves from the dominating set (except possibly the root) and also greedily exclude any other node if all children are either in the dominating set or dominated by one of their children. This method can be converted into an algorithm to compute the number of trees by domination number. See the PARI program for technical details.

			Triangle begins:
  1;
  1;
  1;
  1,  1;
  1,  2;
  1,  4,  1;
  1,  5,  5;
  1,  7, 13,  2;
  1,  8, 27, 11;
  1, 10, 47, 45, 3;
  ...
There are 3 trees with 5 nodes:
    o                                     o
    |                                     |
    x---x---o    o---x---o---x---o    o---x---o
    |                                     |
    o                                     o
The first 2 of these have a minimum dominating set of 2 nodes and the last has a minimum dominating set of 1 node, so T(5,2)=2 and T(5,1)=1.

Andrew Howroyd, Table of n, a(n) for n = 1..2501 (rows 1..100)
Eric Weisstein's World of Mathematics, Domination Number
Wikipedia, Dominating set

Row sums are A000055.

Cf. A065033, A332401 (connected graphs), A339829 (independence number), A339834, A339835.

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i ))-1, -n)}
\\ In the following, u,v,w count rooted trees weighted by domination number: u is root in set, v is root not in the set but dominatated by a child, w is root in set and not yet dominated.
T(n)={my(u=[0], v=[0], w=[1]); for(n=2, n, my(t1=EulerMT(v), t2=EulerMT(u+v)); u=y*concat([0], EulerMT(u+v+w)-t2); v=concat([0], t2-t1); w=concat([1], t1)); w*=y; my(g=x*Ser(u+v+w), gu=x*Ser(u), gw=x*Ser(w), r=Vec(g + (substvec(g, [x,y],[x^2,y^2]) - (1-1/y)*substvec(gw, [x,y], [x^2,y^2]) - g^2 + (1-1/y)*gw*(gw+2*gu) )/2)); vector(#r, n, Vecrev(r[n]/y))}

A286958 Triangle read by rows: T(n,k) is the number of graphs with n vertices with connected domination number k.

Original entry on oeis.org

1, 1, 2, 4, 2, 11, 8, 2, 34, 62, 14, 2, 156, 514, 163, 18, 2, 1044, 7147, 2583, 317, 24, 2, 12346, 170803, 70667, 6720, 513, 29, 2, 274668, 7613603, 3566498, 247454, 13525, 785, 36, 2

Offset: 1

Eric W. Weisstein, May 17 2017

			Triangle begins:
    1;
    1;
    2;
    4,   2;
   11,   8,   2;
   34,  62,  14,  2;
  156, 514, 163, 18, 2;
  ...

Eric Weisstein's World of Mathematics, Connected Domination Number.

Row sums are A001349.
Column k=1 is A000088(n-1).
Cf. A263284, A332400, A332401.

cp's OEIS Frontend

A263284 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs on n vertices with domination number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A339833 Irregular triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with domination number k, n >= 1, 1 <= k <= A065033(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A286958 Triangle read by rows: T(n,k) is the number of graphs with n vertices with connected domination number k.

Views

Author

Keywords

Examples

Links

Crossrefs