1
$\begingroup$

If I have a directed graph with $n$ vertices, and the mean number of out-edges per vertex is $x$, what is the expected number of simple circuits that will be found in the graph?

What happens to the result if we introduce the constraint that each edge can belong to only one circuit?

Thanks in advance.

$\endgroup$
  • $\begingroup$ What, precisely, is the random process by which the edges are drawn? You've specified that the mean number of out-edges per vertex is $x$. Does that mean we just draw $nx$ edges at random in the graph? $\endgroup$ – 6005 Apr 21 '14 at 13:04
  • $\begingroup$ Apologies for leaving out that relevant information. I don't actually know how my real-life graph will look, or what the distribution of edges will be. Is it sufficient for me to say to simply assume a nearly uniform distribution? $\endgroup$ – Sully Apr 22 '14 at 5:07
1
$\begingroup$

There are, on average, $\binom{n-1}{x}$ ways to choose an outgoing neighborhood of $v_{1}$. The vertex $v_{2}$ will be $\binom{n-2}{x-1}$ of these neighborhoods. So simply divide out: $$P( (v_{1}, v_{2}) \in E(G) ) = \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$$

Now for a two-cycle, we want an outgoing arc from $v_{2}$ to $v_{1}$. The probability is the same as we found above, so we multiply. There are $\binom{n}{2} p(C_{2})^{2}$ such cycles we would expect.

For three cycles, we start with by going from $v_{1} \to v_{2}$, with probability $ \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$. We then pick $v_{3}$, and it has the same probability of being in $v_{2}$'s neighborhood.

So now we want the probability of $v_{3}$ having $v_{1}$ in its neighborhood, which is again the same probability as above. So $E(C_{3}) = \binom{n}{3} (\dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} })^{3}$.

Do you see the logic as to how I'm counting? Do you see the pattern to add up?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.