Find maximum number of nodes in a regular graph of degree 4 and diameter 2

Question

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find maximum value of $n$?

Answer 1

The answer is $20$. To construct an example with $n=20$, take the graph whose vertices are all pairs $(p,q)$ with different $p,q\in\{1,2,3,4,5\}$, and assume there is an edge from $(i,j)$ to $(k,l)$ if and only if $j=k$. It is clear that $(i,j)\to(j,k)\to(k,l)$ is a path from $(i,j)$ to $(k,l)$ if $j\neq k$.

Clearly, the number of vertices that can be attained from certain $u$ by paths of length $k$ is at most $\mathrm{outdegree}^k$, so that the upper bound is $4^0+4^1+4^2=21$. (Actually, this was a comment by Jorge Fernández.) To see that this bound cannot be attained is harder, see this paper for the proof.