To access the full text documents, please follow this link: http://hdl.handle.net/2117/80848

Title:	On cyclic Kautz digraphs
Author:	Böhmová, Katerina; Dalfó Simó, Cristina; Huemer, Clemens
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
Abstract:	A prominent problem in Graph Theory is to find extremal graphs or digraphs with restrictions in their diameter, degree and number of vertices. Here we obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs MCK(d, `) and it is derived from the Kautz digraphs K(d, `). It is well-known that the Kautz digraphs K(d, `) have the smallest diameter among all digraphs with their number of vertices and degree. We define the cyclic Kautz digraphs CK(d, `), whose vertices are 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 6= a`. The cyclic Kautz digraphs CK(d, `) have arcs between vertices a1a2 . . . a` and a2 . . . a`a`+1, with a1 6= a` and a2 6= a`+1. Unlike in Kautz digraphs K(d, `), any label of a vertex of CK(d, `) can be cyclically shifted to form again a label of a vertex of CK(d, `). We give the main parameters of CK(d, `): number of vertices, number of arcs, and diameter. Moreover, we construct the modified cyclic Kautz digraphs MCK(d, `) to obtain the same diameter as in the Kautz digraphs, and we show that MCK(d, `) are d-out-regular. Finally, we compute the number of vertices of the iterated line digraphs of CK(d, `).
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta -Graph theory -Grafs, Teoria de
Rights:	http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Draft Report
Share:

Show full item record