For given $n$ and $k$, I am looking for a directed graph with $n$ vertices such that:
- All vertices have in- and out-degree $2$.
- For all vertices $v$ and $w$, the (directed) distance from $v$ to $w$ is at most $k$.
When $n=2^k$, there is an easy construction. On the other hand, $n<2^{k+1}$ is necessary from the out-degree restriction.
My question is: For which $n$ and $k$ do such digraphs exist?
The generalization to other degrees than $2$ may be of additional interest.
[EDIT]
Some clarification in response to a comment:
A solution for $n$ and $k$ is always a solution for all larger $k'$ as well. So I could rephrase the question as follows: Given $n$, what is the smallest $k$ such that a digraph as above exists. The condition $n<2^{k+1}$ gives a lower bound, and in case $n$ is a power of $2$ I have a matching upper bound: Number the vertices from $0$ to $n-1$ and let the edges from vertex $i$ go to $2i\mod n$ and $(2i+1)\mod n$. If $2^k < n < 2^{k+1}$, the same construction can be used to achieve an upper bound of $k+1$, which leaves a gap of $1$ to the lower bound.