Electronic notes in discrete mathematics

Vol. 49, p. 323-330

DOI: 10.1016/j.endm.2015.06.044

Date of publication: 2015-11-12

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 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).]]>

European Conference on Combinatorics, Graph Theory and Applications

Presentation's date: 2015-09-04

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 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 6= al . The cyclic Kautz digraphs CK(d, l) have arcs between vertices a1a2 . . . al and a2 . . . alal+1, with a1 6= al , a2 6= al+1, and ai 6= 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).]]>

Date: 2015

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, `).]]>

Abstract:

Extremal problems in Combinatorics and Graph Theory deal with the study of discrete configurations, which optimize one or several parameters. In this framework, the project includes problems related to the optimization of metric parameters of graphs, to coloring and labeling problems, to connectivity and reliability, isoperimetric problems, to configurations in finite geometries, to symmetric structures, to tilings, to algorithm design and its computational complexity, and to signal processing techniques. All these problems are connected in the framework of the project and are mainly motivated by applications in network design and analysis for communication and multiprocessor systems. In particular, the project considers applications to the study of complex networks and their communication protocols. The project aims at developing applications to these optimization problems of algebraic techniques and of spectral analysis (adjacency and Laplacian matrices), Fourier analysis in Abelian groups and polynomial and probabilistic methods in combinatorics. These techniques complement the combinatorial methods close to the combinatorial nature of the problems under consideration. This project gathers the activity of a well-established research group with almost 30 years of experience and with international projection. Its objectives are inserted into European projects the research group is involved with.]]>

Electronic journal of graph theory and applications

Vol. 3, num. 2, p. 133-145

DOI: 10.5614/ejgta.2015.3.2.3

Date of publication: 2015

Abstract:

We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors).]]>