login
A331563
Number of labeled cyclic graphs with n edges and 2n vertices.
0
0, 0, 20, 1610, 129654, 11688369, 1194822915, 137766789810, 17758192128830, 2535895233070628, 397875362655895761, 68087081506276861665, 12626853606957534296975, 2523446241515288646389325
OFFSET
1,3
LINKS
Eric Weisstein's World of Mathematics, Paw Graph
FORMULA
a(n) = A331505(2n) - A302112(n).
EXAMPLE
a(4) = 1610 since we have 3 non-isomorphic cyclic graphs with 4 edges and 8 nodes. (See illustration below.)
To compute a(4) we can consult A057500, which provides the number of labeled connected unicycles. Because A057500(4)=15, and knowing that there are 3 labeled squares, we have 15-3 = 12 Paw Graphs [see Weisstein link]. So graph 1 is labeled in 12 * C(8,4) = 840 ways. Graph 2 is labeled in 3* C(8,4) = 210 ways. A105599 gives 10 as the number of labeled forests with 5 nodes and 4 components, so graph 3 is labeled in 10 * C(8,3) = 560 ways. We have 840 + 210 + 560 = 1610.
.
graph 1 graph 2 graph 3 (triangle + forest with
5 nodes and 4 components)
*--* *--* *--* *
| /| | | | / |
|/ | | | |/ |
* * *--* * *
* * * * * * * * * * *
CROSSREFS
KEYWORD
nonn
AUTHOR
Washington Bomfim, Jan 20 2020
STATUS
approved