A Kautz graph is a regular directed graph derived from a de Bruijn graph on an
alphabet of 
letters using words of length 
by deleting words containing two or more consecutive
identical letters. Allowing 
or 
gives natural degenerate boundary
cases. For example, the 
-Kautz
graph is illustrated above.
-Kautz graphs for 
to 4 and 
to 3 are illustrated above.
The corresponding graphs in Wolfram Language GraphData and the House of Graphs are the underlying undirected simple graphs obtained by forgetting the directions of their arcs.
Kautz graphs are Eulerian and Hamiltonian. The 
-Kautz graph has vertex
count 
,
and every graph vertex has indegree
and outdegree 
. For 
, its directed graph diameter
is 
.
Kautz graphs arise from iterated line digraphs, so the BEST theorem is relevant to counting their directed Hamiltonian cycles via the corresponding Eulerian cycles.
The Kautz graphs have the smallest possible graph diameter among all directed graphs for any fixed outdegree and vertex count.
Problem for Directed Graphs."
Proc. Tenth Int. Symposium Comput. Architecture. Stockholm, Sweden, pp. 174-177,
1983.Fiol, M. A.; Yebra, J L. A.; and Alegre, I. "Line
Digraph Iterations and the 
Digraph Problem." IEEE Trans. Comput. C-33, 400-403, 1984.House
of Graphs. Kautz Graphs. 
Graphs." In Theory of Cellular Logic Networks
and Machines. AFCRL-68-0668, SRI Project 7258, final report, pp. 20-28,
1968.Li, D.; Lu, X.; and Su, J. "Graph-Theoretic Analysis of Kautz
Topology and DHT Schemes." Network and Parallel Computing: IFIP International
Conference. Wuhan, China: NPC, pp. 308-315, 2004.Reddy, S.
M.; Kuhl, J. G.; Hosseini, S. H.; and Lee, H. "On Digraphs with Minimum
Diameter and Maximum Connectivity." Proc. 20th Annual Allerton Conference,
pp. 1018-1026, Oct. 1982.