0
$\begingroup$

I'm looking for the total number of circles, i.e. paths with the same starting- and endpoints but no loops inbetween in a complete, i.e. fully connected directed graph.

From Wolfram Alpha, I got a solution for an undirected, complete graph: http://mathworld.wolfram.com/CompleteGraph.html

I'd really appreciate your help.

Thanks, Chris

  • 1
    Isn't your answer then just twice the number of cycles in the undirected cases (because each of these count once for each direction you walk it in), plus $\frac{n^2-n}{2}$ (for all of the length-2 loops)?2012-04-03
  • 0
    Thanks, but could you verify this, e.g. using a complete graph with 4 nodes? I also don't understand why we need an additional term for length-2 loops. I only want circles without any repetitions in between. Each circle should consist of all vertices, only in different order.2012-04-04
  • 0
    If you restrict your attention to cycles that contain all vertices, the answer is obviously just the number of ways to arrange the $n$ vertices in a sequence -- that is, $n!$. Or $(n-1)!$ if you consider cycles to be identical if they only differ in which node is named the starting/ending one.2012-04-04

1 Answers 1