A081809 - OEIS

%I #19 Feb 16 2025 08:32:48

%S 1,3,3,10,12,35,58,160,341,958,2444,7242,21190,67217,217335,740542,

%T 2593802,9444080,35383843

%N Number n-cyclic graphs.

%C 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.

%C n-cyclic graphs are distinct simple graphs on which there exists a closed n-walk.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-CyclicGraph.html">k-Cyclic Graph</a>

%H FlowProblem.  <a href="https://web.archive.org/web/20161015202205/http://flowproblem.ru/cycles/explicit-formulae/ck-graphs">C_k-graphs</a>

%e 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:

%e ._.

%e |_| --> |_| + \/ + |

%K nonn,nice,more,hard,changed

%O 3,2

%A Timothy K. Callahan (timcall(AT)math.la.asu.edu), Apr 10 2003

%E More terms from _Eric W. Weisstein_, Jan 08 2014

%E a(18)-a(21) from _Bert Dobbelaere_, Jun 26 2024