Kautz graph
Example of Kautz graph on 3 characters with string length 2 (on the left) and 3 (on the right); the edges on the left correspond to the vertices on the right.
The Kautz graph KMN+1displaystyle K_M^N+1
directed graph of degree Mdisplaystyle M
possible strings s0⋯sNdisplaystyle s_0cdots s_N
an alphabet Adisplaystyle A
symbols, subject to the condition that adjacent characters in the
string cannot be equal (si≠si+1displaystyle s_ineq s_i+1
The Kautz graph KMN+1displaystyle K_M^N+1
si∈Asi≠si+1displaystyle ;s_iin A;s_ineq s_i+1,
It is natural to label each such edge of KMN+1displaystyle K_M^N+1
as s0s1⋯sN+1displaystyle s_0s_1cdots s_N+1
between edges of the Kautz graph KMN+1displaystyle K_M^N+1
and vertices of the Kautz graph
KMN+2displaystyle K_M^N+2
Kautz graphs are closely related to De Bruijn graphs.
Properties
- For a fixed degree Mdisplaystyle M
, the Kautz graph has the smallest diameter of any possible directed graph with Vdisplaystyle V
vertices and degree Mdisplaystyle M
- 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 KMNdisplaystyle K_M^N
and vertices of the Kautz graph KMN+1displaystyle K_M^N+1
- A degree-kdisplaystyle k
Kautz graph has kdisplaystyle k
to any other node ydisplaystyle y
.
In computing
The Kautz graph has been used as a network topology for connecting processors in high-performance computing[1] and fault-tolerant computing[2] applications: such a network is known as a Kautz network.
Notes
^ Darcy, Jeff (2007-12-31). "The Kautz Graph". Canned Platypus. External link in|publisher=(help).mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em
^ Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Graph-Theoretic Analysis of Kautz Topology and DHT Schemes". Network and Parallel Computing: IFIP International Conference. Wuhan, China: NPC. pp. 308–315. ISBN 3-540-23388-1. Retrieved 2008-03-05.
This article incorporates material from Kautz graph on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
