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

Author

Andrew Howroyd, Mar 12 2023

Keywords

• nonn

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.

Examples

			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.

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.