Displaying 1-10 of 14 results found.
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and cut-connectivity k.
+10
18
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
COMMENTS
We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.
EXAMPLE
Triangle begins:
1
0 1
1 0 1
4 3 0 1
26 28 9 0 1
296 490 212 25 0 1
MATHEMATICA
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}]
CROSSREFS
After the first column, same as A327126. Row sums without the first column are A001187. Row sums without the first two columns are A013922.
Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.
+10
17
1, 0, 0, 0, 0, 1, 0, 3, 0, 1, 3, 28, 9, 0, 1, 40, 490, 212, 25, 0, 1, 745, 15336, 9600, 1692, 75, 0, 1
COMMENTS
We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.
EXAMPLE
Triangle begins:
1
0 0
0 0 1
0 3 0 1
3 28 9 0 1
40 490 212 25 0 1
MATHEMATICA
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}]], Union@@#==Range[n]&&cutConnSys[Range[n], #]==k&]], {n, 0, 4}, {k, 0, n}]
CROSSREFS
After the first column, same as A327125. Row sums without the first two columns are A013922.
BII-numbers of set-systems with cut-connectivity 1.
+10
15
1, 2, 8, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 128, 260, 261, 262, 263, 272, 273, 276, 277, 278, 279, 280, 281, 284, 285, 286, 287, 292, 293, 294, 295, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309
COMMENTS
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. We define the cut-connectivity ( A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems ( A326853, A327039), this is the same as vertex-connectivity ( A327334, A327051).
EXAMPLE
The sequence of all set-systems with cut-connectivity 1 together with their BII-numbers begins:
1: {{1}}
2: {{2}}
8: {{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}}
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}}
36: {{1,2},{2,3}}
37: {{1},{1,2},{2,3}}
38: {{2},{1,2},{2,3}}
39: {{1},{2},{1,2},{2,3}}
44: {{1,2},{3},{2,3}}
45: {{1},{1,2},{3},{2,3}}
46: {{2},{1,2},{3},{2,3}}
47: {{1},{2},{1,2},{3},{2,3}}
48: {{1,3},{2,3}}
MATHEMATICA
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[#]]==1&]
CROSSREFS
BII-numbers for cut-connectivity 2 are A327082. BII-numbers for non-spanning edge-connectivity 1 are A327099. BII-numbers for spanning edge-connectivity 1 are A327111. Integer partitions with cut-connectivity 1 are counted by A322390. Labeled connected separable graphs are counted by A327114. Connected separable set-systems are counted by A327197.
BII-numbers of set-systems with non-spanning edge-connectivity 1.
+10
14
1, 2, 4, 7, 8, 16, 22, 23, 25, 28, 29, 30, 31, 32, 37, 39, 42, 44, 45, 46, 47, 49, 50, 51, 57, 58, 59, 64, 67, 73, 74, 75, 76, 77, 78, 79, 82, 83, 90, 91, 97, 99, 105, 107, 128, 256, 262, 263, 278, 279, 280, 281, 284, 285, 286, 287, 292, 293, 294, 295, 300
COMMENTS
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. The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to result in a disconnected or empty set-system.
EXAMPLE
The sequence of all set-systems with non-spanning edge-connectivity 1 together with their BII-numbers begins:
1: {{1}}
2: {{2}}
4: {{1,2}}
7: {{1},{2},{1,2}}
8: {{3}}
16: {{1,3}}
22: {{2},{1,2},{1,3}}
23: {{1},{2},{1,2},{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}}
37: {{1},{1,2},{2,3}}
39: {{1},{2},{1,2},{2,3}}
42: {{2},{3},{2,3}}
44: {{1,2},{3},{2,3}}
45: {{1},{1,2},{3},{2,3}}
46: {{2},{1,2},{3},{2,3}}
MATHEMATICA
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[#]]==1&]
CROSSREFS
Simple graphs with non-spanning edge-connectivity 1 are A327071. BII-numbers for non-spanning edge-connectivity >= 1 are A326749. BII-numbers for non-spanning edge-connectivity 2 are A327097. BII-numbers for spanning edge-connectivity 1 are A327111. BII-numbers for vertex-connectivity 1 are A327114. Covering set-systems with non-spanning edge-connectivity 1 are counted by A327129.
BII-numbers of set-systems with cut-connectivity 2.
+10
12
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
COMMENTS
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. We define the cut-connectivity ( A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems ( A326853, A327039), this is the same as vertex-connectivity ( A327334, A327051).
EXAMPLE
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}}.
MATHEMATICA
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&]
CROSSREFS
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.
Number of labeled simple graphs with vertex-connectivity 1.
+10
12
0, 0, 1, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040, 9672967865350359173180572164444160
COMMENTS
The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton.
EXAMPLE
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}
MATHEMATICA
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}]
CROSSREFS
Connected non-separable graphs are A013922. Set-systems with vertex-connectivity 1 are A327128. Labeled simple graphs with cut-connectivity 1 are A327114.
Number of set-systems covering n vertices with cut-connectivity 1.
+10
8
COMMENTS
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain in a disconnected or empty set-system. Except for cointersecting set-systems ( A327040), this is the same as vertex-connectivity.
FORMULA
Inverse binomial transform of A327128.
EXAMPLE
The a(3) = 24 set-systems:
{12}{13} {1}{12}{13} {1}{2}{12}{13} {1}{2}{3}{12}{13}
{12}{23} {1}{12}{23} {1}{2}{12}{23} {1}{2}{3}{12}{23}
{13}{23} {1}{13}{23} {1}{2}{13}{23} {1}{2}{3}{13}{23}
{2}{12}{13} {1}{3}{12}{13}
{2}{12}{23} {1}{3}{12}{23}
{2}{13}{23} {1}{3}{13}{23}
{3}{12}{13} {2}{3}{12}{13}
{3}{12}{23} {2}{3}{12}{23}
{3}{13}{23} {2}{3}{13}{23}
MATHEMATICA
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], {1, n}]], Union@@#==Range[n]&&cutConnSys[Range[n], #]==1&]], {n, 0, 3}]
CROSSREFS
The BII-numbers of these set-systems are A327098. The same for cut-connectivity 2 is A327113. The non-covering version is A327128. Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327114, A327126, A327229.
BII-numbers of antichains of sets with cut-connectivity 1.
+10
6
1, 2, 8, 20, 36, 48, 128, 260, 272, 276, 292, 304, 308, 320, 516, 532, 544, 548, 560, 564, 576, 768, 784, 788, 800, 804, 1040, 1056, 2064, 2068, 2080, 2084, 2096, 2100, 2112, 2304, 2308, 2324, 2336, 2352, 2560, 2564, 2576, 2596, 2608, 2816, 2820, 2832, 2848
COMMENTS
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. We define the cut-connectivity of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems ( A326853, A327039, A327040), this is the same as vertex-connectivity ( A327334, A327051).
EXAMPLE
The sequence of all antichains of sets with vertex-connectivity 1 together with their BII-numbers begins:
1: {{1}}
2: {{2}}
8: {{3}}
20: {{1,2},{1,3}}
36: {{1,2},{2,3}}
48: {{1,3},{2,3}}
128: {{4}}
260: {{1,2},{1,4}}
272: {{1,3},{1,4}}
276: {{1,2},{1,3},{1,4}}
292: {{1,2},{2,3},{1,4}}
304: {{1,3},{2,3},{1,4}}
308: {{1,2},{1,3},{2,3},{1,4}}
320: {{1,2,3},{1,4}}
516: {{1,2},{2,4}}
532: {{1,2},{1,3},{2,4}}
544: {{2,3},{2,4}}
548: {{1,2},{2,3},{2,4}}
560: {{1,3},{2,3},{2,4}}
564: {{1,2},{1,3},{2,3},{2,4}}
MATHEMATICA
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]]]]]]]]];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 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], stableQ[bpe/@bpe[#], SubsetQ]&&cutConnSys[Union@@bpe/@bpe[#], bpe/@bpe[#]]==1&]
CROSSREFS
BII numbers of antichains with vertex-connectivity >= 1 are A326750. BII-numbers for cut-connectivity 2 are A327082. BII-numbers for cut-connectivity 1 are A327098. Cf. A000120, A000372, A006126, A048143, A048793, A070939, A322390, A326031, A326749, A326751, A327071, A327111.
Number of set-systems with n vertices whose edge-set has cut-connectivity 1.
+10
4
COMMENTS
A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. We define the cut-connectivity ( A326786, A327237, A327126) of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex has cut-connectivity 1. Except for cointersecting set-systems ( A326853, A327039, A327040), this is the same as vertex-connectivity ( A327334, A327051).
MATHEMATICA
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], {1, n}]], cutConnSys[Union@@#, #]==1&]], {n, 0, 3}]
CROSSREFS
The BII-numbers of these set-systems are A327098. Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327113, A327114, A327126, A327229.
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.
+10
4
1, 1, 0, 1, 0, 1, 1, 3, 3, 1, 4, 40, 15, 4, 1, 56, 660, 267, 35, 5, 1, 1031, 18756, 11022, 1862, 90, 6, 1
COMMENTS
We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.
FORMULA
Column-wise binomial transform of A327126.
EXAMPLE
Triangle begins:
1
1 0
1 0 1
1 3 3 1
4 40 15 4 1
56 660 267 35 5 1
MATHEMATICA
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}]], cutConnSys[Union@@#, #]==k&]], {n, 0, 4}, {k, 0, n}]
CROSSREFS
Row sums without the first column are A287689. Cf. A006125, A001187, A013922, A259862, A322389, A326786, A327070, A327114, A327125, A327127, A327198.
Search completed in 0.017 seconds
| 