A361448 Number of connected 3-regular multigraphs on 2n unlabeled nodes rooted at an oriented edge (or loop) whose removal does not disconnect the graph, loops allowed.

1, 2, 10, 66, 511, 4536, 45519, 512661, 6436571, 89505875, 1369509795, 22908806774, 416408493351, 8178599551905, 172690849144538, 3902128758180500, 93970611848528998, 2402929936231885063, 65029668312580777779, 1856984518220396165657, 55803367549204703645086

Offset

0,2

Comments

a(0) = 1 by convention. Loops add two to the degree of a node.

Instead of a rooted edge, the graph can be considered to have a pair of external legs (or half-edges). The external legs add 1 to the degree of a node, but do not contribute to the connectivity of the graph.

The 4-regular version of this sequence is A352174 since removing a single edge from a connected even degree regular graph cannot disconnect the graph.

Links

Table of n, a(n) for n=0..20.

Formula

G.f.: B(x) - x*C(x)^2 where B(x) is the g.f. of A361446 and C(x) is the g.f. of A361412.

Example

a(2) = 10 = A361447(2) + 1 because there is one graph where the orientation of the rooted edge makes a difference:
    1       __
   /| \    |  |
   ||  3---4  |
   \| /    |__|
    2
The nodes are labeled 1,2,3,4. There is a double edge between nodes 1 and 2 and a loop at node 4. Roots at the edges (1,3) and (3,1) are considered different because orientation is considered. Roots at (1,3) and (2,3) are considered the same because the resulting graphs are isomorphic. Roots at (3,4) or (4,3) are disallowed because the removal of that edge would disconnect the graph.

Crossrefs

Cf. A005967 (unrooted), A129427, A352174, A352175, A361412, A361446, A361447.

Sequence in context: A278462 A060206 A277493 * A376226 A346417 A108205

Adjacent sequences: A361445 A361446 A361447 * A361449 A361450 A361451

Keyword

nonn

Author

Andrew Howroyd, Mar 12 2023

Status

approved