2
$\begingroup$

A directed random regular graph is a graph where all vertices have exactly $d_{\rm in}$ edges going in and $d_{\rm out}$ going out. If the graph is undirected, i.e. all vertices have degree $d$, then the average number of cycles of length $\ell$ is given by $(d-1)^\ell/2\ell$.

What is the average number of cycles for the directed case?

Note that it cannot be naively $(d_{\rm in}d_{\rm out}-1)^\ell/2\ell$ because for a cycle to form, all edges must be in the same direction.

Edit: I know of two different way to define directed regular graphs:

  1. A $d_{\rm in}d_{\rm out}$-regular graph on $n$ vertices is chosen uniformly from the set of all $d_{\rm in}d_{\rm out}$-regular graphs (i.e., graphs where every vertex has in-degree exactly $d_{\rm in}$ and out-degree exactly $d_{\rm out}$) on $n$ vertices without multiple edges.

  2. A more practical definition is to assign $d_{\rm in} + d_{\rm out}$ stubs to each vertex and connect random pairs of vertices until their in-degree and out-degree are satisfied. This model allows loops and multiple edges but for $n\gg1$ the graph will be locally tree-like.

Improve this question
$\endgroup$
3
  • $\begingroup$ What is a directed random regular graph? How are you using randomness to assign directions to edges of a $d$ regular graph? For instance, just randomly assigning $d_{in}$ out of the $d$ incident edges to be inward will not work as it may create conflicts. $\endgroup$
    – Agile_Eagle
    Commented Jun 6 at 0:59
  • $\begingroup$ If you create the directed random regular graph by taking an undirected random regular graph (however that is defined) and then assigning each edge a random direction, then shouldn't the average number of cycles of length $l$ in the directed case be the same as the average number of cycles of length $l$ in the indirected case, but divided by $2^{l-1}$? As for each choice of random indirected graph and each cycle in it, it has a probability of $2^{1-l}$ of being an oriented cycle. But I would have to see the formal definitions, e.g. I am not sure if your cycles are based at some fixed point $\endgroup$
    – Saúl RM
    Commented Jun 6 at 1:12
  • 2
    $\begingroup$ @SaúlRM, by assigning each edge a random direction you will lose the constraint that each vertex has exactly in-degree $d_{\rm in}$ and out-degree $d_{\rm out}$. Otherwise dividing my naive formula by $2^{l-1}$ would have been sufficient indeed. $\endgroup$
    – stopro
    Commented Jun 6 at 1:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .