A245797
The number of labeled graphs of n vertices that have endpoints, where an endpoint is a vertex with degree 1.
Original entry on oeis.org
0, 1, 6, 49, 710, 19011, 954184, 90154415, 16108626420, 5481798833245, 3582369649269620, 4532127781040045649, 11177949079089720090800, 54050029251399545975868271, 514598463471970554205910304780, 9677402372862708729859372687791391
Offset: 1
The generalization to set-systems is
A327228.
BII-numbers of set-systems with minimum degree 1 are
A327105.
Cf.
A001187,
A006129,
A059166,
A059167,
A100743,
A136284,
A327079,
A327098,
A327103,
A327229,
A327230.
-
m = 16;
egf = Exp[x^2/2]*Sum[2^Binomial[n, 2]*(x/Exp[x])^n/n!, {n, 0, m}];
A059167[n_] := SeriesCoefficient[egf, {x, 0, n}]*n!;
a[n_] := 2^(n(n-1)/2) - A059167[n];
Array[a, m] (* Jean-François Alcover, Feb 23 2019 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}] (* Gus Wiseman, Sep 11 2019 *)
A327111
BII-numbers of set-systems with spanning edge-connectivity 1.
Original entry on oeis.org
1, 2, 4, 5, 6, 7, 8, 16, 17, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 88, 89, 90, 91, 96, 97, 98, 99
Offset: 1
The sequence of all set-systems with spanning edge-connectivity 1 together with their BII-numbers begins:
1: {{1}}
2: {{2}}
4: {{1,2}}
5: {{1},{1,2}}
6: {{2},{1,2}}
7: {{1},{2},{1,2}}
8: {{3}}
16: {{1,3}}
17: {{1},{1,3}}
20: {{1,2},{1,3}}
21: {{1},{1,2},{1,3}}
22: {{2},{1,2},{1,3}}
23: {{1},{2},{1,2},{1,3}}
24: {{3},{1,3}}
25: {{1},{3},{1,3}}
28: {{1,2},{3},{1,3}}
29: {{1},{1,2},{3},{1,3}}
30: {{2},{1,2},{3},{1,3}}
31: {{1},{2},{1,2},{3},{1,3}}
32: {{2,3}}
Graphs with spanning edge-connectivity >= 2 are counted by
A095983.
BII-numbers for vertex-connectivity 1 are
A327098.
BII-numbers for non-spanning edge-connectivity 1 are
A327099.
BII-numbers for spanning edge-connectivity 2 are
A327108.
BII-numbers for spanning edge-connectivity >= 2 are
A327109.
Set-systems with spanning edge-connectivity 2 are counted by
A327130.
Graphs with spanning edge-connectivity 1 are counted by
A327145.
Graphs with spanning edge-connectivity 2 are counted by
A327146.
-
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]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Select[Range[0,100],spanEdgeConn[Union@@bpe/@bpe[#],bpe/@bpe[#]]==1&]
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
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}
The non-covering version is
A245797.
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.
-
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,5}]
A327125
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and cut-connectivity k.
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 26, 28, 9, 0, 1, 296, 490, 212, 25, 0, 1, 6064, 15336, 9600, 1692, 75, 0, 1, 230896
Offset: 0
Triangle begins:
1
0 1
1 0 1
4 3 0 1
26 28 9 0 1
296 490 212 25 0 1
After the first column, same as
A327126.
Row sums without the first column are
A001187.
Row sums without the first two columns are
A013922.
-
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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],cutConnSys[Range[n],#]==k&]],{n,0,4},{k,0,n}]
A327114
Number of labeled simple graphs covering n vertices with cut-connectivity 1.
Original entry on oeis.org
0, 0, 0, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040
Offset: 0
Connected non-separable graphs are
A013922.
BII-numbers for cut-connectivity 1 are
A327098.
Set-systems with cut-connectivity 1 are counted by
A327197.
Labeled simple graphs with vertex-connectivity 1 are
A327336.
-
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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]
-
seq(n)={my(g=log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))); Vec(serlaplace(g-intformal(1+log(x/serreverse(x*deriv(g))))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019
A327229
Number of set-systems covering n vertices with at least one endpoint/leaf.
Original entry on oeis.org
0, 1, 4, 50, 3069, 2521782, 412169726428, 4132070622008664529903, 174224571863520492185852863478334475199686, 133392486801388257127953774730008469744261637221272599199572772174870315402893538
Offset: 0
The a(2) = 4 set-systems:
{{1,2}}
{{1},{2}}
{{1},{1,2}}
{{2},{1,2}}
The non-covering version is
A327228.
The specialization to simple graphs is
A327227.
BII-numbers of these set-systems are
A327105.
-
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]==1&]],{n,0,3}]
A327082
BII-numbers of set-systems with cut-connectivity 2.
Original entry on oeis.org
4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 256, 257, 384, 385, 512, 514, 640, 642, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850
Offset: 1
The sequence of all set-systems with cut-connectivity 2 together with their BII-numbers begins:
4: {{1,2}}
5: {{1},{1,2}}
6: {{2},{1,2}}
7: {{1},{2},{1,2}}
16: {{1,3}}
17: {{1},{1,3}}
24: {{3},{1,3}}
25: {{1},{3},{1,3}}
32: {{2,3}}
34: {{2},{2,3}}
40: {{3},{2,3}}
42: {{2},{3},{2,3}}
256: {{1,4}}
257: {{1},{1,4}}
384: {{4},{1,4}}
385: {{1},{4},{1,4}}
512: {{2,4}}
514: {{2},{2,4}}
640: {{4},{2,4}}
642: {{2},{4},{2,4}}
The first term involving an edge of size 3 is 832: {{1,2,3},{1,4},{2,4}}.
BII-numbers for non-spanning edge-connectivity 2 are
A327097.
BII-numbers for spanning edge-connectivity 2 are
A327108.
The cut-connectivity 1 version is
A327098.
The cut-connectivity > 1 version is
A327101.
Covering 2-cut-connected set-systems are counted by
A327112.
Covering set-systems with cut-connectivity 2 are counted by
A327113.
-
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]]]]]]]]];
vertConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Select[Range[0,100],vertConnSys[bpe/@bpe[#]]==2&]
A327336
Number of labeled simple graphs with vertex-connectivity 1.
Original entry on oeis.org
0, 0, 1, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040, 9672967865350359173180572164444160
Offset: 0
The a(2) = 1 through a(4) = 28 edge-sets:
{12} {12,13} {12,13,14}
{12,23} {12,13,24}
{13,23} {12,13,34}
{12,14,23}
{12,14,34}
{12,23,24}
{12,23,34}
{12,24,34}
{13,14,23}
{13,14,24}
{13,23,24}
{13,23,34}
{13,24,34}
{14,23,24}
{14,23,34}
{14,24,34}
{12,13,14,23}
{12,13,14,24}
{12,13,14,34}
{12,13,23,24}
{12,13,23,34}
{12,14,23,24}
{12,14,24,34}
{12,23,24,34}
{13,14,23,34}
{13,14,24,34}
{13,23,24,34}
{14,23,24,34}
Connected non-separable graphs are
A013922.
Set-systems with vertex-connectivity 1 are
A327128.
Labeled simple graphs with cut-connectivity 1 are
A327114.
-
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]]]]]]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],vertConnSys[Range[n],#]==1&]],{n,0,4}]
A327101
BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).
Original entry on oeis.org
4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107
Offset: 1
The sequence of all 2-cut-connected set-systems together with their BII-numbers begins:
4: {{1,2}}
5: {{1},{1,2}}
6: {{2},{1,2}}
7: {{1},{2},{1,2}}
16: {{1,3}}
17: {{1},{1,3}}
24: {{3},{1,3}}
25: {{1},{3},{1,3}}
32: {{2,3}}
34: {{2},{2,3}}
40: {{3},{2,3}}
42: {{2},{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}}
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}}
Positions of numbers >= 2 in
A326786.
2-cut-connected graphs are counted by
A013922, if we assume
A013922(2) = 0.
2-cut-connected integer partitions are counted by
A322387.
BII-numbers for cut-connectivity 2 are
A327082.
BII-numbers for cut-connectivity 1 are
A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are
A327102.
BII-numbers for spanning edge-connectivity >= 2 are
A327109.
Covering 2-cut-connected set-systems are counted by
A327112.
Covering set-systems with cut-connectivity 2 are counted by
A327113.
The labeled cut-connectivity triangle is
A327125, with unlabeled version
A327127.
-
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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]>=2&]
A327127
Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 2, 0, 1, 13, 11, 7, 2, 0, 1
Offset: 0
Triangle begins:
1
0 1
1 0 1
2 1 0 1
5 3 2 0 1
13 11 7 2 0 1
A more standard version (zeros removed) is
A259862.
Showing 1-10 of 15 results.
Comments