igraph (version 0.5.4-1)

graph.kautz: Kautz graphs

Description

Kautz graphs are labeled graphs representing the overlap of strings.

Usage

graph.kautz(m,n)

Arguments

m
Integer scalar, the size of the alphabet. See details below.
n
Integer scalar, the length of the labels. See details below.

Value

  • A graph object.

concept

Kautz graph

Details

A Kautz graph is a labeled graph, vertices are labeled by strings of length n+1 above an alphabet with m+1 letters, with the restriction that every two consecutive letters in the string must be different. There is a directed edge from a vertex v to another vertex w if it is possible to transform the string of v into the string of w by removing the first letter and appending a letter to it. Kautz graphs have some interesting properties, see eg. Wikipedia for details.

See Also

graph.de.bruijn, line.graph

Examples

Run this code
line.graph(graph.kautz(2,1))
graph.kautz(2,2)

Run the code above in your browser using DataCamp Workspace