Digraphs with unique walk of length $k$ between any two vertices Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices.
Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $1$.
Then it is not too hard to show, using algebraic methods, that the number of vertices is $d^k$ for some integer $d$, that each vertex has indegree and outdegree $d$ and that $G$ has $d$ loops. Let's call such a digraph a $(d,k)$-nice digraph.
A simple example of a $(d,k)$-nice digraph is the de Bruijn graph for words of lenght $k$ over an alphabet of $d$ symbols. Note also that, if $G$ is a $(d,k)$-nice digraph, then the line digraph of $G$ is a $(d,k+1)$-nice digraph.
There are however, other examples than de Bruijn graphs. The following digraph, for example, is $(3,2)$-nice: http://graphonline.ru/en/?graph=iuDxicdebMgXCAFE. This example is, unfortunately, very asymmetric and doesn't seem to have a simple interpretation like de Bruijn graphs.
My questions are:

*

*Does this class of digraphs have already been studied?

*Is there a way to classify all $(d,k)$-nice graphs?

*If there is no simple classification in the general case (which seems plausible given the irregular example I gave), can we hope to have a classification for specific values of $d$? In particular, can we find examples of $(2,k)$-nice digraphs that are not de Bruijn?

*Are there any other interesting properties that we can prove that these digraphs have?

 A: Your irregular $(3,2)$-nice graph is almost a De Bruijn graph.
Label the vertices ($0$ to $8$) with $12,21,11,22,10,02,20,01,00.$ Then the deviations are that your edges $$1\rightarrow 6 \ \&\  3\rightarrow 4 \mbox{ should be switched to edges } 1\rightarrow 4\ \& \ 3\rightarrow 6.$$  i.e. $$21\rightarrow 20\ \&\ 22\rightarrow 10  \mbox{ should be switched to  }21\rightarrow 10\ \&\ 22\rightarrow 20. $$ You might think about similar switching. Given the $(d,k)$-nice De Bruijn Graph, consider all switches of $$p_1 \rightarrow q_1\ \& \ p_2 \rightarrow q_2 \mbox{ to } p_1 \rightarrow q_2\ \&\ p_2 \rightarrow q_1 $$which preserve $(d,k)$-niceness. Do the same for each of the resulting graphs. In the end you might have a digraph with nodes labelled by (some) $(d,k)$ nice graphs, maybe all. This might allow the generation of these graphs.
Is it the case that the $d$ loops must stay fixed? What about the $\binom{d}{2}$ digons like $ ab \leftrightarrow ba$ for $k=2$ or $aba \leftrightarrow bab$ for $k=3?$
LATER Here is an elaboration in a more general context. It is essentially trivial as I give it here. The question is if it is useful for this problem.
Without being too specific about the setting (I'll suggest one below), fix $d,k$ and let $\mathcal{N}=\mathcal{N}_{d,k}$ be the family of (labelled) $(d,k)$-nice digraphs. This is  a (rather) special subfamily of $\mathcal{D}=\mathcal{D}_{d,k}$ the family of digraphs with $d^k$ vertices each of indegree=outdegree=$d.$
For $G,H \in \mathcal{D}$ there is some $\ell  \geq 2$ such that $G$ has $\ell$ edges not in $H$ and $H$ has $\ell$ edges not in $G.$   We can change $G$ into $H$ by a single $\ell$-"switch."  Call a $2$-switch simply a switch. This means replacing two edges shown in red with two shown in blue or vice versa.

We can create a graph whose vertices are labelled by the members of $\mathcal{D}$ with an edge between pairs which can be obtained by a switch. This graph is connected.
But what use is all this for $\mathcal{N}?$ We can certainly move around in $\mathcal{N}$ using $\ell$-switches of various sizes $\ell$. The question is if we can do so with $2$-switches or maybe $d-1$-switches?
SETTING: Here is one possibility. Since we are interested in $\mathcal{N}$ and the appropriate De Bruijn graph seems very distinguished, let's start there. Let's always label the vertices with length $k$ words over a $d$-letter alphabet. Since there are exactly $d$ vertices with loops, label them with the constant words.
So that is a start: Perhaps consider only digraphs with $d^k$ vertices each of indegree=outdegree=$d$ labelled by the words of length $k$ in $\{0,1,\cdots,d-1\}$ Having exactly $d$ loops which occur at the vertices labelled by constant words. Consider only $\ell$ switches which do not create or destroy loops.
Further regularities could be required. The unique walk of length $k$ between two of those now labelled points must actually be the shortest path between them (any shorter path can be augmented to a walk in several ways by loops at the start or end.) Do these $d(d-1)$ paths necessarily need to be internally disjoint? I want to say yes, but I'm not sure. If so, then, as in the De Bruijn graph, we can decree that the labels on the $d(d-1)(d-2)$ internal points are labeled with the words of the form $xx\cdots xyy\cdots y.$ And, again if this is true, we could consider those edges unswitchable.
