A327070 -id:A327070 - cp's OEIS frontend

A327069 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and spanning edge-connectivity k.

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 475, 227, 25, 1, 0, 6064, 14736, 10110, 1782, 75, 1, 0

Offset: 0

Gus Wiseman, Aug 23 2019

The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty graph.

We consider a graph with one vertex and no edges to be disconnected.

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 475 227  25   1   0

Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(1) = 1.
Column k = 1 is A327071.
Column k = 2 is A327146.
The unlabeled version (except with offset 1) is A263296.
Cf. A001187, A095983, A259862, A322338, A326787, A327070, A327072, A327073.

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&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]==k&]],{n,0,5},{k,0,n}]

a(21)-a(27) from Robert Price, May 25 2021

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 490, 212, 25, 1, 0, 6064, 15336, 9600, 1692, 75, 1, 0, 230896, 851368, 789792, 210140, 14724, 231, 1, 0

Offset: 0

Gus Wiseman, Sep 01 2019

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. Except for complete graphs, this is the same as cut-connectivity (A327125).

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 490 212  25   1   0

Wikipedia, k-vertex-connected graph

The unlabeled version is A259862.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = A054592(1) = 1.
Column k = 1 is A327336.
Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.
Row sums without the first two columns are A013922, if we assume A013922(1) = 0.
Cut-connectivity is A327125.
Spanning edge-connectivity is A327069.
Non-spanning edge-connectivity is A327148.
Cf. A322389, A327051, A327070, A327126, A327127, A327350.

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],#]==k&]],{n,0,5},{k,0,n}]

a(21)-a(35) from Robert Price, May 14 2021

A327126 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Aug 25 2019

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.

			Triangle begins:
   1
   0   0
   0   0   1
   0   3   0   1
   3  28   9   0   1
  40 490 212  25   0   1

After the first column, same as A327125.
Column k = 0 is A327070.
Column k = 1 is A327114.
Row sums are A006129.
Different from A327069.
Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.
Row sums without the first two columns are A013922.
Cf. A006125, A259862, A322389, A326786, A327114, A327127, A327198, A327237.

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

a(21)-a(27) from Robert Price, May 20 2021

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

Gus Wiseman, Aug 25 2019

nonn

The cut-connectivity of a graph is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty graph.

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

Column k = 1 of A327126.
The unlabeled version is A052442, if we assume A052442(2) = 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.
Cf. A001187, A054592, A259862, A322389, A322390, A326786, A327070, A327100, A327125.

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

a(n) = A001187(n) - A013922(n), if we assume A001187(1) = 0.

A327075 Number of non-connected unlabeled simple graphs covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 10, 35, 185, 1242, 13929, 292131, 12344252, 1032326141, 166163019475, 50671385831320, 29105332577409883, 31455744378606296280, 64032559078724993894492, 245999991257359808853560276, 1787823917424909126688749033668, 24639597815428343970034635549911427

Offset: 0

Gus Wiseman, Aug 26 2019

nonn

We consider the empty graph to be neither connected (one component) nor disconnected (more than one component).

			Non-isomorphic representatives of the a(0) = 1 through a(6) = 10 graphs (empty columns not shown):
  {}  {12,34}  {12,35,45}     {12,34,56}
               {12,34,35,45}  {12,35,46,56}
                              {12,36,46,56}
                              {13,23,46,56}
                              {12,34,35,46,56}
                              {12,36,45,46,56}
                              {13,23,45,46,56}
                              {12,13,23,45,46,56}
                              {12,35,36,45,46,56}
                              {12,34,35,36,45,46,56}

Gus Wiseman, The a(4) = 1 through a(6) = 10 non-connected covering graphs.

Column k = 0 of A327201.
The labeled version is A327070.
Disconnected graphs are A000719.
Cf. A000088, A001187, A001349, A002494, A006129, A054592.

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A327075(n):
    if n <= 1: return 1-n
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return b(n)-b(n-1)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024

a(n) = A002494(n) - A001349(n), if we assume A001349(0) = A001349(1) = 0.

a(20)-a(21) from Chai Wah Wu, Jul 03 2024

A327146 Number of labeled simple graphs with n vertices and spanning edge-connectivity 2.

Original entry on oeis.org

0, 0, 0, 1, 9, 227

Offset: 0

Gus Wiseman, Aug 27 2019

The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a disconnected or empty graph.

Gus Wiseman, The a(4) = 9 simple graphs with spanning edge-connectivity 2.

Column k = 2 of A327069.
BII-numbers of set-systems with spanning edge-connectivity 2 are A327108.
The generalization to set-systems is A327130.
Cf. A006129, A327070, A327071, A327102, A327109, A327111, A327129, A327144.

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&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]==2&]],{n,0,4}]

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

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

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Original entry on oeis.org

1, 7, 60, 968, 31737, 2069963, 267270032, 68629753640, 35171000942697, 36024807353574279, 73784587576805254652, 302228602363365451957792, 2475873310144021668263093201, 40564787336902311168400640561083, 1329227697997490307154018925966130304

Offset: 2

Eric W. Weisstein, May 29 2017

nonn

Also the number of labeled simple graphs with n vertices whose edge-set is connected. - Gus Wiseman, Sep 11 2019

			From _Gus Wiseman_, Sep 11 2019: (Start)
The a(4) = 60 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}
  {13}  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {14}  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {23}  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {24}  {13,14}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {34}  {13,23}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
        {13,34}  {12,14,34}  {12,14,23,24}
        {14,24}  {12,23,24}  {12,14,23,34}
        {14,34}  {12,23,34}  {12,14,24,34}
        {23,24}  {12,24,34}  {12,23,24,34}
        {23,34}  {13,14,23}  {13,14,23,24}
        {24,34}  {13,14,24}  {13,14,23,34}
                 {13,14,34}  {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}             {12,13,14,23,24,34}
                 {23,24,34}
(End)

Andrew Howroyd, Table of n, a(n) for n = 2..50
Eric Weisstein's World of Mathematics, Triangular Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

The unlabeled version is A292300.

Cf. A001187, A006125, A327070, A327148, A327199, A327235.

Table[With[{g = GraphData[{"Triangular", n}]}, Total[Boole[ConnectedGraphQ[Subgraph[g, #]] & /@ Subsets[VertexList[g]]]]], {n, 2, 5}] - 1
(* Second program: *)
g[n_] := g[n] = If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k) * (n-k-1)/2)*g[k], {k, 1, n-1}]/n]; a[n_] := Sum[Binomial[n, i]*g[i], {i, 2, n}]; Table[a[n], {n, 2, 16}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)

seq(n)={Vec(serlaplace(exp(x + O(x*x^n))*(-x+log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n))))))} \\ Andrew Howroyd, Sep 11 2019

a(n) = Sum_{i=2..n} binomial(n,i) * A001187(i). - Andrew Howroyd, Jun 07 2017
E.g.f.: exp(x)*(-x + log(Sum_{k>=0} 2^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Sep 11 2019
a(n) = A006125(n) - A327199(n). - Gus Wiseman, Sep 11 2019

Terms a(9) and beyond from Andrew Howroyd, Jun 07 2017

A327149 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of simple labeled graphs covering n vertices with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 3, 12, 15, 10, 1, 40, 180, 297, 180, 60, 10, 1

Offset: 0

Gus Wiseman, Aug 27 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty graph.

			Triangle begins:
   1
   {}
   0   1
   0   0   3   1
   3  12  15  10   1
  40 180 297 180  60  10   1

Row sums are A006129.
Column k = 0 is A327070.
Column k = 1 is A327079.
The corresponding triangle for vertex-connectivity is A327126.
The corresponding triangle for spanning edge-connectivity is A327069.
The non-covering version is A327148.
The unlabeled version is A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327097, A327099, A327102, A327125, A327129, A327144.

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]]]]]]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,4},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

A327148(n,k) = Sum_{m = 0..n} binomial(n,m) T(m,k). In words, column k is the inverse binomial transform of column k of A327148.

A327199 Number of labeled simple graphs with n vertices whose edge-set is not connected.

Original entry on oeis.org

1, 1, 1, 1, 4, 56, 1031, 27189, 1165424, 89723096, 13371146135, 3989665389689, 2388718032951812, 2852540291841718752, 6768426738881535155247, 31870401029679493862010949, 297787425565749788134314214272

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

Also graphs with non-spanning edge-connectivity 0.

			The a(4) = 4 edge-sets: {}, {12,34}, {13,24}, {14,23}.

Column k = 0 of A327148.
The covering case is A327070.
The unlabeled version is A327235.
Cf. A001187, A006129, A322395, A326787, A327075, A327076, A327079, A327129, A327200, A327201, A327231, A327236.

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}]],Length[csm[#]]!=1&]],{n,0,5}]

Binomial transform of A327070.

cp's OEIS Frontend

A327069 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A327334 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A327126 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A327075 Number of non-connected unlabeled simple graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A327146 Number of labeled simple graphs with n vertices and spanning edge-connectivity 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Views

Author

Keywords

Comments