A327128 -id:A327128 - cp's OEIS frontend

A327336 Number of labeled simple graphs with vertex-connectivity 1.

0, 0, 1, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040, 9672967865350359173180572164444160

Offset: 0

Gus Wiseman, Sep 02 2019

nonn

Same as A327114 except a(2) = 1.

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.

			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}

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

Column k = 1 of A327334.
The unlabeled version is A052442.
Connected non-separable graphs are A013922.
Set-systems with vertex-connectivity 1 are A327128.
Labeled simple graphs with cut-connectivity 1 are A327114.
Cf. A006129, A054592, A322389, A322390, A326786, A327070, A327098, A327100, A327125, A327126.

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

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

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

Gus Wiseman, Aug 25 2019

A graph with one vertex and no edges is considered to be connected. Except for complete graphs, this is the same as vertex-connectivity (A259862).

There are two ways to define (vertex) connectivity: the minimum size of a vertex cut, and the minimum of the maximum number of internally disjoint paths between two distinct vertices. For non-complete graphs they coincide, which is tremendously useful. For complete graphs with at least 2 vertices, there are no cuts but the second method still works so it is customary to use it to justify the connectivity of K_n being n-1. - Brendan McKay, Aug 28 2019.

			Triangle begins:
   1
   0  1
   1  0  1
   2  1  0  1
   5  3  2  0  1
  13 11  7  2  0  1

Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.

Row sums are A000088.
Column k = 0 is A000719, if we assume A000719(0) = 1.
Column k = 1 is A052442, if we assume A052442(1) = 1 and A052442(2) = 0.
The labeled version is A327125.
A more standard version (zeros removed) is A259862.
Cf. A052443, A322389, A326786, A327082, A327098, A327100, A327113, A327126, A327128, A327197.

A327113 Number of set-systems covering n vertices with cut-connectivity 2.

Original entry on oeis.org

0, 0, 4, 0, 4752

Offset: 0

Gus Wiseman, Aug 24 2019

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 empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			The a(2) = 4 set-systems:
  {{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

Covering graphs with cut-connectivity >= 2 are A013922, if we assume A013922(2) = 1.
Covering antichains (blobs) with cut-connectivity >= 2 are A275307, if we assume A275307(1) = 0.
2-vertex-connected integer partitions are A322387.
Connected covering set-systems are A323818.
Covering set-systems with cut-connectivity >= 2 are A327112.
The cut-connectivity of the set-system with BII-number n is A326786(n).
BII-numbers of set-systems with cut-connectivity 2 are A327082.
Cf. A002218, A003465, A048143, A259862, A322389, A327101, A327113, A327126, A327128, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]==2&]],{n,0,3}]

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 1, 0, 24, 1984

Offset: 0

Gus Wiseman, Sep 01 2019

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.

			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}

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.

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

Inverse binomial transform of A327128.

cp's OEIS Frontend

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327113 Number of set-systems covering n vertices with cut-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula