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 
.
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.Imase, M. and Itoh, M. "Design to Minimize Diameter on Building-Block Network." IEEE Trans. Comput. C-30, 439-442, 1981.Kautz, W. H. "Bounds on Directed 
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.