A053530 -id:A053530 - cp's OEIS frontend

A369193 Number of labeled simple graphs with n vertices and at most as many edges as covered (non-isolated) vertices.

1, 1, 2, 8, 57, 608, 8614, 151365, 3162353, 76359554, 2088663444, 63760182536, 2147325661180, 79051734050283, 3157246719905273, 135938652662043977, 6275929675565965599, 309242148569525451140, 16197470691388774460758, 898619766673014862321176, 52639402023471657682257626

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 1 through a(3) = 8 graphs:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}

The case of equality is A367862, covering case of A116508, also A367863.
The covering case is A369191, for loop-graphs A369194.
The version counting all vertices is A369192.
The version for loop-graphs is A369196, counting all vertices A066383.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001187, A006649, A053530, A129271, A143543, A322661, A367916.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]<=Length[Union@@#]&]],{n,0,5}]

Binomial transform of A369191.

A001862 Number of forests of least height with n nodes.

Original entry on oeis.org

1, 1, 2, 7, 26, 111, 562, 3151, 19252, 128449, 925226, 7125009, 58399156, 507222535, 4647051970, 44747776651, 451520086208, 4761032807937, 52332895618066, 598351410294193, 7102331902602676, 87365859333294151, 1111941946738682522, 14621347433458883187

Offset: 0

N. J. A. Sloane

nonn

From Gus Wiseman, Feb 14 2024: (Start)
Also the number of minimal loop-graphs covering n vertices. This is the minimal case of A322661. For example, the a(0) = 1 through a(3) = 7 loop-graphs are (loops represented as singletons):
  {}  {1}  {12}   {1-23}
           {1-2}  {2-13}
                  {3-12}
                  {12-13}
                  {12-23}
                  {13-23}
                  {1-2-3}
(End)

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983. See (3.3.7): number of ways to cover the complete graph K_n with star graphs.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
John Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
John Riordan, Letter to N. J. A. Sloane, Oct. 1970
John Riordan and N. J. A. Sloane, Correspondence, 1974

The connected case is A000272.
Without loops we have A053530, minimal case of A369191.
This is the minimal case of A322661.
A000666 counts unlabeled loop-graphs, covering A322700.
A006125 counts simple graphs; also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
Cf. A000085, A000169, A003465, A062740, A066383, A133686, A368597.

Range[0, 20]! CoefficientList[Series[Exp[x Exp[x] - x^2/2], {x, 0, 20}], x] (* Geoffrey Critzer, Mar 13 2011 *)
fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]& /@ Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];
Table[Length@fasmin[Select[Subsets[Subsets[Range[n],{1,2}]], Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Feb 14 2024 *)

E.g.f.: exp(x*(exp(x)-x/2)).

Binomial transform of A053530. - Gus Wiseman, Feb 14 2024

Formula and more terms from Vladeta Jovovic, Mar 27 2001

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

These are graphs with n vertices and n edges having at least two cycles in the same component.

			The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Without the choice condition we have A001434, covering A006649.
The labeled version without choice is A116508, covering A367863, A367862.
The complement is counted by A137917, labeled A137916.
For any number of edges we have A140637, complement A134964.
For labeled set-systems we have A368600.
The case with loops is A368835, labeled A368596.
The labeled version is A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])],{p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute/@Select[Subsets[Subsets[Range[n],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A001434(n) - A137917(n).

a(25) onwards from Andrew Howroyd, Feb 02 2024

A290716 Number of minimal dominating sets in the n-triangular (Johnson) graph.

Original entry on oeis.org

1, 1, 1, 3, 15, 35, 225, 1197, 6881, 45369, 327375, 2460755, 19925367, 171368067, 1551364997, 14763620445, 147405166785, 1538113071857, 16732908859599, 189413984297187, 2226589748578775, 27130592749003275, 342118450334269917, 4458168165784234253, 59952936723606219009

Offset: 0

Eric W. Weisstein, Aug 09 2017

nonn

A minimal dominating set on the triangular graph corresponds either with a minimal edge cover on the complete graph minus one vertex or with a perfect matching on the complete graph. Perfect matchings on the complete graph exists only for even n. - Andrew Howroyd, Aug 13 2017

Also the number of maximal irredundant sets in the n-triangular graph. - Eric W. Weisstein, Dec 31 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A001147, A053530, A290847.

b[n_]:=n! Sum[1/k! (Binomial[k, n - k] 2^(k - n) (-1)^k + Sum[Binomial[k, j] Sum[j^(i - j)/(i - j)! Binomial[k - j, n - i - k + j] 2^(i - j + k - n) (-1)^(k - j), {i, j, n - k + j}], {j, k}]), {k, n}]; Join[{1, 1}, Table[n b[n - 1] + If[Mod[n, 2] == 0, (n - 1)!!, 0], {n, 2, 20}]] (* Eric W. Weisstein, Aug 14 2017 *)
Range[0, 20]! CoefficientList[Series[Exp[x^2/2] + x Exp[x Exp[x] - (x + x^2/2)], {x, 0, 20}], x] (* Eric W. Weisstein, Apr 23 2018 *)

\\ here b(n) is A053530, df(n) is (2*n-1)!! = A001147
b(n)=polcoeff(serlaplace(exp(-x-1/2*x^2+x*exp(x+O(x^(n+1))))),n,x);
df(n)=polcoeff(serlaplace((1-2*x+O(x^(n+1)))^(-1/2)),n,x);
a(n) = n*b(n-1) + if(n%2==0, df(n/2), 0); \\ Andrew Howroyd, Aug 13 2017

seq(n)={Vec(serlaplace(exp(x^2/2 + O(x*x^n)) + x*exp(x*exp(x + O(x^n)) - (x+x^2/2))))} \\ Andrew Howroyd, Apr 21 2018

a(n) = n*A053530(n-1) for n odd, a(n) = (n-1)!! + n*A053530(n-1) for n even. - Andrew Howroyd, Aug 13 2017

E.g.f.: exp(x^2/2) + x*exp(x*exp(x) - (x+x^2/2)). - Andrew Howroyd, Apr 21 2018

a(8)-a(24) from formula by Andrew Howroyd, Aug 13 2017

a(0)-a(1) prepended by Andrew Howroyd, Apr 21 2018

A210655 Number of irreducible coverings by edges of the complete bipartite graph K_{n,n}; main diagonal of A210654.

Original entry on oeis.org

1, 2, 15, 184, 2945, 63756, 1748803, 58746304, 2361347073, 111310111900, 6059192459771, 376064819659728, 26330615879623393, 2061099487899901372, 178985517944285956275, 17127853895338704829696, 1795558477562697433148417, 205139946486547987323752124

Offset: 1

N. J. A. Sloane, Mar 27 2012

nonn

In other words, the number of minimal edge covers in the complete bipartite graph K_{n,n}. - Andrew Howroyd, Aug 04 2017

Alois P. Heinz, Table of n, a(n) for n = 1..304
Ioan Tomescu, Some properties of irreducible coverings by cliques of complete multipartite graphs, J. Combin. Theory Ser. B 28 (1980), no. 2, 127--141. MR0572469 (81i:05106).
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Cf. A053530 (complete graph), A210654.

T:= proc(p, q) option remember; `if`(p=1 or q=1, 1,
         add(binomial(q, r) *T(p-1, q-r), r=2..q-1)
      +q*add(binomial(p-1, s) *T(p-s-1, q-1), s=0..p-2))
    end:
a:= n-> T(n, n):
seq(a(n), n=1..20);  # Alois P. Heinz, Feb 10 2013

T[p_, q_] := T[p, q] = If[p == 1 || q === 1, 1, Sum[Binomial[q, r]*T[p - 1, q - r], {r, 2, q - 1}] + q*Sum[Binomial[p - 1, s]*T[p - s - 1, q - 1], {s, 0, p - 2}]]; a[n_] := T[n, n]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
With[{ser = Series[Exp[x Exp[y] + y Exp[x] - x - y - x y] - 1, {x, 0, 20}, {y, 0, 20}]}, Table[(n!)^2 Coefficient[ser, x^n y^n], {n, 20}]] (* Eric W. Weisstein, Aug 10 2017 *)

a(n) = n!^2 [x^n y^n] exp(x*exp(y)+y*exp(x)-x-y-x*y)-1. - Alois P. Heinz, Feb 10 2013

More terms from Alois P. Heinz, Feb 10 2013

A290715 Number of minimal edge covers in the n-barbell graph.

Original entry on oeis.org

12, 82, 1540, 35786, 880372, 30032066, 1234252432, 57364282990, 3118120533196, 194664165928178, 13642997281164016, 1068856625530082390, 93052682387512347676, 8925752446376598352186, 937682295833817289298944, 107371680361648855572333662

Offset: 3

Eric W. Weisstein, Aug 09 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 3..100
Eric Weisstein's World of Mathematics, Barbell Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Cf. A053530.

b[n_] := n! Sum[1/k! (Binomial[k, n - k] 2^(k - n) (-1)^k + Sum[Binomial[k, j] Sum[j^(i - j)/(i - j)! Binomial[k - j, n - i - k + j] 2^(i - j + k - n) (-1)^(k - j), {i, j, n - k + j}], {j, k}]), {k, n}]; Table[b[n]^2 + b[n - 1] (b[n - 1] + 2 + 2 Sum[Binomial[n - 1, i] b[i], {i, n - 2}]), {n, 3, 20}] (* Eric W. Weisstein, Aug 10 2017 *)

\\ here b(n) is A053530
b(n)={n!*sum(k=1, n, (binomial(k, n-k)*2^(k-n)*(-1)^k + sum(j=1, k, binomial(k, j) *sum(i=j, n-k+j, j^(i-j)/(i-j)!*binomial(k-j, n-i-k+j)*(1/2)^(n-i-k+j)*(-1)^(k-j))))/k!)}
a(n)={my(v=vector(n,i,b(i)));if(n<3,0,v[n]*v[n]+v[n-1]*(v[n-1]+2+2*sum(i=1,n-2,binomial(n-1,i)*v[i])))} \\ Andrew Howroyd, Aug 10 2017

a(n) = A053530(n)^2 + A053530(n-1)*(A053530(n-1) + 2 + 2*Sum{i=1..n-2} binomial(n-1,i)*A053530(i)). - Andrew Howroyd, Aug 10 2017

a(6)-a(8) from Giovanni Resta, Aug 09 2017

Terms a(9) and beyond from Andrew Howroyd, Aug 10 2017

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 5, 22, 119

Offset: 0

Gus Wiseman, Jun 29 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b. A graph is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

			The a(4) = 1 through a(6) = 22 edge-sets:
  {13,24}  {13,14,25}  {13,25,46}
           {13,24,25}  {14,25,36}
           {13,24,35}  {14,26,35}
           {14,24,35}  {15,24,36}
           {14,25,35}  {13,14,15,26}
                       {13,14,25,26}
                       {13,15,24,26}
                       {13,15,26,46}
                       {13,24,25,26}
                       {13,24,25,36}
                       {13,24,26,35}
                       {13,24,35,36}
                       {13,24,35,46}
                       {14,15,26,36}
                       {14,24,35,36}
                       {14,24,35,46}
                       {14,25,35,46}
                       {15,24,35,46}
                       {15,25,35,46}
                       {15,25,36,46}
                       {15,26,35,46}
                       {15,26,36,46}

The non-minimal case is A324327.
Minimal covers are A053530.
Topologically connected graphs are A324327 (covering) or A324328 (all).
Cf. A000108, A006125, A007297, A054726, A136653, A324169, A326210, A326293.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
Table[Length[fasmin[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],Length[crosscmpts[#]]<=1]&]]],{n,0,5}]

A290763 Number of minimal edge covers in the n-sun graph.

Original entry on oeis.org

17, 56, 207, 839, 3579, 16124, 76037, 373772, 1907842, 10080307, 54988156, 308997810, 1785241070, 10586718392, 64343528516, 400271482199, 2545649131486, 16533901290930, 109563921896553, 740108482190948, 5092272608657314, 35661352536071043

Offset: 3

Eric W. Weisstein, Aug 10 2017

nonn

Andrew Howroyd, Minimal edge covers in the n-sun graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover
Eric Weisstein's World of Mathematics, Sun Graph

Cf. A053530, A290933.

b[n_] := b[n] = n!*SeriesCoefficient[Exp[-x-x^2/2 + x*Exp[x]], {x, 0, n}];
a[n_] := Sum[b[i]*Sum[Binomial[j, i]*(2*Binomial[n, 2*j]*(n - j)^(j - i) + Sum[n*Binomial[j + k - 1, j]*Binomial[n - k - 1, 2*k + 2*j - 1]*(n - 2*k - j)^(j - i)/k, {k, 1, (n - 2*j)/3}]), {j, i, n/2}], {i, 0, n/2}];
Table[a[n], {n, 3, 24}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

\\ here b(n) is A053530
b(n)={Vec(serlaplace(exp(-x-1/2*x^2+x*exp(x + O(x^(n+1))))))[n+1]}
a(n) ={sum(i=0, n\2, b(i)*sum(j=i, n\2, binomial(j,i)*(2*binomial(n,2*j)*(n-j)^(j-i) + sum(k=1, (n-2*j)\3, n*binomial(j+k-1,j)*binomial(n-k-1,2*k+2*j-1)*(n-2*k-j)^(j-i)/k) )))} \\ Andrew Howroyd, Aug 13 2017

a(n) = Sum_{i=0..n/2} Sum_{j=i..n/2} binomial(j,i)*A053530(i)*(2*binomial(n,2*j)*(n-j)^(j-i) + Sum_{k=1..(n-2*j)/3} n*binomial(j+k-1,j)*binomial(n-k-1,2*k+2*j-1)*(n-2*k-j)^(j-i)/k). - Andrew Howroyd, Aug 13 2017

a(6)-a(9) from Andrew Howroyd, Aug 11 2017

a(10)-a(24) from Andrew Howroyd, Aug 13 2017

A202081 The number of simple labeled graphs on n nodes whose connected components are cycles, stars, wheels, or paths.

Original entry on oeis.org

1, 1, 2, 8, 46, 298, 2206, 19009, 187076, 2053349, 24800484, 327067043, 4677505768, 72075818159, 1189985755128, 20952274850927, 391829421176768, 7755079821666945, 161926610838369418, 3556807008080385549, 81979632030102053376, 1978135038931568355707

Offset: 0

Geoffrey Critzer, Dec 10 2011

nonn

Here a cycle is of length 3 or more, a star has at least 4 (total) vertices, a wheel has at least 4 (total) vertices, and a path can be an isolated vertex.

R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge 1999, problem 5.15

G. C. Greubel, Table of n, a(n) for n = 0..440

Cf. A001205, A053530, A053531, A011800.

nn = 16; a = x/(2 (1 - x)) + x/2; b = x^4/4! + Sum[(n (n - 2)!/2) x^n/n!, {n, 5, nn}]; c = x Exp[x] - x^3/2 - x^2 - x; d = -x/2 - x^2/4; Range[0, nn]! CoefficientList[Series[Exp[a]*Exp[b]*Exp[c]*Exp[d]/(1 - x)^(1/2), {x, 0, nn}], x]

E.g.f.: exp(x/2+x/(2*(1-x))) * exp(-x^2/2-x^3/4-x^4/8)/(1-x)^(x/2) * exp(-x-x^2-x^3/2 + x*exp(x)) * exp(-x/2-x^2/4)/(1-x)^(1/2). [corrected by Jason Yuen, Feb 17 2025]

A351589 Number of minimal edge covers in the n-cocktail party graph.

Original entry on oeis.org

0, 2, 74, 2228, 100494, 6014932, 453143662, 41921209920, 4639656895118, 603202689990836, 90714189165482310, 15583340701180474312, 3025677781064563172326, 658038493760685537784572, 159065982382639942877853134, 42449055613405195868802686816

Offset: 1

Eric W. Weisstein, Feb 14 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Cf. A053530, A297029, A297474, A351588.

a(n)={my(x=x+O(x^(2*n+1)), p=exp(-x - x^2/2 + x*exp(x)), q=2*exp(x) - 1); sum(k=0, n, (-1)^(n-k)*binomial(n,k)*(2*k)!*polcoef(q^(n-k)*p, 2*k))} \\ Andrew Howroyd, Feb 21 2022

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * (2*k)! * [x^(2*k)] B(n-k,x), where B(k,x) = (2*exp(x) - 1)^k * exp(-x - x^2/2 + x*exp(x)). - Andrew Howroyd, Feb 21 2022

Terms a(5) and beyond from Andrew Howroyd, Feb 21 2022

cp's OEIS Frontend

A369193 Number of labeled simple graphs with n vertices and at most as many edges as covered (non-isolated) vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A001862 Number of forests of least height with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A290716 Number of minimal dominating sets in the n-triangular (Johnson) graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A210655 Number of irreducible coverings by edges of the complete bipartite graph K_{n,n}; main diagonal of A210654.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A290715 Number of minimal edge covers in the n-barbell graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326341 Number of minimal topologically connected chord graphs covering {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A290763 Number of minimal edge covers in the n-sun graph.