A263284 -id:A263284 - cp's OEIS frontend

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

1, 1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 13, 15, 4, 1, 1, 37, 82, 30, 5, 1, 1, 106, 578, 301, 51, 6, 1, 1, 409, 6021, 4985, 842, 80, 7, 1, 1, 1896, 101267, 142276, 27107, 1995, 117, 8, 1, 1, 12171, 2882460, 7269487, 1724440, 112225, 4210, 164, 9, 1, 1, 105070, 138787233, 655015612, 210799447, 13893557, 388547, 8165, 221, 10, 1

Offset: 1

Christian Stump, Oct 15 2015

The independence number of a graph is the maximum size of an independent set.
Row sums give A000088, n >= 1.
T(n,k) is also the number of graphs on n vertices such that a largest clique is of size k. - Geoffrey Critzer, Sep 23 2016
T(n,k) is also the number of graphs on n vertices such that the size of a smallest vertex cover is n-k. - Geoffrey Critzer, Sep 23 2016
T(n,k) is also the number of graphs on n vertices with independence number k. - Eric W. Weisstein, May 17 2017
For any graph the independence number is greater than or equal to the independent domination number (A332402) and less than or equal to the upper domination number (A332403). - Andrew Howroyd, Feb 19 2020

			Triangle begins:
  1;
  1,     1;
  1,     2,       1;
  1,     6,       3,       1;
  1,    13,      15,       4,       1;
  1,    37,      82,      30,       5,      1;
  1,   106,     578,     301,      51,      6,    1;
  1,   409,    6021,    4985,     842,     80,    7,   1;
  1,  1896,  101267,  142276,   27107,   1995,  117,   8, 1;
  1, 12171, 2882460, 7269487, 1724440, 112225, 4210, 164, 9, 1;
  ...

Brendan McKay, Table of n, a(n) for n = 1..91 (first 13 rows)
FindStat - Combinatorial Statistic Finder, The length of the maximal independent set of vertices of a graph.
FindStat - Combinatorial Statistic Finder, The order of the largest clique of the graph.
Eric Weisstein's World of Mathematics, Clique Number
Eric Weisstein's World of Mathematics, Independence Number
Wikipedia, Clique (graph theory)

Row sums are A000088.
Columns 2..9 are A052450, A052451, A052452, A077392, A077393, A077394, A205577, A205578.
Transpose of A287024.
Cf. A115196, A126744 (clique number of connected graphs), A294490 (independence number of connected graphs).
Cf. A263284, A332402, A332403.

a(21)-a(28) from Geoffrey Critzer, Sep 22 2016
Rows 8-10 from Eric W. Weisstein, May 16 2017
Rows 11-13 from Brendan McKay, Feb 18 2020
Name clarified by Andrew Howroyd, Feb 18 2020

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.

A332405 Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes with upper irredundance 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, 364, 6025, 5025, 843, 80, 7, 1, 1, 1511, 99503, 144371, 27160, 1996, 117, 8, 1, 1, 7917, 2706030, 7441332, 1733212, 112291, 4211, 164, 9, 1

Offset: 1

Andrew Howroyd, Feb 11 2020

First differs from A332403 in row 7.

The upper irredundance number of a graph is the maximum size of an irredundant set. For any graph the upper irredundance number is greater than or equal to the upper domination number (A332403).

			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,  364,    6025,    5025,     843,     80,    7,   1;
  1, 1511,   99503,  144371,   27160,   1996,  117,   8, 1;
  1, 7917, 2706030, 7441332, 1733212, 112291, 4211, 164, 9, 1;
  ...

Eric Weisstein's World of Mathematics, Irredundant Set

Row sums are A000088.

Cf. A263284, A263341, A332402, A332403, A332404.

A332400 Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes with total domination number k, n >= 2, 2 <= k <= n.

Original entry on oeis.org

1, 2, 0, 6, 0, 1, 19, 2, 2, 0, 96, 14, 11, 0, 1, 670, 163, 51, 2, 2, 0, 8191, 2583, 495, 21, 11, 0, 1, 183149, 70667, 8127, 314, 61, 2, 2, 0, 7888271, 3566498, 268125, 6929, 644, 21, 11, 0, 1

Offset: 2

Andrew Howroyd, Feb 11 2020

Only graphs without isolated nodes can have a total dominating set.

The total domination number of a graph is greater than or equal to the domination number.

			Triangle begins, n >= 2, k >= 2:
        1;
        2,       0;
        6,       0,      1;
       19,       2,      2,    0;
       96,      14,     11,    0,   1;
      670,     163,     51,    2,   2,  0;
     8191,    2583,    495,   21,  11,  0,  1;
   183149,   70667,   8127,  314,  61,  2,  2, 0;
  7888271, 3566498, 268125, 6929, 644, 21, 11, 0, 1;
  ...

Eric Weisstein's World of Mathematics, Total Domination Number
Wikipedia, Dominating set

Column k=2 is A332406.
Row sums are A002494.
Cf. A263284, A286958.

T(2*n, 2*n) = 1; T(2*n+1, 2*n) = 2; T(2*n+1, 2*n+1) = T(2*n+2, 2*n+1) = 0.

A332401 Irregular triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with domination number k, n >= 1, 1 <= k <= A065033(n+1).

Original entry on oeis.org

1, 1, 2, 4, 2, 11, 10, 34, 76, 2, 156, 655, 42, 1044, 9162, 905, 6, 12346, 219823, 28720, 191, 274668, 9864065, 1568173, 9644, 21

Offset: 1

Andrew Howroyd, Feb 11 2020

Bivariate inverse Euler transform of A263284. This sequence can be derived from A263284 because the domination number of a disconnected graph is the sum of the domination numbers of its components.

Connected graphs with greatest domination number include the path graph.

			Triangle begins:
      1;
      1;
      2;
      4,      2;
     11,     10;
     34,     76,     2;
    156,    655,    42;
   1044,   9162,   905,   6;
  12346, 219823, 28720, 191;
   ....

Eric Weisstein's World of Mathematics, Domination Number
Wikipedia, Dominating set

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

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.

A332625 Number of simple graphs on n unlabeled nodes with domination number 2.

Original entry on oeis.org

0, 1, 1, 5, 16, 94, 708, 9384, 221135, 9877969

Offset: 1

Andrew Howroyd, Feb 17 2020

Eric Weisstein's World of Mathematics, Domination Number.

Column k=2 of A263284.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A332400 Triangle read by rows: T(n,k) is the number of simple graphs on n unlabeled nodes with total domination number k, n >= 2, 2 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A332401 Irregular triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with domination number k, n >= 1, 1 <= k <= A065033(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A332625 Number of simple graphs on n unlabeled nodes with domination number 2.

Views

Author

Keywords

Links

Crossrefs