# Consultar col·lecció

Per data Per autors Per títols Per matèries

Del document Tot RECERCAT

# El meu RECERCAT

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/85343

 Títol: The diameter of cyclic Kautz digraphs Böhmová, Katerina; Dalfó Simó, Cristina; Huemer, Clemens Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta 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 degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs MCK(d,l) and it is derived from the Kautz digraphs K(d,l). It is well-known that the Kautz digraphs K(d,l) have the smallest diameter among all digraphs with their number of vertices and degree. Here we define the cyclic Kautz digraphs CK(d,l), whose vertices are labeled by all possible sequences a1…al of length l , 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¿al. The cyclic Kautz digraphs CK(d,l) have arcs between vertices a1a2…al and a2…alal+1, with a1¿al, a2¿al+1, and ai¿ai+1 for i=1,…,l-1. The cyclic Kautz digraphs CK(d,l) are subdigraphs of the Kautz digraphs K(d,l). We give the main parameters of CK(d,l) (number of vertices, number of arcs, and diameter). Moreover, we construct the modified cyclic Kautz digraphs MCK(d,l) to obtain the same diameter as in the Kautz digraphs, and we show that MCK(d,l) are d -out-regular. Finally, we compute the number of vertices of the iterated line digraphs of CK(d,l). Àrees temàtiques de la UPC::Matemàtiques i estadísticaGraph theoryDirected graphsKautz digraphsdiameterline digraphspartial line digraphsGrafs, Teoria de http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/submittedVersionArticle

# Documents relacionats

## Altres documents del mateix autor/a

Böhmová, Katerina; Dalfó Simó, Cristina; Huemer, Clemens
Dalfó Simó, Cristina; Huemer, Clemens; Salas Piñon, Julián
Dalfó Simó, Cristina; Huemer, Clemens; Salas, Julian
Dalfó Simó, Cristina; Huemer, Clemens; Salas Piñon, Julián
Böhmová, Katerina

Coordinació

Patrocini