A007146 -id:A007146 - cp's OEIS frontend

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

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

A322396 Number of unlabeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Original entry on oeis.org

1, 1, 1, 2, 5, 18, 98, 779, 10589, 255790, 11633297, 1004417286, 163944008107, 50324877640599, 29001521193534445, 31396727025729968365, 63969154112074956299242, 245871360738448777028919520, 1787330701747389106609369225312, 24636017249593067184544456944967278

Offset: 0

Gus Wiseman, Dec 06 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..25
Eric Weisstein's World of Mathematics, Graph Bridge
Eric Weisstein's World of Mathematics, Endpoint
Gus Wiseman, The a(5) = 18 simple connected graphs whose bridges are all leaves.

Cf. A001187, A006125, A007146, A013922, A054921, A095983, A322338, A322394, A322395.

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

a(6)-a(10) from Andrew Howroyd, Dec 08 2018

Terms a(11) and beyond from Andrew Howroyd, Dec 31 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

A007145 Number of rooted bridgeless graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 4, 24, 193, 2420, 47912, 1600524, 93253226, 9694177479, 1822463625183, 625829508087155, 395785845695978077, 464137111800208818956, 1015091598240432264958267, 4160447480034069826186309689, 32088552194861245127627790541334

Offset: 1

N. J. A. Sloane

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, terms 21..22 corrected by Andrew Howroyd)
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.

Cf. A004115, A007146.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); sSolve( gcr, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020

Reference gives first 22 terms (terms a(21) and a(22) contain typos).

More terms from R. J. Mathar, Jun 06 2007

A263914 Number of (not necessarily connected) simple bridgeless graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 16, 77, 582, 8002, 205538, 10010657, 912838330, 154634281045, 48597689465264, 28412286324844316, 31024936551325074359, 63533058735488301141874, 244916078109873267213212830, 1783406527132994841804241539063, 24605674622456537969150523621546114

Offset: 1

Eric W. Weisstein, Oct 29 2015

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..30
Eric Weisstein's World of Mathematics, Bridgeless Graph
Eric Weisstein's World of Mathematics, Simple Graph

Cf. A000088 (number of simple graphs).
Cf. A007146 (number of simple connected bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263915 (number of simple bridged graphs).

a(n) = A000088(n) - A263915(n).

Euler transform of A007146. - Falk Hüffner, Jan 18 2016

More terms from A007146 by Falk Hüffner, Jan 18 2016

A263915 Number of (not necessarily connected) simple bridged graphs with n nodes.

Original entry on oeis.org

0, 1, 2, 6, 18, 79, 462, 4344, 69130, 1994511, 106159534, 10456891547, 1904341902688, 641869332391172, 401549418479234409, 467956969039256753054, 1019786043659665470506946, 4171198012616858743636651785, 32134630668466555232483869886654

Offset: 1

Eric W. Weisstein, Oct 29 2015

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..30
Eric Weisstein's World of Mathematics, Bridged Graph
Eric Weisstein's World of Mathematics, Simple Graph

Cf. A000088 (number of simple graphs).
Cf. A007146 (number of simple connected bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263914 (number of simple bridgeless graph).

a(n) = A000088(n) - A263914(n).

More terms using formula by Falk Hüffner, Jan 18 2016

A324227 Number of simple 4-edge-connected non-isomorphic n-vertex graphs.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 29, 424, 15471, 1249951, 187095386, 48211082866

Offset: 1

Jens M. Schmidt, Feb 18 2019

Jens M. Schmidt, Data files in graph6 format

Cf. A007146, A052447.

a(12) added by Georg Grasegger, Jan 07 2025

A324096 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 7.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 4, 100, 10790, 7772555, 12294282710

Offset: 1

Jens M. Schmidt, Feb 18 2019

Jens M. Schmidt, Data files in graph6 format

Column k=7 of A263296.

Cf. A052447, A007146.

A324097 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 8.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 150, 36095, 77299066, 348666442245

Offset: 1

Jens M. Schmidt, Feb 18 2019

Jens M. Schmidt, Data files in graph6 format

Column k=8 of A263296.

Cf. A052447, A007146.

A324098 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 9.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 225, 124046, 835008556

Offset: 1

Jens M. Schmidt, Feb 18 2019

Jens M. Schmidt, Data files in graph6 format

Column k=9 of A263296.

Cf. A052447, A007146.

cp's OEIS Frontend

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

Crossrefs

Programs

Mathematica

PARI

Extensions

A322396 Number of unlabeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A007145 Number of rooted bridgeless graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A263914 Number of (not necessarily connected) simple bridgeless graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A263915 Number of (not necessarily connected) simple bridged graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A324227 Number of simple 4-edge-connected non-isomorphic n-vertex graphs.

Views

Author

Keywords

Links

Crossrefs

Extensions

A324096 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 7.

Views

Author

Keywords

Links

Crossrefs

A324097 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 8.

Views

Author

Keywords

Links

Crossrefs

A324098 Number of simple non-isomorphic n-vertex graphs of edge-connectivity 9.

Views