login
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.
3
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.
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
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Mar 12 2023
STATUS
approved