A245797 -id:A245797 - cp's OEIS frontend

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

0, 1, 0, 6, 4, 50, 66, 532, 1016, 6876, 16750, 104456, 303612, 1821976, 6067166, 35857200, 133160176, 785514512, 3192117966, 18948962656, 83099447300, 498931946016, 2336474411062, 14234346694976, 70598633745576, 437304764440000, 2282139344678726, 14390600621415552

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

Graphs consist of zero or more paths on two nodes each and either a single isolated node or a star with two or more peripheral nodes. - Andrew Howroyd, Sep 05 2019

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

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

Column k = n - 1 of A327369.
The unlabeled version is A028242.
Cf. A006125, A059167, A100743, A245797, A294217, A327227, A327377.

f:= gfun:-rectoproc({(n-1)*(n-2)*a(n)-n*(n-3)*(n-2)*a(n-1)-n*(n-1)^2*a(n-2)+(2*n-7)*n*(n-1)*(n-2)*a(n-3)-n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5)=0, a(0)=0, a(1)=1, a(2)=0, a(3)=6, a(4)=4},a(n),remember):
map(f, [$0..40]); # Robert Israel, Sep 06 2019

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Count[Length/@Split[Sort[Join@@#]],1]==n-1&]],{n,0,5}]
With[{nn=30},CoefficientList[Series[x Exp[x^2/2](Exp[x]-x),{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Apr 28 2022 *)

seq(n)={Vec(serlaplace(x*exp(x^2/2 + O(x^n))*(exp(x + O(x^n))-x)), -(n+1))} \\ Andrew Howroyd, Sep 05 2019

E.g.f.: x*exp(x^2/2)*(exp(x) - x). - Andrew Howroyd, Sep 05 2019

(n-1)*(n-2)*a(n) - n*(n-3)*(n-2)*a(n-1) - n*(n-1)^2*a(n-2) + (2*n-7)*n*(n-1)*(n-2)*a(n-3) - n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5) = 0. - Robert Israel, Sep 06 2019

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

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

Gus Wiseman, Sep 04 2019

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 28 connected covering graphs with at least one endpoint.

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.

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}]

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

Inverse binomial transform of A327364.

a(n) = A001187(n) - A059166(n). - Andrew Howroyd, Sep 11 2019

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

A327366 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 23, 31, 9, 1, 0, 256, 515, 227, 25, 1, 0, 5319, 15381, 10210, 1782, 75, 1, 0, 209868, 834491, 815867, 221130, 15564, 231, 1, 0, 15912975, 83016613, 116035801, 47818683, 5499165, 151455, 763, 1, 0, 2343052576, 15330074139, 29550173053, 18044889597, 3291232419, 158416629, 1635703, 2619, 1, 0

Offset: 0

Gus Wiseman, Sep 04 2019

The minimum vertex-degree of the empty graph is infinity. It has been included here under k = 0. - Andrew Howroyd, Mar 09 2020

			Triangle begins:
     1
     1     0
     1     1     0
     4     3     1     0
    23    31     9     1     0
   256   515   227    25     1     0
  5319 15381 10210  1782    75     1     0

Andrew Howroyd, Table of n, a(n) for n = 0..230 (rows n = 0..20)
Gus Wiseman, The graphs with 4 vertices and minimum vertex-degree k (row n = 4).

Row sums are A006125.
Row sums without the first column are A006129.
Row sums without the first two columns are A100743.
Column k = 0 is A327367(n > 0).
Column k = 1 is A327227.
The unlabeled version is A294217.
Cf. A059167, A245797, A327069, A327103, A327334, A327369.

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

GraphsByMaxDegree(n)={
  local(M=Map(Mat([x^0, 1])));
  my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
  my(merge(r, p, v)=acc(p + sum(i=1, poldegree(p)-r-1, polcoef(p, i)*(1-x^i)), v));
  my(recurse(r, p, i, q, v, e)=if(i<0, merge(r, x^e+q, v), my(t=polcoef(p, i)); for(k=0, t, self()(r, p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+k))));
  for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(n-k, p, poldegree(p), 0, src[i, 2], 0)));
  Mat(M);
}
Row(n)={if(n==0, [1], my(M=GraphsByMaxDegree(n), u=vector(n+1)); for(i=1, matsize(M)[1], u[n-poldegree(M[i,1])]+=M[i,2]); u)}
{ for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Mar 09 2020

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

A327107 BII-numbers of set-systems with minimum vertex-degree > 1.

Original entry on oeis.org

7, 25, 30, 31, 42, 45, 47, 51, 52, 53, 54, 55, 59, 60, 61, 62, 63, 75, 76, 77, 78, 79, 82, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 97, 99, 100, 101, 102, 103, 105, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124

Offset: 1

Gus Wiseman, Aug 26 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

In a set-system, the degree of a vertex is the number of edges containing it.

			The sequence of all set-systems with maximum degree > 1 together with their BII-numbers begins:
   7: {{1},{2},{1,2}}
  25: {{1},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  42: {{2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  47: {{1},{2},{1,2},{3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  59: {{1},{2},{3},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}
  75: {{1},{2},{3},{1,2,3}}
  76: {{1,2},{3},{1,2,3}}

Positions of terms > 1 in A327103.
BII-numbers for minimum degree 1 are A327105.
Graphs with minimum degree > 1 are counted by A059167.
Cf. A000120, A029931, A048793, A058891, A070939, A245797, A326031, A326701, A326786, A327041, A327104, A327227-A327230.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100],Min@@Length/@Split[Sort[Join@@bpe/@bpe[#]]]>1&]

A327335 Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 4, 18, 216

Offset: 0

Gus Wiseman, Sep 02 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. 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 covering set-systems with minimum covered vertex-degree 1.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 18 set-systems:
  {{1}}  {{1}}        {{1}}
         {{1,2}}      {{1,2}}
         {{1},{2}}    {{1},{2}}
         {{1},{1,2}}  {{1,2,3}}
                      {{1},{1,2}}
                      {{1},{2,3}}
                      {{1},{1,2,3}}
                      {{1,2},{1,3}}
                      {{1},{2},{3}}
                      {{1,2},{1,2,3}}
                      {{1},{2},{1,3}}
                      {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{2},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1},{2},{3},{1,2}}
                      {{1},{2},{1,2},{1,3}}
                      {{1},{2},{1,2},{1,2,3}}

Unlabeled set-systems are A000612.
The labeled version is A327228.
The covering version is A327230 (first differences).
Cf. A002494, A245797, A261919, A283877, A327103, A327105, A327197, A327227, A327229, A327336.

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Original entry on oeis.org

0, 0, 1, 6, 46, 655, 17991, 927416, 89009740, 16020407709, 5468601546685, 3578414666656214, 4529751815161579194, 11175105490563109463875, 54043272967471942825421219, 514566625051705610110588073460, 9677104749727084630538798805505880

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

			The a(4) = 46 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}
  {13}  {12,14}  {12,13,24}  {12,13,14,24}
  {14}  {12,23}  {12,13,34}  {12,13,14,34}
  {23}  {12,24}  {12,14,23}  {12,13,23,24}
  {24}  {13,14}  {12,14,34}  {12,13,23,34}
  {34}  {13,23}  {12,23,24}  {12,14,23,24}
        {13,34}  {12,23,34}  {12,14,24,34}
        {14,24}  {12,24,34}  {12,23,24,34}
        {14,34}  {13,14,23}  {13,14,23,34}
        {23,24}  {13,14,24}  {13,14,24,34}
        {23,34}  {13,23,24}  {13,23,24,34}
        {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

The covering case is A327362.
Graphs with endpoints are A245797.
Graphs with connected edge-set are A287689.
Connected graphs with bridges are A327071.
Covering graphs with endpoints are A327227.
Cf. A001187, A059167, A141580, A322395, A327148, A327335, A327369.

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}]],Length[csm[#]]==1&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]

seq(n)={my(x=x + O(x*x^n)); Vec(serlaplace(exp(x)*(-x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!)) - log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x))^k/k!)))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Binomial transform of A327362.

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

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

A245796 T(n,k) is the number of labeled graphs of n vertices and k edges that have endpoints, where an endpoint is a vertex with degree 1.

Original entry on oeis.org

0, 1, 3, 3, 6, 15, 16, 12, 10, 45, 110, 195, 210, 120, 20, 15, 105, 435, 1320, 2841, 4410, 4845, 3360, 1350, 300, 30, 21, 210, 1295, 5880, 19887, 51954, 106785, 171360, 208565, 186375, 120855, 56805, 19110, 4410, 630, 42

Offset: 1

Chai Wah Wu, Aug 01 2014

The length of the rows are 1,1,2,4,7,11,16,22,...: (1+(n-1)*(n-2)/2) = A152947(n).
T(n,k) = 0 if k > (n-1)*(n-2)/2 + 1.
Let j = (n-1)*(n-2)/2.  For i >=0, n >= 4+i, T(n,j-i+1) = n*(n-1)*binomial(j,i).
For k <= 3, T(n,k) is equal to the number of labeled bipartite graphs with n vertices and k edges.  In particular, T(n,1) = A000217(n-1), T(n,2) = A050534(n) and T(n,3) = A053526(n).

			Triangle starts:
..0
..1
..3......3
..6.....15.....16.....12
.10.....45....110....195....210....120.....20
.15....105....435...1320...2841...4410...4845...3360...1350....300.....30
...

Chai Wah Wu, Graphs whose normalized Laplacian matrices are separable as density matrices in quantum mechanics, arXiv:1407.5663 [quant-ph], 2014.

Sum of n-th row is A245797(n).

Cf. A000217, A050534, A053526, A152947.

A327379 Number of labeled non-mating-type graphs with n vertices.

Original entry on oeis.org

0, 1, 4, 32, 436, 11292, 545784, 49826744, 8647819328, 2876819527744, 1848998498567936, 2312324942899031040, 5659406410382924819712, 27230994319259100289485568, 258465217554621196991878652416, 4851552662579126853087143276476928

Offset: 1

Gus Wiseman, Sep 05 2019

nonn

A mating-type graph has all different rows in its adjacency matrix.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(4) = 32 non-mating-type graphs.

The unlabeled version is A141580.

Cf. A006024, A006125, A028242, A059167, A245797, A327369, A327370.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!UnsameQ@@AdjacencyMatrix[Graph[Range[n],#]]&]],{n,5}]

a(n) = {2^binomial(n,2) - sum(k=0, n, stirling(n, k, 1)*2^binomial(k,2))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A006125(n) - A006024(n). - Andrew Howroyd, Sep 11 2019

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

cp's OEIS Frontend

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A327366 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A327107 BII-numbers of set-systems with minimum vertex-degree > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327335 Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327364 Number of labeled simple graphs with n vertices, a connected edge-set, and at least one endpoint (vertex of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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