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

A263284 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs on n vertices with domination 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, 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.

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.

A332407 Number of simple graphs on n unlabeled nodes with upper domination number greater than independence number.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 6, 85, 2574, 193486

Offset: 1

Andrew Howroyd, Feb 15 2020

The upper domination number of a graph is the maximum cardinality of a minimal dominating set. For any graph the upper domination number is greater than or equal to the independence number. This sequence gives the number of graphs where it is strictly greater than.

The m X n rook graphs with 2 <= m < n are a class of graph with this property because the independence number is m, and a row of n rooks is minimally dominating.

			The a(6) = 1 graph illustrated below has independence number 2 and upper domination number 3.
    *--------o
    | \    / |
    |  *--o  |
    | /    \ |
    *--------o
The above graph is the 2 X 3 rook graph, drawn to show all edges.
The three vertices marked with an asterisk are a minimal dominating set.

Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Cf. A263341, A332403.

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

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

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

A332407 Number of simple graphs on n unlabeled nodes with upper domination number greater than independence number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs