A327372 -id:A327372 - cp's OEIS frontend

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

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

A327371 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 2, 0, 2, 0, 5, 1, 3, 1, 1, 16, 6, 7, 2, 3, 0, 78, 35, 25, 8, 7, 2, 1, 588, 260, 126, 40, 20, 6, 4, 0, 8047, 2934, 968, 263, 92, 25, 13, 3, 1, 205914, 53768, 11752, 2434, 596, 140, 47, 12, 5, 0, 10014882, 1707627, 240615, 34756, 5864, 1084, 256, 58, 21, 4, 1

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
     1;
     1,    0;
     1,    0,   1;
     2,    0,   2,   0;
     5,    1,   3,   1,  1;
    16,    6,   7,   2,  3,  0;
    78,   35,  25,   8,  7,  2,  1;
   588,  260, 126,  40, 20,  6,  4, 0;
  8047, 2934, 968, 263, 92, 25, 13, 3, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Gus Wiseman, The graphs counted in row 5 (isolated vertices not shown).

Row sums are A000088.
Row sums without the first column are A141580.
Columns k = 0..2 are A004110, A325115, A325125.
Column k = n is A059841.
Column k = n - 1 is A028242.
The labeled version is A327369.
The covering case is A327372.
Cf. A055540, A059167, A245797, A294217, A327227, A327370.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)*(1-x^2*y)/(1-x^2*y^2)}
T(n)={my(v=Vec(G(n))); vector(#v, n, Vecrev(v[n], n))}
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 22 2021

Column-wise partial sums of A327372.

Terms a(21) and beyond from Andrew Howroyd, Sep 05 2019

A327377 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly k endpoints (vertices of degree 1).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 3, 0, 10, 12, 12, 4, 3, 253, 260, 160, 60, 35, 0, 12068, 9150, 4230, 1440, 480, 66, 15, 1052793, 570906, 195048, 53200, 12600, 2310, 427, 0, 169505868, 63523656, 15600032, 3197040, 585620, 95088, 14056, 1016, 105

Offset: 0

Gus Wiseman, Sep 05 2019

A graph is covering if there are no isolated vertices.

			Triangle begins:
      1
      0     0
      0     0     1
      1     0     3     0
     10    12    12     4     3
    253   260   160    60    35     0
  12068  9150  4230  1440   480    66    15

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

Row sums are A006129.
Column k = 0 is A100743.
Column k = n is A123023.
Row sums without the first column are A327227.
The non-covering version is A327369.
The unlabeled version is A327372.
Cf. A004110, A006125, A055302, A055314, A059167, A245797, A327362, A327364, A327370.

Row(n)={ \\ R, U, B are e.g.f. of A055302, A055314, A059167.
  my(U=sum(n=2, n, x^n*sum(k=1, n, stirling(n-2, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(R=sum(n=1, n, x^n*sum(k=1, n, stirling(n-1, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(B=x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!)));
  my(A=exp(-x + O(x*x^n))*exp(x + U + subst(B-x, x, x*(1-y) + R)));
  Vecrev(n!*polcoef(A, n), n + 1);
}
{ for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Oct 05 2019

Column-wise inverse binomial transform of A327369.

E.g.f.: exp(-x)*exp(x + U(x,y) + B(x*(1-y) + R(x,y))), where R(x,y) is the e.g.f. of A055302, U(x,y) is the e.g.f. of A055314 and B(x) + x is the e.g.f. of A059167. - Andrew Howroyd, Oct 05 2019

Terms a(28) and beyond from Andrew Howroyd, Oct 05 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

Andrew Howroyd, Sep 03 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Minimum Vertex Degree
Gus Wiseman, The a(2) = 1 through a(5) = 12 unlabeled graphs with minimum degree 1.

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.

a(n) = A002494(n) - A261919(n).

First differences of A141580. - Andrew Howroyd, Jan 11 2021

cp's OEIS Frontend

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

A327371 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A327377 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly k endpoints (vertices of degree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula