Kautz graphs are labeled graphs representing the overlap of strings.
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 e.g. Wikipedia for details.
Author
Gabor Csardi csardi.gabor@gmail.com, the first version in R was written by Vincent Matossian.
Examples
make_line_graph(make_kautz_graph(2, 1))
#> ── <igraph> Line graph ────────────────────────────────────────────── 43e416c ──
#> ℹ directed
#> ℹ 12 vertices · 24 edges
#>
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph: name <chr>
#>
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 5 → 1 9 → 1 5 → 2 9 → 2 6 → 3 10 → 3 6 → 4 10 → 4 1 → 5
#> [10] 11 → 5 1 → 6 11 → 6 2 → 7 12 → 7 2 → 8 12 → 8 3 → 9 7 → 9
#> [19] 3 → 10 7 → 10 4 → 11 8 → 11 4 → 12 8 → 12
make_kautz_graph(2, 2)
#> ── <igraph> Kautz graph 2-2 ───────────────────────────────────────── 0f116ff ──
#> ℹ directed
#> ℹ 12 vertices · 24 edges
#>
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph: name <chr>, m <dbl>, n <dbl>
#>
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 → 5 1 → 6 2 → 7 2 → 8 3 → 9 3 → 10 4 → 11 4 → 12 5 → 1
#> [10] 5 → 2 6 → 3 6 → 4 7 → 9 7 → 10 8 → 11 8 → 12 9 → 1 9 → 2
#> [19] 10 → 3 10 → 4 11 → 5 11 → 6 12 → 7 12 → 8