El gráfico de Kautz es un gráfico dirigido de grado y dimensión , que tiene vértices etiquetados por todas las posibles cadenas de longitud que están compuestas por caracteres elegidos de un alfabeto que contiene símbolos distintos, sujeto a la condición de que los caracteres adyacentes en la cadena no pueden ser iguales ( ).
El gráfico de Kautz tiene aristas
Es natural etiquetar cada uno de estos bordes
como , dando una correspondencia uno a uno entre los bordes del gráfico de Kautz
y los vértices del gráfico de Kautz .
Para un grado y número fijo de vértices , el grafo de Kautz tiene el diámetro más pequeño de cualquier grafo dirigido posible con vértices y grado .
Todos los grafos de Kautz tienen ciclos eulerianos . (Un ciclo euleriano es aquel que visita cada arista exactamente una vez. Este resultado se deduce porque los grafos de Kautz tienen un grado de entrada igual al grado de salida para cada nodo)
Todos los grafos de Kautz tienen un ciclo hamiltoniano (este resultado se desprende de la correspondencia descrita anteriormente entre los bordes del grafo de Kautz y los vértices del grafo de Kautz ; un ciclo hamiltoniano en está dado por un ciclo euleriano en )
Un gráfico de grado Kautz tiene caminos disjuntos desde cualquier nodo a cualquier otro nodo .
^ Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Análisis de teoría de grafos de la topología de Kautz y los esquemas DHT". Computación en red y paralela: Conferencia internacional IFIP . Wuhan, China: NPC. págs. 308–315. ISBN 3-540-23388-1. Consultado el 5 de marzo de 2008 .