We present a new kind of digraphs, called cyclic Kautz digraphs CK(d, `), which are subdigraphs of the well-known Kautz digraphs K(d, `). The latter have the smallest diameter among all digraphs with their number of vertices and degree. Cyclic Kautz digraphs CK(d, `) have vertices labeled by all possible sequences a1 . . . a` of length `, such that each character ai is chosen from an alphabet containing d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in...
We present a new kind of digraphs, called cyclic Kautz digraphs CK(d, `), which are subdigraphs of the well-known Kautz digraphs K(d, `). The latter have the smallest diameter among all digraphs with their number of vertices and degree. Cyclic Kautz digraphs CK(d, `) have vertices labeled by all possible sequences a1 . . . a` of length `, such that each character ai is chosen from an alphabet containing d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 , a` . Their arcs are between vertices a1a2 . . . a` and a2 . . . aà`+1, with a1 , a` and a2 , a`+1. We give the diameter of CK(d, `) for all the values of d and `, and also its number of vertices and arcs
Citation
Böhmová, K., Dalfo, C., Huemer, C. The diameter of cyclic Kautz digraphs. "Filomat", 2017, vol. 31, núm. 20, p. 6551-6560.