A332405 -id:A332405 - 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

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

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 11, 16, 5, 1, 1, 34, 90, 25, 5, 1, 1, 156, 668, 188, 25, 5, 1, 1, 1044, 8648, 2394, 228, 25, 5, 1, 1, 12346, 199990, 58578, 3493, 229, 25, 5, 1, 1, 274668, 8776166, 2837118, 113197, 3758, 229, 25, 5, 1, 1

Offset: 1

Andrew Howroyd, Feb 11 2020

The independent domination number of a graph is the minimum size of a maximal independent set (sets which are both independent and dominating). For any graph it is greater than or equal to the domination number (A263284) and less than or equal to the independence number (A263341).

The final terms of each row tend to the sequence (1, 1, 5, 25, 229, 3759, ...). This happens because a connected graph on n nodes with n > 1 cannot have an independent domination number > floor(n/2). Similar limits are seen in A263284 and A332404 for the same reason.

			Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       4,       5,       1,      1;
      11,      16,       5,      1,    1;
      34,      90,      25,      5,    1,   1;
     156,     668,     188,     25,    5,   1,  1;
    1044,    8648,    2394,    228,   25,   5,  1, 1;
   12346,  199990,   58578,   3493,  229,  25,  5, 1, 1;
  274668, 8776166, 2837118, 113197, 3758, 229, 25, 5, 1, 1;
  ...

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Row sums are A000088.
Column k=1 is A000088(n-1).
Cf. A263284, A263341, A332402, A332403, A332404, A332405.

T(n,k) = T(n-1,k-1) for 2*(k-1) >= n.

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 13, 15, 4, 1, 1, 36, 83, 30, 5, 1, 1, 101, 582, 302, 51, 6, 1, 1, 365, 6024, 5025, 843, 80, 7, 1, 1, 1518, 99497, 144370, 27160, 1996, 117, 8, 1, 1, 8002, 2706069, 7441209, 1733211, 112291, 4211, 164, 9, 1

Offset: 1

Andrew Howroyd, Feb 11 2020

First differs from A263341 in row 6.

The upper domination number of a graph is the maximum size of a minimal dominating set (a set that is both dominating and irredundant). For any graph it is greater than or equal to the independence number (A263341) and less than or equal to the upper irredundance number (A332405). The number of graphs where it is strictly greater than is given in A332407.

			Triangle begins:
  1;
  1,    1;
  1,    2,       1;
  1,    6,       3,       1;
  1,   13,      15,       4,       1;
  1,   36,      83,      30,       5,      1;
  1,  101,     582,     302,      51,      6,    1;
  1,  365,    6024,    5025,     843,     80,    7,   1;
  1, 1518,   99497,  144370,   27160,   1996,  117,   8, 1;
  1, 8002, 2706069, 7441209, 1733211, 112291, 4211, 164, 9, 1;
  ...

Eric Weisstein's World of Mathematics, Minimal Dominating Set

Row sums are A000088.

Cf. A263284, A263341, A332402, A332404, A332405, A332407.

A332404 Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes with irredundance number k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 11, 16, 5, 1, 1, 34, 94, 21, 5, 1, 1, 156, 710, 150, 21, 5, 1, 1, 1044, 9419, 1691, 164, 21, 5, 1, 1, 12346, 221979, 38207, 1944, 164, 21, 5, 1, 1, 274668, 9907071, 1773452, 47802, 1983, 164, 21, 5, 1, 1

Offset: 1

Andrew Howroyd, Feb 11 2020

The irredundance number of a graph is the minimum size of a maximal irredundant set.
For any graph the following relation holds:
   irredundance number (this sequence)
      <= domination number (A263284)
      <= independent domination number (A332402)
      <= independence number (A263341)
      <= upper domination number (A332403)
      <= upper irredundance number (A332405).

			Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       4,       5,       1,     1;
      11,      16,       5,     1,    1;
      34,      94,      21,     5,    1,   1;
     156,     710,     150,    21,    5,   1,  1;
    1044,    9419,    1691,   164,   21,   5,  1, 1;
   12346,  221979,   38207,  1944,  164,  21,  5, 1, 1;
  274668, 9907071, 1773452, 47802, 1983, 164, 21, 5, 1, 1;
  ...

Eric Weisstein's World of Mathematics, Maximal Irredundant Set

Row sums are A000088.
Column k=1 is A000088(n-1).
Cf. A263284, A263341, A332402, A332403, A332404, A332405.

T(n,k) = T(n-1,k-1) for 2*(k-1) >= n.

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A332404 Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes with irredundance number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula