A327077 -id:A327077 - cp's OEIS frontend

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

1, 0, 1, 3, 11, 60, 502, 7403, 197442, 9804368, 902818087, 153721215608, 48443044675155, 28363687700395422, 30996524108446916915, 63502033750022111383196, 244852545022627009655180986, 1783161611023802810566806448531, 24603891215865809635944516464394339

Offset: 1

N. J. A. Sloane

Also unlabeled simple graphs with spanning edge-connectivity >= 2. The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices. - Gus Wiseman, Sep 02 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 (terms 1..22 from R. J. Mathar)
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305, Table III.
Eric Weisstein's World of Mathematics, Bridgeless Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
Gus Wiseman, The a(3) = 1 through a(5) = 11 connected bridgeless graphs.

Cf. A005470 (number of simple graphs).
Cf. A007145 (number of simple connected rooted bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263914 (number of simple bridgeless graphs).
Cf. A263915 (number of simple bridged graphs).
The labeled version is A095983.
Row sums of A263296 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Cf. A000719, A001349, A002494, A261919, A327069, A327071, A327074, A327075, A327077, A327109, A327144, A327146.

\\ Translation of theorem 3.2 in Hanlon and Robinson reference. See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); sSolve( gc + gcr^2/2 - sRaise(gcr,2)/2, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 31 2020

a(n) = A001349(n) - A052446(n). - Gus Wiseman, Sep 02 2019

Reference gives first 22 terms.

A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1.

Original entry on oeis.org

0, 0, 1, 3, 28, 475, 14736, 818643, 82367552, 15278576679, 5316021393280, 3519977478407687, 4487518206535452672, 11116767463976825779115, 53887635281876408097483776, 513758302006787897939587736715, 9668884580476067306398361085853696

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

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).

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.

Jean-François Alcover and Vaclav Kotesovec, Table of n, a(n) for n = 0..82 [using A001187 and b-file from A095983]
Eric Weisstein's World of Mathematics, Bridged Graph

Column k = 1 of A327069.
The unlabeled version is A052446.
Connected graphs without bridges are A007146.
The enumeration of labeled connected graphs by number of bridges is A327072.
Connected graphs with exactly one bridge are A327073.
Graphs with non-spanning edge-connectivity 1 are A327079.
BII-numbers of set-systems with spanning edge-connectivity 1 are A327111.
Covering set-systems with spanning edge-connectivity 1 are A327145.
Graphs with spanning edge-connectivity 2 are A327146.
Cf. A001187, A001349, A006125, A059166, A322395, A327071, A327077, A327099, 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],#]==1&]],{n,0,4}]

a(1) = 0; a(n > 1) = A001187(n) - A095983(n).

A052446 Number of unlabeled simple connected bridged graphs on n nodes.

Original entry on oeis.org

0, 1, 1, 3, 10, 52, 351, 3714, 63638, 1912203, 103882478, 10338614868, 1892863194064, 639799762452639, 400857034314325045, 467526363203064793081, 1019286659457016864347582, 4170114225096278323394128049, 32130213534058019378134295287305

Offset: 1

Eric W. Weisstein, May 08 2000

These are unlabeled connected graphs with spanning edge-connectivity 1, where 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, Sep 02 2019

Jean-François Alcover, Table of n, a(n) for n = 1..22
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, Discr. Appl. Math. 201 (2016) 172-181
Eric Weisstein's World of Mathematics, k-Edge-Connected Graph
Eric Weisstein's World of Mathematics, Bridged Graph
Eric Weisstein's World of Mathematics, Connected Graph
Gus Wiseman, The a(2) = 1 through a(5) = 10 connected bridged graphs

Cf. other k-edge-connected unlabeled graph sequences A052446, A052447, A052448, A241703, A241704, A241705.
Cf. A001349 (number of simple connected graphs).
Cf. A007146 (number of simple connected bridgeless graphs).
Cf. A263914 (number of simple bridgeless graphs).
Cf. A263915 (number of simple bridged graphs).
Column k = 1 of A263296.
Row sums of A327077 if the first column is removed.
BII-numbers of set-systems with spanning edge-connectivity 1 are A327111.
The labeled version is A327071.
Cf. A002494, A327069, A327074, A327109, A327144.

A001349 = Cases[Import["https://oeis.org/A001349/b001349.txt", "Table"], {, }][[All, 2]];
A007146 = Cases[Import["https://oeis.org/A007146/b007146.txt", "Table"], {, }][[All, 2]] ;
a[n_] := A001349[[n + 1]] - A007146[[n]];
Array[a, 22] (* Jean-François Alcover, Nov 09 2019 *)

a(n) = A001349(n) - A007146(n).

a(8) and a(9) and better description by Eric W. Weisstein, Nov 07 2010
a(10) from the Encyclopedia of Finite Graphs by Travis Hoppe and Anna Petrone, Apr 22 2014
Additional terms from A001349 and A007146 by Eric W. Weisstein, Oct 29 2015
a(18)-a(22) from A001349 and A007146 by Jean-François Alcover, Nov 09 2019

A327236 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled simple graphs with n vertices whose edge-set has non-spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 1, 4, 5, 10, 8, 5, 1, 1

Offset: 0

Gus Wiseman, Sep 03 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a disconnected or empty graph, ignoring isolated vertices.

			Triangle begins:
  1
  1
  1  1
  1  1  1  1
  2  2  3  3  1
  4  5 10  8  5  1  1

Gus Wiseman, Unlabeled graphs with 5 vertices, organized by non-spanning edge-connectivity (isolated vertices not shown).

Row sums are A000088.
Column k = 0 is A327235.
The labeled version is A327148.
The covering version is A327201.
Spanning edge-connectivity is A263296.
Vertex-connectivity is A259862.
Cf. A322338, A322396, A326787, A327069, A327077, A327097, A327099, A327102, A327200, A327231.

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

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

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 2, 3, 7, 5, 4, 1, 1

Offset: 0

Gus Wiseman, Sep 03 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a disconnected or empty graph, ignoring isolated vertices.

			Triangle begins:
  1
  {}
  0 1
  0 0 1 1
  1 1 2 2 1
  2 3 7 5 4 1 1

Gus Wiseman, Unlabeled graphs covering 5 vertices, organized by non-spanning edge-connectivity.

Row sums are A002494.
Column k = 0 is A327075.
The labeled version is A327149.
Spanning edge-connectivity is A263296.
The non-covering version is A327236 (partial sums).
Cf. A000088, A322338, A322396, A326787, A327076, A327077, A327079, A327126, A327129, A327148, A327235.

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Original entry on oeis.org

0, 0, 1, 0, 12, 200, 7680, 506856, 58934848, 12205506096, 4595039095680, 3210660115278000, 4240401342141499392, 10743530775519296581944, 52808688280248604235191296, 507730995579614277599205009240, 9603347831901155679455061048606720, 358743609478638769812094362544644831968

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

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).

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 12 graphs with exactly one bridge.

Column k = 1 of A327072.
The unlabeled version is A327074.
Connected graphs with no bridges are A007146.
Connected graphs whose bridges are all leaves are A322395.
Connected graphs with at least one bridge are A327071.
Cf. A001187, A006129, A052446, A095983, A327069, A327077, A327108, A327111, A327145, A327146.

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&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==1&]],{n,0,5}]

\\ See A095983.
seq(n)={my(p=x*deriv(log(sum(k=0, n-1, 2^binomial(k, 2) * x^k / k!) + O(x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))^2/2), -(n+1)) } \\ Andrew Howroyd, Dec 28 2020

E.g.f.: (x + Sum_{k>=2} A095983(k)*x^k/(k-1)!)^2/2. - Andrew Howroyd, Aug 25 2019

Terms a(6) and beyond from Andrew Howroyd, Aug 25 2019

A325111 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k articulation vertices, (0 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 3, 2, 1, 0, 0, 10, 7, 3, 1, 0, 0, 56, 33, 17, 5, 1, 0, 0, 468, 244, 101, 32, 7, 1, 0, 0, 7123, 2792, 890, 242, 60, 9, 1, 0, 0, 194066, 52448, 11468, 2461, 527, 97, 12, 1, 0, 0, 9743542, 1690206, 239728, 35839, 6056, 1029, 155, 15, 1, 0, 0

Offset: 0

Andrew Howroyd, Sep 05 2019

Articulation vertices are also called cutpoints. These are vertices that when removed increase the component count of the graph.

			Triangle begins:
     1;
     1     0;
     1,    0,   0;
     1,    1,   0,   0;
     3,    2,   1,   0,  0;
    10,    7,   3,   1,  0, 0;
    56,   33,  17,   5,  1, 0, 0;
   468,  244, 101,  32,  7, 1, 0, 0;
  7123, 2792, 890, 242, 60, 9, 1, 0, 0;
  ...

Eric Weisstein's World of Mathematics, Articulation Vertex

Columns k=0..5 are A002218(n>1), A241767, A241768, A241769, A241770, A241771.
Row sums are A001349.
Cf. A327077, A370064 (labeled version).

Diagonal for k = n inserted by Andrew Howroyd, Feb 25 2024

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Aug 24 2019

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.

			Triangle begins:
    1
    1   0
    0   1   0
    1   0   3   0
   10  12   0  16   0
  253 200 150   0 125   0

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.

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.

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

\\ 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

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

A327074 Number of unlabeled connected graphs with n vertices and exactly one bridge.

Original entry on oeis.org

0, 0, 1, 0, 1, 4, 25, 197, 2454, 48201, 1604016, 93315450, 9696046452, 1822564897453, 625839625866540, 395787709599238772, 464137745175250610865, 1015091996575508453655611, 4160447945769725861550193834, 32088553211819016484736085677320, 467409605282347770524641700949750858

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Unlabeled graphs with no bridges are counted by A007146 (unlabeled graphs with spanning edge-connectivity >= 2).

Gus Wiseman, The a(5) = 4 unlabeled connected graphs with n vertices and exactly one bridge.

The labeled version is A327073.
Unlabeled graphs with at least one bridge are A052446.
The enumeration of unlabeled connected graphs by number of bridges is A327077.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Cf. A001349, A002494, A007146, A263296, A327075, A327111, A327144, A327145.

A007145 = Cases[Import["https://oeis.org/A007145/b007145.txt", "Table"], {, }][[All, 2]];
f[x_] = A007145 . x^Range[lg = Length[A007145]];
(f[x]^2 + f[x^2])/2 + O[x]^lg // CoefficientList[#, x]& (* Jean-François Alcover, Sep 23 2019 *)

G.f.: (f(x)^2 + f(x^2))/2 where f(x) is the g.f. of A007145. - Andrew Howroyd, Aug 25 2019

Terms a(6) and beyond from Andrew Howroyd, Aug 25 2019

cp's OEIS Frontend

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A327071 Number of labeled simple connected graphs with n vertices and at least one bridge, or graphs with spanning edge-connectivity 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A052446 Number of unlabeled simple connected bridged graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327236 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled simple graphs with n vertices whose edge-set has non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A325111 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k articulation vertices, (0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links