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

  • 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)!$