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. For example, the 
-Kautz graph is illustrated above.
-Kautz graphs for 
to 4 and 
to 3 are illustrated above.
Kautz graphs are Eulerian and Hamiltonian. The 
-Kautz graph has vertex
count 
,
graph diameter 
, and vertex degree 
.
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 degree and number of vertices.
Problem for Directed Graphs."
Proc. Tenth Int. Symposium Comput. Architecture. Stockholm, 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.