cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

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

Original entry on oeis.org

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

Views

Author

Gus Wiseman, Sep 01 2019

Keywords

Comments

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.

Examples

			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}

Links

Crossrefs

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.

Programs

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

Formula

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

Views

Author

Eric W. Weisstein, Oct 25 2017

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Formula

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

Views

Author

Christian Stump, Oct 13 2015

Keywords

Comments

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

Examples

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

Links

Crossrefs

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.

Formula

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

Extensions

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

A327362 Number of labeled connected graphs covering n vertices with at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 3, 28, 475, 14646, 813813, 82060392, 15251272983, 5312295240010, 3519126783483377, 4487168285715524124, 11116496280631563128723, 53887232400918561791887118, 513757147287101157620965656285, 9668878162669182924093580075565776
Offset: 0

Views

Author

Gus Wiseman, Sep 04 2019

Keywords

Comments

A graph is covering if the vertex set is the union of the edge set, so there are no isolated vertices.

Links

Crossrefs

The non-connected version is A327227.
The non-covering version is A327364.
Graphs with endpoints are A245797.
Connected covering graphs are A001187.
Connected graphs with bridges are A327071.
Cf. A004110, A059166, A006125, A006129, A059166, A100743, A141580, A322395, A327105, A327229, A327230, A327366, A327369, A327377.

Programs

  • Mathematica
    csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]
  • PARI
    seq(n)={Vec(serlaplace(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k! + O(x*x^n))) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Formula

Inverse binomial transform of A327364.
a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

Extensions

Terms a(7) and beyond from Andrew Howroyd, Sep 11 2019

A324693 Number of simple graphs on n unlabeled nodes with minimum degree exactly 1.

Original entry on oeis.org

0, 1, 1, 4, 12, 60, 378, 3843, 64455, 1921532, 104098702, 10348794144, 1893781768084, 639954768875644, 400905675004630820, 467554784370658979194, 1019317687720204607541914, 4170177760438554428852944352, 32130458453030025927403299167172
Offset: 1

Views

Author

Andrew Howroyd, Sep 03 2019

Keywords

Links

Crossrefs

Column k = 1 of A294217.
A diagonal of A263293.
The labeled version is A327227.
The generalization to set-systems is A327335, with covering case A327230.
Unlabeled covering graphs are A002494.
Cf. A000088, A004110, A100743, A141580, A245797, A261919, A327105, A327362, A327364, A327366, A327372.

Formula

a(n) = A002494(n) - A261919(n).
First differences of A141580. - Andrew Howroyd, Jan 11 2021
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.