Rahul Sharma (Editor)

Kautz graph

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Kautz graph

The Kautz graph K M N + 1 is a directed graph of degree M and dimension N + 1 , which has ( M + 1 ) M N vertices labeled by all possible strings s 0 ⋯ s N of length N + 1 which are composed of characters s i chosen from an alphabet A containing M + 1 distinct symbols, subject to the condition that adjacent characters in the string cannot be equal ( s i ≠ s i + 1 ).

Contents

The Kautz graph K M N + 1 has ( M + 1 ) M N + 1 edges

{ ( s 0 s 1 ⋯ s N , s 1 s 2 ⋯ s N s N + 1 ) | s i ∈ A s i ≠ s i + 1 }

It is natural to label each such edge of K M N + 1 as s 0 s 1 ⋯ s N + 1 , giving a one-to-one correspondence between edges of the Kautz graph K M N + 1 and vertices of the Kautz graph K M N + 2 .

Kautz graphs are closely related to De Bruijn graphs.

Properties

  • For a fixed degree M and number of vertices V = ( M + 1 ) M N , the Kautz graph has the smallest diameter of any possible directed graph with V vertices and degree 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 K M N and vertices of the Kautz graph K M N + 1 ; a Hamiltonian cycle on K M N + 1 is given by an Eulerian cycle on K M N )
  • A degree- k Kautz graph has k disjoint paths from any node x to any other node y .

    • In computing

    The Kautz graph has been used as a network topology for connecting processors in high-performance computing and fault-tolerant computing applications: such a network is known as a Kautz network.

    References

    Kautz graph Wikipedia
    (Text) CC BY-SA


    Similar Topics