A054592 -id:A054592

A327069

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

+10
24

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,7

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..27.

EXAMPLE

Triangle begins:

1

1 0

1 1 0

4 3 1 0

26 28 9 1 0

296 475 227 25 1 0

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

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

CROSSREFS

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.

KEYWORD

nonn,tabl,more

AUTHOR

Gus Wiseman, Aug 23 2019

EXTENSIONS

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

STATUS

approved

A327334

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

+10
23

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,7

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

LINKS

Table of n, a(n) for n=0..35.

Wikipedia, k-vertex-connected graph

EXAMPLE

Triangle begins:

1

1 0

1 1 0

4 3 1 0

26 28 9 1 0

296 490 212 25 1 0

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

CROSSREFS

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.

KEYWORD

nonn,tabl,more

AUTHOR

Gus Wiseman, Sep 01 2019

EXTENSIONS

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

STATUS

approved

A327125

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,7

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.

LINKS

Table of n, a(n) for n=0..28.

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.

The unlabeled version is A327127.

Row sums are A006125.

Column k = 0 is A054592, if we assume A054592(0) = 1.

Column k = 1 is A327114, if we assume A327114(1) = 1.

Row sums without the first column are A001187.

Row sums without the first two columns are A013922.

Different from A327069.

Cf. A259862, A322389, A326786, A327082, A327098, A327100, A327101.

KEYWORD

nonn,more,tabl

AUTHOR

Gus Wiseman, Aug 25 2019

EXTENSIONS

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

a(1) and a(2) corrected by Robert Price, May 20 2021

STATUS

approved

A327114

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

+10
15

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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.

LINKS

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

FORMULA

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

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}]], Union@@#==Range[n]&&cutConnSys[Range[n], #]==1&]], {n, 0, 3}]

PROG

(PARI) 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

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 25 2019

STATUS

approved

A327070

Number of non-connected simple labeled graphs covering n vertices.

+10
14

1, 0, 0, 0, 3, 40, 745, 21028, 973889, 80133088, 12523299729, 3847333778244, 2341705361100633, 2821794389863015840, 6728707109106848947081, 31769173063866390661714996, 297278309767391164611330317921

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

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

LINKS

Table of n, a(n) for n=0..16.

FORMULA

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

Inverse binomial transform of A327199.

EXAMPLE

The a(4) = 3 graphs:

{{1,2},{3,4}}

{{1,3},{2,4}}

{{1,4},{2,3}}

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

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[csm[#]]!=1&]], {n, 0, 5}]

CROSSREFS

Column k = 0 of A327149.

The unlabeled version is A327075.

The non-covering version is A327199.

Cf. A000719, A001187, A001349, A002494, A006125, A006129, A054592, A327070.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 24 2019

STATUS

approved

A327075

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

+10
12

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

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

LINKS

Table of n, a(n) for n=0..21.

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

FORMULA

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

EXAMPLE

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}

PROG

(Python)

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<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>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

CROSSREFS

Column k = 0 of A327201.

The labeled version is A327070.

Disconnected graphs are A000719.

Cf. A000088, A001187, A001349, A002494, A006129, A054592.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 26 2019

EXTENSIONS

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

STATUS

approved

A327336

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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.

LINKS

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

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

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.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Sep 02 2019

EXTENSIONS

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

STATUS

approved

A327072

Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.

+10
7

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

COMMENTS

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).

Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.

LINKS

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

Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.

EXAMPLE

Triangle begins:

1

1 0

0 1 0

1 0 3 0

10 12 0 16 0

253 200 150 0 125 0

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

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]]<n||Length[csm[Delete[#, i]]]>1, {i, Length[#]}], True]==k&]]], {n, 0, 4}, {k, 0, n}]

PROG

(PARI) \\ 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

CROSSREFS

Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.

Column k = 1 is A327073.

Column k = n - 1 is A000272.

Row sums are A001187.

The unlabeled version is A327077.

Row sums without the first column are A327071.

Cf. A001349, A007146, A052446, A054592, A059166, A322395, A327069, A327148.

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Aug 24 2019

EXTENSIONS

Terms a(21) and beyond from Andrew Howroyd, Dec 28 2020

STATUS

approved

A327235

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

+10
5

1, 1, 1, 1, 2, 4, 14, 49, 234, 1476, 15405, 307536, 12651788, 1044977929, 167207997404, 50838593828724, 29156171171238607, 31484900549777534887, 64064043979274771429379, 246064055301339083624989655, 1788069981480210465772374023323, 24641385885409824180500407923934750

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

LINKS

Table of n, a(n) for n=0..21.

FORMULA

a(n) = 1 + A000088(n) - Sum_{i = 1..n} A001349(i).

EXAMPLE

The a(4) = 2 through a(6) = 14 edge-sets:

{} {} {}

{12,34} {12,34} {12,34}

{12,35,45} {12,34,56}

{12,34,35,45} {12,35,45}

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

PROG

(Python)

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 A327235(n):

if n == 0: return 1

@lru_cache(maxsize=None)

def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>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))

def a(n): return sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n if n else 1

return 1+b(n)-sum(a(i) for i in range(1, n+1)) # Chai Wah Wu, Jul 03 2024

CROSSREFS

Unlabeled non-connected graphs are A000719.

Partial sums of A327075.

The labeled version is A327199.

Cf. A000088, A001349, A002494, A052446, A054592, A327070, A327071.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Sep 01 2019

EXTENSIONS

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

STATUS

approved

A182100

The number of connected simple labeled graphs with <= n nodes.

+10
3

1, 2, 4, 11, 65, 974, 31744, 2069971, 267270041, 68629753650, 35171000942708, 36024807353574291, 73784587576805254665, 302228602363365451957806, 2475873310144021668263093216, 40564787336902311168400640561099

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..80

FORMULA

a(n) = Sum_{i=0..n} binomial(n,i)*A001187(i).

E.g.f.: exp(x)*A(x) where A(x) is e.g.f. for A001187.

a(n) = A327078(n) + n. - Gus Wiseman, Sep 03 2019

EXAMPLE

From Gus Wiseman, Sep 03 2019: (Start)

The a(0) = 1 through a(3) = 11 edge-sets (singletons represent uncovered vertices):

{} {} {} {}

{{1,2},{1,3}}

{{1,2},{2,3}}

{{1,3},{2,3}}

{{1,2},{1,3},{2,3}}

(End)

MATHEMATICA

nn = 15; g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Exp[x] (Log[g] + 1), {x, 0, nn}], x]

CROSSREFS

The unlabeled version is A292300(n) + 1.

Cf. A001187, A006129, A054592, A287689, A327070, A327075, A327078.

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Apr 11 2012

STATUS

approved