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

A243781 Number of simple connected graphs on n nodes whose independence number a(g)=2.

Original entry on oeis.org

0, 0, 1, 4, 11, 34, 103, 405, 1892, 12166

Offset: 1

Travis Hoppe and Anna Petrone, Jun 20 2014

The independence number of a graph is the cardinality of the largest independent vertex set.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Independence Number, Maximum Independent Vertex Set

Column 2 of A294490.

Cf. Values of a(g) for simple connected graphs, A243781, A243782, A243783, A243784.

A243782 Number of simple connected graphs on n nodes whose independence number a(g)=3.

Original entry on oeis.org

0, 0, 0, 1, 8, 63, 524, 5863, 100702, 2880002

Offset: 1

Travis Hoppe and Anna Petrone, Jun 20 2014

The independence number of a graph is the cardinality of the largest independent vertex set.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Independence Number, Maximum Independent Vertex Set

Column 3 of A294490.

Cf. Values of a(g) for simple connected graphs, A243781, A243782, A243783, A243784.

A243783 Number of simple connected graphs on n nodes whose independence number a(g)=4.

Original entry on oeis.org

0, 0, 0, 0, 1, 13, 205, 4308, 135563, 7161399

Offset: 1

Travis Hoppe and Anna Petrone, Jun 20 2014

The independence number of a graph is the cardinality of the largest independent vertex set.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Independence Number, Maximum Independent Vertex Set

Column 4 of A294490.

Cf. Values of a(g) for simple connected graphs, A243781, A243782, A243783, A243784.

A243784 Number of simple connected graphs on n nodes whose independence number a(g)=5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 19, 513, 21782, 1576634

Offset: 1

Travis Hoppe and Anna Petrone, Jun 20 2014

The independence number of a graph is the cardinality of the largest independent vertex set.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Independence Number, Maximum Independent Vertex Set

Column 5 of A294490.

Cf. Values of a(g) for simple connected graphs, A243781, A243782, A243783, A243784.

A339829 Triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with independence number k.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 3, 1, 0, 0, 0, 0, 6, 4, 1, 0, 0, 0, 0, 5, 12, 5, 1, 0, 0, 0, 0, 0, 20, 20, 6, 1, 0, 0, 0, 0, 0, 15, 52, 31, 7, 1, 0, 0, 0, 0, 0, 0, 76, 107, 43, 8, 1, 0, 0, 0, 0, 0, 0, 49, 242, 192, 58, 9, 1, 0, 0, 0, 0, 0, 0, 0, 313, 589, 313, 75, 10, 1, 0

Offset: 1

Andrew Howroyd, Dec 18 2020

For n > 1, a star graph on n nodes has independence number n-1 and a path graph has independence number ceiling(n/2) which is the least possible in a tree.

A maximum independent set can be found in a tree using a greedy algorithm. First choose any node to be the root and perform a depth first search from the root. Include all leaves in the independent set (except possibly the root) and also greedily include any other node if no children are in the set. This method can be converted into an algorithm to compute the number of trees by independence number. See the PARI program for technical details.

			Triangle begins:
  1;
  1, 0;
  0, 1, 0;
  0, 1, 1, 0;
  0, 0, 2, 1,  0;
  0, 0, 2, 3,  1,  0;
  0, 0, 0, 6,  4,  1,  0;
  0, 0, 0, 5, 12,  5,  1, 0;
  0, 0, 0, 0, 20, 20,  6, 1, 0;
  0, 0, 0, 0, 15, 52, 31, 7, 1, 0;
  ...
There are 3 trees with 5 nodes:
    x                                     x
    |                                     |
    o---x---o    x---o---x---o---x    x---o---x
    |                                     |
    x                                     x
The first 2 of these have a maximum independent set of 3 nodes and the last has a maximum independent set of 4 nodes, so T(5,3)=2 and T(5,4)=1.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Eric Weisstein's World of Mathematics, Independence Number

Row sums are A000055.

Cf. A294490 (connected graphs), A339830, A339831, A339833 (domination number).

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1, -n)}
\\ In the following, u,v count rooted trees weighted by independence number: u is root in the set and v is root not in the set.
T(n)={my(u=[y], v=[0]); for(n=2, n, my(t=EulerMT(v)); v=concat([0], EulerMT(u+v)-t); u=y*concat([1], t)); my(g=x*Ser(u+v), gu=x*Ser(u), r=Vec(g + (substvec(g, [x,y], [x^2,y^2]) - (1-1/y)*substvec(gu, [x,y], [x^2,y^2]) - g^2 + (1-1/y)*gu^2 )/2)); vector(#r, n, Vecrev(r[n]/y, n))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

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

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

A243781 Number of simple connected graphs on n nodes whose independence number a(g)=2.

Views

Author

Keywords

Comments

Links

Crossrefs

A243782 Number of simple connected graphs on n nodes whose independence number a(g)=3.

Views

Author

Keywords

Comments

Links

Crossrefs

A243783 Number of simple connected graphs on n nodes whose independence number a(g)=4.

Views

Author

Keywords

Comments

Links

Crossrefs

A243784 Number of simple connected graphs on n nodes whose independence number a(g)=5.

Views

Author

Keywords

Comments

Links

Crossrefs

A339829 Triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with independence number k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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