login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A081809
Number n-cyclic graphs.
0
1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444, 7242, 21190, 67217, 217335, 740542, 2593802, 9444080, 35383843
OFFSET
3,2
COMMENTS
Take the graph of an n-cycle and consider all possible contractions (including no contraction at all) that do not produce self-loops. Then eliminate multiple edges and count the nonisomorphic graphs.
n-cyclic graphs are distinct simple graphs on which there exists a closed n-walk.
LINKS
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, k-Cyclic Graph
FlowProblem. C_k-graphs
EXAMPLE
a(4)=3 because the square loop gives itself and can be folded to give the tree on three vertices and the connected graph on two vertices:
._.
|_| --> |_| + \/ + |
CROSSREFS
Sequence in context: A332955 A355089 A218953 * A359894 A236170 A129885
KEYWORD
nonn,nice,more,hard
AUTHOR
Timothy K. Callahan (timcall(AT)math.la.asu.edu), Apr 10 2003
EXTENSIONS
More terms from Eric W. Weisstein, Jan 08 2014
a(18)-a(21) from Bert Dobbelaere, Jun 26 2024
STATUS
approved