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.

Enumerative Combinatorics, vol. 2, and Exercise 10.8 in my bookAlgebraic Combinatorics, second ed., are devoted to this topic. It's easy to compute the eigenvalues and number of Eulerian tours of $G$. My guess is that a classification is hopeless. The solution to Exercise 5.74 gives a method for constructing such graphs if multiple edges are allowed. $\endgroup$Algebraic Combinatorics! (very good book by the way) I found the problem very interesting and wanted investigate it more deeply, that's why I wanted to know if some research had already been done about it and if some form of classification was realistic. Also I don't see how we could allow multiple edges: doesn't a double edge necessarily create two paths of length k with the same start and end? $\endgroup$without repetition. But the power of the adjacency matrix counts allwalk, that is, with repetition. Is your question about what I refer to as "walks"? $\endgroup$4more comments