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

0

If you're talking about no-directed cycles in a complete directed graph with $n$ nodes, you have that for each $k$ from $2$ to $n$, the number of subsets of nodes of size $k$ is $\binom{n}{k}$, and for each set of $k$ nodes, the number of different cycles using all nodes is $2^{k-1}(k-1)!$, where $(k-1)!$ are the circular permutations and $2^{k-1}$ is given by the fact that you can chose any edge from $ \lbrace (a,b),(b,a)\rbrace $, when $a,b$ are nodes of your subset. Finally, the number of cycles is $$\sum_{k=2}^n\binom{n}{k}2^{k-1}(k-1)!$$ On the other hand, if you want directed cycles only, given a subset of nodes and a permutation there are just two different cycles, so the total number is $$2\sum_{k=2}^n\binom{n}{k}(k-1)!$$