A261919
Number of n-node unlabeled graphs without isolated nodes or endpoints (i.e., no nodes of degree 0 or 1).
Original entry on oeis.org
1, 0, 0, 1, 3, 11, 62, 510, 7459, 197867, 9808968, 902893994, 153723380584, 48443158427276, 28363698856991892, 30996526139142442460, 63502034434187094606966, 244852545450108200518282934, 1783161611521019613186341526720, 24603891216946828886755056314074748
Offset: 0
From _Gus Wiseman_, Aug 15 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 graphs (empty columns not shown):
{} {12,13,23} {12,13,24,34} {12,13,24,35,45}
{13,14,23,24,34} {12,14,25,34,35,45}
{12,13,14,23,24,34} {12,15,25,34,35,45}
{13,14,23,24,35,45}
{12,13,24,25,34,35,45}
{13,15,24,25,34,35,45}
{14,15,24,25,34,35,45}
{12,13,15,24,25,34,35,45}
{14,15,23,24,25,34,35,45}
{13,14,15,23,24,25,34,35,45}
{12,13,14,15,23,24,25,34,35,45}
(End)
- F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.
Cf.
A004108 (connected version),
A004110 (version allowing isolated nodes).
-
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1-x^p[[i]], {i, 1, Length[p]}], x, n-k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; b[0] = 1;
a[n_] := b[n] - b[n-1];
a /@ Range[0, 19] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A004110 *)
A327097
BII-numbers of set-systems with non-spanning edge-connectivity 2.
Original entry on oeis.org
5, 6, 17, 20, 24, 34, 36, 40, 48, 53, 54, 55, 60, 61, 62, 63, 65, 66, 68, 71, 72, 80, 86, 87, 89, 92, 93, 94, 95, 96, 101, 103, 106, 108, 109, 110, 111, 113, 114, 115, 121, 122, 123, 257, 260, 272, 308, 309, 310, 311, 316, 317, 318, 319, 320, 326, 327, 342
Offset: 1
The sequence of all set-systems with non-spanning edge-connectivity 2 together with their BII-numbers begins:
5: {{1},{1,2}}
6: {{2},{1,2}}
17: {{1},{1,3}}
20: {{1,2},{1,3}}
24: {{3},{1,3}}
34: {{2},{2,3}}
36: {{1,2},{2,3}}
40: {{3},{2,3}}
48: {{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}}
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}}
65: {{1},{1,2,3}}
66: {{2},{1,2,3}}
68: {{1,2},{1,2,3}}
71: {{1},{2},{1,2},{1,2,3}}
BII-numbers for vertex-connectivity 2 are
A327082.
BII-numbers for non-spanning edge-connectivity 1 are
A327099.
BII-numbers for non-spanning edge-connectivity > 1 are
A327102.
BII-numbers for spanning edge-connectivity 2 are
A327108.
Cf.
A007146,
A048793,
A052446,
A059166,
A070939,
A095983,
A263296,
A322335,
A322338,
A322395,
A326031,
A327041,
A327069,
A327111.
-
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[bpe/@#]]!=1&]];
Select[Range[0,100],edgeConn[bpe[#]]==2&]
A092430
Number of n-node labeled connected mating graphs, cf. A006024.
Original entry on oeis.org
1, 1, 25, 438, 18388, 1409674, 206682994, 58152537184, 31715884061624, 33827568738189576, 71066571962396085656, 295645506683051376527648, 2444503529745123474354656720, 40269655263141217619453414445968
Offset: 2
- Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
-
a(n)={n!*polcoef(log(sum(i=0, n, 2^binomial(i, 2)*log(1+x + O(x*x^n))^i/i!)/(1+x)), n)} \\ Andrew Howroyd, Sep 09 2018
A327102
BII-numbers of set-systems with non-spanning edge-connectivity >= 2.
Original entry on oeis.org
5, 6, 17, 20, 21, 24, 34, 36, 38, 40, 48, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 66, 68, 69, 70, 71, 72, 80, 81, 84, 85, 86, 87, 88, 89, 92, 93, 94, 95, 96, 98, 100, 101, 102, 103, 104, 106, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121
Offset: 1
The sequence of all set-systems with non-spanning edge-connectivity >= 2 together with their BII-numbers begins:
5: {{1},{1,2}}
6: {{2},{1,2}}
17: {{1},{1,3}}
20: {{1,2},{1,3}}
21: {{1},{1,2},{1,3}}
24: {{3},{1,3}}
34: {{2},{2,3}}
36: {{1,2},{2,3}}
38: {{2},{1,2},{2,3}}
40: {{3},{2,3}}
48: {{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}}
56: {{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}}
Graphs with spanning edge-connectivity >= 2 are counted by
A095983.
Graphs with non-spanning edge-connectivity >= 2 are counted by
A322395.
Also positions of terms >=2 in
A326787.
BII-numbers for non-spanning edge-connectivity 2 are
A327097.
BII-numbers for non-spanning edge-connectivity 1 are
A327099.
BII-numbers for spanning edge-connectivity >= 2 are
A327109.
Cf.
A000120,
A048793,
A059166,
A070939,
A263296,
A326031,
A326749,
A327076,
A327101,
A327102,
A327108,
A327148.
-
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConn[y_]:=If[Length[csm[bpe/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[bpe/@#]]!=1&]];
Select[Range[0,100],edgeConn[bpe[#]]>=2&]
A327072
Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.
Original entry on oeis.org
1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0, 11968, 7680, 3600, 2160, 0, 1296, 0, 1047613, 506856, 190365, 68600, 36015, 0, 16807, 0, 169181040, 58934848, 16353792, 4695040, 1433600, 688128, 0, 262144, 0, 51017714393, 12205506096, 2397804444, 500828832, 121706550, 33067440, 14880348, 0, 4782969, 0
Offset: 0
Triangle begins:
1
1 0
0 1 0
1 0 3 0
10 12 0 16 0
253 200 150 0 125 0
Row sums without the first column are
A327071.
-
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[If[n<=1&&k==0,1,Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==k&]]],{n,0,4},{k,0,n}]
-
\\ p is e.g.f. of A053549.
T(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))), v=Vec(1+serreverse(serreverse(log(x/serreverse(x*exp(p))))/exp(x*y+O(x^n))))); vector(#v, k, max(0,k-2)!*Vecrev(v[k], k)) }
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 28 2020
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
The non-connected version is
A327227.
The non-covering version is
A327364.
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
A088974
Number of (nonisomorphic) connected bipartite graphs with minimum degree at least 2 and with n vertices.
Original entry on oeis.org
0, 0, 0, 1, 1, 5, 9, 45, 160, 1018, 6956, 67704, 830392, 13539344, 288643968, 8112651795, 300974046019, 14796399706863, 967194378235406, 84374194347669628, 9856131011755992817, 1546820212559671605395
Offset: 1
Felix Goldberg (felixg(AT)tx.technion.ac.il), Oct 30 2003
Consider n = 4. There is one connected bipartite graph with minimum degree at least 2: the square graph. Also there is one connected point-determining bipartite graph: the graph *--*--*--*. - _Justin M. Troyka_, Nov 27 2013
Cf.
A006024,
A004110 (labeled and unlabeled point-determining graphs [the latter is also unlabeled graphs w/ min. degree >= 2]).
Cf.
A059167 (labeled graphs w/ min. degree >= 2).
Cf.
A092430,
A004108 (labeled and unlabeled connected point-determining graphs [the latter is also unlabeled connected graphs w/ min. degree >= 2]).
Cf.
A059166 (labeled connected graphs w/ min. degree >= 2).
Cf.
A232699,
A218090 (labeled and unlabeled point-determining bipartite graphs).
Cf.
A232700 (labeled connected point-determining bipartite graphs).
A101388
Number of n-vertex unlabeled digraphs without endpoints.
Original entry on oeis.org
1, 1, 1, 8, 137, 7704, 1413982, 855543836, 1775124241697, 12985137979651848, 340909258684048264585, 32512676857544231506934756, 11365672344040389664750137465767, 14668676509227095069116619104786898732, 70315084528883620836175544247562749711989951
Offset: 0
-
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, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
seq(n)=Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^3 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2)) \\ Andrew Howroyd, Jan 22 2021
a(0)=1 prepended and terms a(7) and beyond from
Andrew Howroyd, Jan 22 2021
A101389
Number of n-vertex unlabeled oriented graphs without endpoints.
Original entry on oeis.org
1, 1, 1, 3, 21, 369, 16929, 1913682, 546626268, 406959998851, 808598348346150, 4358157210587930509, 64443771774627635711718, 2636248889492487709302815665, 300297332862557660078111708007894, 95764277032243987785712142452776403618, 85885545190811866954428990373255822969983915
Offset: 0
a(3) = 3 because there are 2 distinct orientations of the triangle K_3 plus the empty graph on 3 vertices.
-
\\ See links in A339645 for combinatorial species functions.
oedges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
ographsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 3^oedges(p) * sMonomial(p)); s/n!}
ographs(n)={sum(k=0, n, ographsCycleIndex(k)*x^k) + O(x*x^n)}
trees(n,k)={sRevert(x*sv(1)/sExp(k*x*sv(1) + O(x^n)))}
cycleIndexSeries(n)={my(g=ographs(n), tr=trees(n,2), tu=tr-tr^2); sSolve( g/sExp(tu), tr )*symGroupSeries(n)}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020
-
\\ faster stand-alone version
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]-1)\2)}
seq(n)={Vec(sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 3^edges(p) * prod(i=1, #p, my(d=p[i]); (1-x^d)^2 + O(x*x^(n-k))) ); x^k*s/k!)/(1-x^2))} \\ Andrew Howroyd, Jan 22 2021
a(0)=1 prepended and terms a(9) and beyond from
Andrew Howroyd, Dec 27 2020
A257947
Number of connected graphs with minimum degree at least 3 and with n vertices.
Original entry on oeis.org
1, 26, 1858, 236926, 53470032, 21496173692, 15580846842786, 20666722709050752, 50987383226899017116, 237747620610010161018672, 2125708489963555363039732518, 36886187432874074894930307867796, 1253964425811022692146824416678500176
Offset: 4
- Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p.404-405.
-
Table[n!*SeriesCoefficient[Log[Sum[2^(k*(k-1)/2)*x^k*Exp[k*x*(x-1-k)/(2*(1+x))]/k!, {k, 0, n}]] - x*(2+x+x^2)/(4*(1+x)) - Log[1+x]/2, {x, 0, n}], {n, 4, 15}]
Comments