A095983 Number of 2-edge-connected labeled graphs on n nodes.

0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016

Offset: 0

Author

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

Keywords

• nonn

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
• P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.
• 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.

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.

Programs

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

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

PARI

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

Formula

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

Extensions

Name corrected and more terms from Pavel Irzhavski, Nov 01 2014

Offset corrected by Falk Hüffner, Jun 17 2018

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