The diameter of cyclic Kautz digraphs
MetadataShow full item record
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ɭ 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.
Is part ofFilomat, 2017, vol. 31, núm. 20, p. 6551-6560
European research projects
Except where otherwise noted, this item's license is described as cc-by-nc-nd (c) Böhmová, Katerina et al., 2017
Showing items related by title, author, creator and subject.
Dalfó, Cristina (World Scientific Publishing, 2018)Kautz digraphs K(d, l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, l) were recently introduced by ...
Dalfó, Cristina (Elsevier, 2017)Kautz digraphs K(d, `) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz CK(d, `) and the subKautz sK(d, 2) digraphs were ...
Comellas, Francesc; Dalfó, Cristina; Fiol, Miguel Angel (Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia, 2013)We study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other ...