A324693 -id:A324693 - cp's OEIS frontend

A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf.

0, 0, 1, 3, 31, 515, 15381, 834491, 83016613, 15330074139, 5324658838645, 3522941267488973, 4489497643961740521, 11119309286377621015089, 53893949089393110881259181, 513788884660608277842596504415, 9669175277199248753133328740702449

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Covering means there are no isolated vertices.
A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.
Also graphs with minimum vertex-degree 1.

			The a(4) = 31 edge-sets:
  {12,34}  {12,13,14}  {12,13,14,23}
  {13,24}  {12,13,24}  {12,13,14,24}
  {14,23}  {12,13,34}  {12,13,14,34}
           {12,14,23}  {12,13,23,24}
           {12,14,34}  {12,13,23,34}
           {12,23,24}  {12,14,23,24}
           {12,23,34}  {12,14,24,34}
           {12,24,34}  {12,23,24,34}
           {13,14,23}  {13,14,23,34}
           {13,14,24}  {13,14,24,34}
           {13,23,24}  {13,23,24,34}
           {13,23,34}  {14,23,24,34}
           {13,24,34}
           {14,23,24}
           {14,23,34}
           {14,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k=1 of A327366.
The non-covering version is A245797.
The unlabeled version is A324693.
The generalization to set-systems is A327229.
BII-numbers of set-systems with minimum degree 1 are A327105.
Cf. A001187, A006129, A059166, A059167, A100743, A136284, A327079, A327098, A327103, A327228, A327230.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

Inverse binomial transform of A245797, if we assume A245797(0) = 0.

A294217 Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 4, 2, 1, 11, 12, 8, 2, 1, 34, 60, 43, 15, 3, 1, 156, 378, 360, 121, 25, 3, 1, 1044, 3843, 4869, 2166, 378, 41, 4, 1, 12346, 64455, 113622, 68774, 14306, 1095, 65, 4, 1, 274668, 1921532, 4605833, 3953162, 1141597, 104829, 3441, 100, 5, 1

Offset: 1

Eric W. Weisstein, Oct 25 2017

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A327366. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 10 2020

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    4,   4,   2,   1;
   11,  12,   8,   2,  1;
   34,  60,  43,  15,  3, 1;
  156, 378, 360, 121, 25, 3, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)
Eric Weisstein's World of Mathematics, Minimum Vertex Degree

Row sums are A000088 (simple graphs on n nodes).
Columns k=0..2 are A000088(n-1), A324693, A324670.
Cf. A263293 (triangle of n-node maximum vertex degree counts).
The labeled version is A327366.
Cf. A002494, A004110, A261919, A327227, A327230, A327335, A327372.

T(n, 0) = A000088(n-1).
T(n, n-2) = A004526(n) for n > 1.
T(n, n-1) = 1.
T(n, k) = A263293(n, n-1-k). - Andrew Howroyd, Sep 03 2019

A263293 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and maximum vertex degree k, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 4, 4, 1, 2, 8, 12, 11, 1, 3, 15, 43, 60, 34, 1, 3, 25, 121, 360, 378, 156, 1, 4, 41, 378, 2166, 4869, 3843, 1044, 1, 4, 65, 1095, 14306, 68774, 113622, 64455, 12346, 1, 5, 100, 3441, 104829, 1141597, 3953162, 4605833, 1921532, 274668

Offset: 1

Christian Stump, Oct 13 2015

			Triangle begins:
1,
1,    1,
1,    1,    2,
1,    2,    4,    4,
1,    2,    8,   12,   11,
1,    3,   15,   43,   60,   34,
1,    3,   25,  121,  360,  378,  156,
1,    4,   41,  378, 2166, 4869, 3843, 1044,
...

Andrew Howroyd, Table of n, a(n) for n = 1..210 (first 20 rows)
FindStat - Combinatorial Statistic Finder, The degree of a graph
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A000088 (simple graphs on n nodes).
Column k=2 is A324740.
Diagonals include A000088(n-1), A324693, A324670.
Cf. A294217 (triangle of n-node minimum vertex degree counts).
Cf. A327366.

From Geoffrey Critzer, Sep 10 2016: (Start)
G.f. for column k=0: A(x)=1/(1-x).
G.f. for column k=1: B(x)=x^2/((1-x^2)(1-x)).
G.f. for column k=2: 1/((1-x)(1-x^2))*Product_{i>=3} 1/(1-x^i)^2 - B(x) - A(x).
(End)
T(n, 0) = 1.
T(n, n - 1) = A000088(n - 1).
T(n, k) = A294217(n, n - 1 - k). - Andrew Howroyd, Sep 03 2019

Rows n=9 and 10 added by Eric W. Weisstein, Oct 24 2017

cp's OEIS Frontend

A327227 Number of labeled simple graphs covering n vertices with at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A294217 Triangle read by rows: T(n,k) is the number of graphs with n vertices and minimum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A263293 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs with n vertices and maximum vertex degree k, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions