login
A263341
Triangle read by rows: T(n,k) is the number of unlabeled graphs on n vertices with independence number k.
19
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,5
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
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
EXAMPLE
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;
...
CROSSREFS
Row sums are A000088.
Transpose of A287024.
Cf. A115196, A126744 (clique number of connected graphs), A294490 (independence number of connected graphs).
Sequence in context: A084268 A332405 A332403 * A201198 A349933 A120258
KEYWORD
nonn,tabl
AUTHOR
Christian Stump, Oct 15 2015
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
STATUS
approved