A321426 -id:A321426 - cp's OEIS frontend

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

R. J. Mathar, Nov 09 2018

nonn

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.

			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.

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

Cf. A002829, A321426.

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

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

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

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

A321427 Number of connected labeled closely cubic graphs on 2n+1 nodes.

Original entry on oeis.org

0, 0, 30, 5670, 2543940, 2147121900, 3060711804150, 6822508357214550, 22450423357516354200, 104310014134397398727400, 660475190873012530467201750, 5537072793132139084007288856750, 60005787711473418534665255077267500, 823803200874542135657355819087997282500

Offset: 0

R. J. Mathar, Nov 09 2018

nonn

Closely cubic graphs are cubic graphs (A002829) where 1 point has degree 2. All other points have degree 3. They are constructed by removing a point from the fairly cubic graphs (A321426).

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. See e.g.f. c(x).

Cf. A002829, A321425, A321426.

nmax = 13;
b[n_] := Sum[Sum[Sum[((-1)^(i + j) (2n)! (2(3n - i - 2j - 3k))!)/(2^(5n - i - 2j - 4k) 3^(2n - i - 2j - k)(3n - i - 2j - 3k)! i! j! k! (2n - i - 2j - 2k)!), {j, 0, Min[Floor[(3n - i - 3k)/2], Floor[(2n - i - 2k)/2]]}], {k, 0, Min[Floor[(3n - i)/3], Floor[(2n - i)/2]]}], {i, 0, 2n}];
seq[n_] := seq[n] = Module[{v = Table[0, {n + 1}]}, For[k = 2, k <= n, k++, v[[k + 1]] = 3k b[k] + 2k(2k - 1) v[[k]] + k(2k - 1)(2k - 2)(2k - 3)v[[k - 1]]]; v];
a[n_] := (2n+1) seq[nmax][[n+1]];
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Nov 23 2018, after Andrew Howroyd *)

a(n) = (2*n+1)*A321426(n). [Wormald eq. (2.2)]

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions