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

%I #57 Jul 23 2023 17:06:20

%S 0,0,0,1,10,253,11968,1047613,169181040,51017714393,29180467201536,

%T 32121680070545657,68867078000231169536,290155435185687263172693,

%U 2417761175748567327193407488,40013922635723692336670167608181,1318910073755307133701940625759574016

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

%C From _Falk Hüffner_, Jun 28 2018: (Start)

%C 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, ...).

%C Labeled version of A007146. (End)

%C 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

%H Jinyuan Wang, <a href="/A095983/b095983.txt">Table of n, a(n) for n = 0..82</a>

%H P. Hanlon and R. W. Robinson, <a href="http://dx.doi.org/10.1016/0095-8956(82)90048-X">Counting bridgeless graphs</a>, J. Combin. Theory, B 33 (1982), 276-305.

%H Gus Wiseman, <a href="/A095983/a095983.png">The a(4) = 10 labeled graphs with spanning edge-connectivity >= 2.</a>

%H Gus Wiseman, <a href="/A095983/a095983_1.png">Non-isomorphic representatives of the a(5) = 253 graphs with spanning edge-connectivity >= 2.</a>

%F a(n) = A001187(n) - A327071(n). - _Gus Wiseman_, Sep 20 2019

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

%t seq[16] (* _Jean-François Alcover_, Aug 13 2019, after _Andrew Howroyd_ *)

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

%t spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]>=2&]],{n,0,5}] (* _Gus Wiseman_, Sep 20 2019 *)

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

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

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

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

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

%o concat([0],v)} \\ _Andrew Howroyd_, Jun 18 2018

%o (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

%Y Cf. A053549, A198046.

%Y The unlabeled version is A007146.

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

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

%Y Graphs with spanning edge-connectivity 2 are A327146.

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

%Y 2-vertex-connected graphs are A013922.

%Y Graphs without endpoints are A059167.

%Y Graphs with spanning edge-connectivity 1 are A327071.

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

%K nonn

%O 0,5

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

%E Name corrected and more terms from _Pavel Irzhavski_, Nov 01 2014

%E Offset corrected by _Falk Hüffner_, Jun 17 2018

%E a(12)-a(16) from _Andrew Howroyd_, Jun 18 2018