login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A095983 Number of 2-edge-connected labeled graphs on n nodes. 37
0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

From Falk Hüffner, Jun 28 2018: (Start)

Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).

Labeled version of A007146. (End)

The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019

LINKS

Jinyuan Wang, Table of n, a(n) for n = 0..82

Gus Wiseman, The a(4) = 10 labeled graphs with spanning edge-connectivity >= 2.

Gus Wiseman, Non-isomorphic representatives of the a(5) = 253 graphs with spanning edge-connectivity >= 2.

FORMULA

a(n) = A001187(n) - A327071(n). - Gus Wiseman, Sep 20 2019

MATHEMATICA

seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];

seq[16] (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)

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

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, 5}] (* Gus Wiseman, Sep 20 2019 *)

PROG

(PARI) \\ here p is initially A053549, q is A198046 as e.g.f's.

seq(n)={my(v=vector(n));

my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));

my(q=x*exp(p)); p-=q;

for(k=3, n, my(c=polcoeff(p, k)); v[k]=c*(k-1)!; p-=c*q^k);

concat([0], v)} \\ Andrew Howroyd, Jun 18 2018

CROSSREFS

Cf. A053549, A198046.

The unlabeled version is A007146.

Row sums of A327069 if the first two columns are removed.

BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.

Graphs with spanning edge-connectivity 2 are A327146.

Graphs with non-spanning edge-connectivity >= 2 are A327200.

2-vertex-connected graphs are A013922.

Graphs without endpoints are A059167.

Graphs with spanning edge-connectivity 1 are A327071.

Cf. A001187, A002218, A052446, A059166, A100743, A322395, A327079, A327144.

Sequence in context: A001536 A114450 A178689 * A059166 A100743 A251588

Adjacent sequences:  A095980 A095981 A095982 * A095984 A095985 A095986

KEYWORD

nonn

AUTHOR

Yifei Chen (yifei(AT)mit.edu), Jul 17 2004

EXTENSIONS

Name corrected and extended by Pavel Irzhavski, Nov 01 2014

Offset corrected by Falk Hüffner, Jun 17 2018

a(12)-a(16) from Andrew Howroyd, Jun 18 2018

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 October 22 19:53 EDT 2019. Contains 328319 sequences. (Running on oeis4.)