Kautz Graph

Author

Eric W. Weisstein
April 7, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/KautzGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/KautzGraph.html.

©2025 Wolfram Research, Inc. except for portions noted otherwise

Sources

https://en.wikipedia.org/wiki/Kautz_graph

Bermond, J.-C.; Delorme, C.; and Quisquater, J.-J.  ``Strategies for Interconnection Networks: Some Methods from Graph Theory.''  {\it J.\ Parallel and Distributed Comput.} {\bf 3}, 433--449, 1986.

(note Figure 4c in the paper is a de Bruijn graph; not a Kautz graph)

Figure

Labeled

KautzGraph[2,3,VertexLabels->With[{v=VertexList@KautzGraph[2,3]},Thread[v->Row/@v]],BaseStyle->Directive[Black,14,FontFamily->"Times"]]//StyleGraphs

KautzGraph[3,3,VertexLabels->With[{v=VertexList@KautzGraph[3,3]},Thread[v->Row/@v]],BaseStyle->Directive[Black,14,FontFamily->"Times"]]//StyleGraphs

Array

bug(458808): Graph loops are cut off in GraphicsGrid's starting in V14.3

GraphicsGrid[Table[KautzGraph[m,n,PlotLabel->StringReplace[ToString[{m,n}],{"{"->"(","}"->")"}]],{m,2,4},{n,3}]//StyleGraphs[#,VertexSize->{"Scaled",.05}]&,ImageSize->500,Dividers->All,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[Black,14,FontFamily->"Times"]}]

Special cases

<<MathWorld`Graphs`

Table[KautzGraph[m,n,DirectedEdges->False],{m,3,4},{n,2,4}]

TextGrid[
DeleteCases[
Flatten[Table[{{m,n},RecognizeGraph@UndirectedGraph@SimpleGraph@KautzGraph[m,n]},{m,3,5},{n,2,5}],1],
{_,{}}
],
Dividers->All]

Properties

kautz=Table[KautzGraph[m,n],{m,3,5},{n,3,5}];//Timing

Diameter == n

Map[GraphDiameter,kautz,{2}]

EdgeCount

Map[EdgeCount,kautz,{2}]

Eulerian == True

Map[EulerianGraphQ,kautz,{2}]

Hamiltonian == True

Map[HamiltonianGraphQ,kautz,{2}]

MaximumVertexDegree == 2(m-1)

Map[Max[VertexDegree[#]]&,kautz,{2}]

VertexCount == m(((m-1))^(n-1))

Map[VertexCount,kautz,{2}]

Table[m(((m-1))^(n-1)),{m,3,5},{n,3,5}]

VertexDegree

Map[Union@VertexDegree[#]&,kautz,{2}]

Map[Union@VertexDegree[UndirectedGraph@#]&,kautz,{2}]