login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A327079 Number of labeled simple connected graphs covering n vertices with at least one bridge that is not an endpoint/leaf  (non-spanning edge-connectivity 1). 14
0, 0, 1, 0, 12, 180, 4200, 157920, 9673664, 1011129840, 190600639200, 67674822473280, 46325637863907072, 61746583700640860736, 161051184122415878112640, 824849999242893693424992000, 8317799170120961768715123118080 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

Also labeled simple connected graphs covering n vertices with non-spanning edge-connectivity 1, where 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.

LINKS

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

FORMULA

a(n) = A001187(n) - A322395(n) for n > 2. - Andrew Howroyd, Aug 27 2019

Inverse binomial transform of A327231.

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

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

CROSSREFS

Column k = 1 of A327149.

The non-covering version is A327231.

Connected bridged graphs (spanning edge-connectivity 1) are A327071.

BII-numbers of graphs with non-spanning edge-connectivity 1 are A327099.

Covering set-systems with non-spanning edge-connectivity 1 are A327129.

Cf. A001187, A006129, A052446, A059166, A322395, A327072, A327073, A327148.

Sequence in context: A318245 A051609 A001814 * A013924 A145560 A230345

Adjacent sequences:  A327076 A327077 A327078 * A327080 A327081 A327082

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 25 2019

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 6 18:59 EDT 2020. Contains 334832 sequences. (Running on oeis4.)