The Kautz graph is a
directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 of degree and dimension , which has vertices labeled by all
possible strings of length which are composed of characters chosen from
an alphabet containing distinct
symbols, subject to the condition that adjacent characters in the
string cannot be equal ().

The Kautz graph has edges



It is natural to label each such edge of
as , giving a one-to-one correspondence
between edges of the Kautz graph
and vertices of the Kautz graph
.

Kautz graphs are closely related to De Bruijn graph

De Bruijn graph

In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...

s.

Properties

• For a fixed degree and number of vertices , the Kautz graph has the smallest diameter
  Diameter
  In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...
  
   of any possible directed graph with vertices and degree .

• All Kautz graphs have Eulerian cycles. (An Eulerian cycle is one which visits each edge exactly once-- This result follows because Kautz graphs have in-degree equal to out-degree for each node)

• All Kautz graphs have a Hamiltonian cycle (This result follows from the correspondence described above between edges of the Kautz graph and vertices of the Kautz graph ; a Hamiltonian cycle on is given by an Eulerian cycle on )

• A degree- Kautz graph has disjoint paths from any node to any other node .

In computing

The Kautz graph has been used as a network topology

Network topology

Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....

 for connecting processors in high-performance computing

High-performance computing

High-performance computing uses supercomputers and computer clusters to solve advanced computation problems. Today, computer systems approaching the teraflops-region are counted as HPC-computers.-Overview:...

 and fault-tolerant computing applications: such a network is known as a Kautz network.