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

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

A304124 Number of simple graphs with n vertices which contain no K4 subgraph.

Original entry on oeis.org

1, 2, 4, 10, 29, 120, 685, 6431, 103164, 2894632, 138892304, 11118977705, 1459412127955

Offset: 1

Brendan McKay, May 06 2018

The graphs do not need to be connected.

Cf. A000088, A006785 (no K3), A115196 (graphs by clique number), A304125 (no K5).

a(n) = 1+A052450(n)+A052451(n).

a(13) from Brendan McKay, May 08 2018

A304125 Number of simple graphs with n vertices which contain no K5 subgraph.

Original entry on oeis.org

1, 2, 4, 11, 33, 150, 986, 11416, 245440, 10164119, 793907916, 114150623175, 29709609171994

Offset: 1

Brendan McKay, May 06 2018

The graphs do not need to be connected.

Cf. A000088, A006785 (no K3), A115196 (graphs by clique number), A304124 (no K4).

a(n) = 1+A052450(n)+A052451(n)+A052452(n).

a(13) from Brendan McKay, May 08 2018

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

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

A304124 Number of simple graphs with n vertices which contain no K4 subgraph.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A304125 Number of simple graphs with n vertices which contain no K5 subgraph.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions