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

Author

Christian Stump, Oct 15 2015

Keywords

• nonn
• tabl

Comments

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

Examples

			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;
  ...
		

Links

• 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)

Crossrefs

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.

Extensions

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