A321425 Number of connected labeled almost cubic graphs on 2n nodes.

0, 0, 6, 630, 232260, 167712300, 207994906350, 409639268108070, 1206311009131027800, 5069191623021896970600, 29288218834810895163954750, 225729928889064072869657010750, 2263331356064784471285438421502700, 28907890013735339531664032407056442500

Offset

0,3

Comments

Almost cubic graphs are cubic graphs (A002829) where 2 points have degree 2 and these 2 points are non-adjacent. All other points have degree 3. They are constructed by removing an edge from the cubic graphs.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..100

N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, e.g.f. a(x).

Formula

a(n) = 3*n*A002829(n). [Wormald eq. (2.1)]

Example

There is 1 unlabeled almost cubic graph on 4 nodes (the kite, obtained by removing an edge of the tetrahedron K_4). This has 6 = binomial(4,2) labeled versions obtained by selecting two out of 4 labels for the points of degree 2.

Mathematica

terms = 14; egf = HypergeometricPFQ[{1/6, 5/6}, {}, 12x/(x^2 + 8x + 4)^(3/2)] Exp[-Log[1/4 x^2 + 2x + 1]/4 - x/3 + (x^2 + 8x + 4)^(3/2)/(24 x) - 1/(3x) - x^2/24 - 1] + O[x]^terms;
CoefficientList[egf, x](2 Range[0, terms-1])! 3 Range[0, terms-1] (* Jean-François Alcover, Nov 23 2018, from A002829 *)

Prog

(PARI) b(n) = sum(i=0, 2*n, sum(k=0, min(floor((3*n-i)/3), floor((2*n-i)/2)), sum(j=0, min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2)), ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!)))); \\ A002829
vector(20, n, n--; 3*n*b(n)) \\ Michel Marcus, Nov 10 2018

Crossrefs

Cf. A002829, A321426.

Sequence in context: A265116 A132928 A055317 * A220858 A337652 A222743

Adjacent sequences: A321422 A321423 A321424 * A321426 A321427 A321428

Keyword

nonn

Author

R. J. Mathar, Nov 09 2018

Extensions

Terms a(11) and beyond from Andrew Howroyd, Nov 09 2018

Status

approved