A263341 -id:A263341 - cp's OEIS frontend

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

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.

A115196 Triangle read by rows formed from nonzero entries in table of number of graphs on n nodes with clique number k.

Original entry on oeis.org

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

Offset: 2

N. J. A. Sloane, based on email from Keith Briggs, Apr 03 2006

			Table: number of graphs on n nodes with clique number k
n = .1...2...3...4....5....6.....7......8........9.......10.
k ----------------------------------------------------------
2....0...1...2...6...13...37...106....409.....1896....12171 = A052450
3....0...0...1...3...15...82...578...6021...101267..2882460 = A052451
4....0...0...0...1...4....30...301...4985...142276..7269487 = A052452
5....0...0...0...0...1....5.....51....842....27107..1724440 = A077392
6....0...0...0...0...0....1......6.....80.....1995...112225 = A077393
7....0...0...0...0...0....0......1......7......117.....4210 = A077394
8....0...0...0...0...0....0......0......1........8......164 = A205577
9....0...0...0...0...0....0......0......0........1........9 = A205578
10...0...0...0...0...0....0......0......0........0........1.

Keith M. Briggs, Combinatorial Graph Theory
Eric Weisstein's World of Mathematics, Clique Number

Cf. A287024, A263341. Partial column sums: A304124, A304125.

1+Sum_{k>=2} T(n,k) = A000088(n). - R. J. Mathar, May 06 2018

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.

A287024 Triangle read by rows: T(n,k) is the number of graphs with n vertices with vertex cover number k-1.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein, May 18 2017

Aside from trailing 1's, same as A115196.

			Triangle begins:
  1;
  1, 1;
  1, 2,   1;
  1, 3,   6,    1;
  1, 4,  15,   13,      1;
  1, 5,  30,   82,     37,       1;
  1, 6,  51,  301,    578,     106,       1;
  1, 7,  80,  842,   4985,    6021,     409,       1;
  1, 8, 117, 1995,  27107,  142276,  101267,    1896,     1;
  1, 9, 164, 4210, 112225, 1724440, 7269487, 2882460, 12171, 1;
  ...
Row 3 is 1, 2, 1 because
\bar K_3 (1 graph) has vertex cover number 0
K_1\cup K_2 and P_3 (2 graphs) have vertex cover number 1
K_3=C_3 (1 graph) has vertex cover number 2
Here, \bar denotes graph complementation and \cup denotes (disjoint) graph union.

Andrew Howroyd, Table of n, a(n) for n = 1..91 (first 13 rows, after Brendan McKay data in A263341)
Eric Weisstein's World of Mathematics, Vertex Cover
Eric Weisstein's World of Mathematics, Vertex Cover Number

Cf. A000088 (row sums), A115196 (number of graphs on n nodes with clique number k), A263341.

Terms a(46) and beyond from Brendan McKay added by Andrew Howroyd, Feb 19 2020

A205577 Number of n-node simple graphs having clique number 8.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 8, 164, 8165, 1184155, 462435257

Offset: 1

Michael Sollami, Jan 29 2012

Also, number of n-node simple graphs having independence number 8. - Andrew Howroyd, Oct 31 2017

Column 8 of A263341.

Cf. A052450, A052451, A052452, A052453, A077392, A077393.

a(12) from Michael Sollami, Mar 26 2012

a(13) from Brendan McKay, May 07 2018

A205578 Number of n-node simple graphs having clique number 9.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 9, 221, 14838, 3273685

Offset: 1

Michael Sollami, Jan 29 2012

Also, number of n-node simple graphs having independence number 9. - Andrew Howroyd, Oct 31 2017

Column 9 of A263341.

a(12) from Michael Sollami, Mar 26 2012

a(13) from Brendan McKay, May 07 2018

A325304 Irregular triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with matching number k, (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 0, 1, 0, 2, 0, 1, 5, 0, 1, 20, 0, 1, 16, 95, 0, 1, 22, 830, 0, 1, 29, 790, 10297, 0, 1, 37, 1479, 259563, 0, 1, 46, 2625, 166988, 11546911

Offset: 0

Andrew Howroyd, Sep 05 2019

			Triangle begins:
  1;
  1;
  0, 1;
  0, 2;
  0, 1,  5;
  0, 1, 20;
  0, 1, 16,   95;
  0, 1, 22,  830;
  0, 1, 29,  790,  10297;
  0, 1, 37, 1479, 259563;
  0, 1, 46, 2625, 166988, 11546911;
  ...

Eric Weisstein's World of Mathematics, Matching Number
Wikipedia, Matching (graph theory)

Columns k=2..3 are A243800, A243801.
Row sums are A001349.
Cf. A286951 (not necessarily connected).
Cf. A218463 (right diagonal, even terms).
Cf. A263341, A294490.

T(2*n, n) = A218463(n).

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

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

A115196 Triangle read by rows formed from nonzero entries in table of number of graphs on n nodes with clique number k.

Views

Author

Keywords

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

A287024 Triangle read by rows: T(n,k) is the number of graphs with n vertices with vertex cover number k-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A205577 Number of n-node simple graphs having clique number 8.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A205578 Number of n-node simple graphs having clique number 9.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A325304 Irregular triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with matching number k, (0 <= k <= floor(n/2)).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs