Discrete applied mathematics

DOI: 10.1016/j.dam.2018.12.016

Date of publication: 2019-01-11

Abstract:

A new general family of mixed graphs is presented, which generalizes both the pancake graphs and the cycle prefix digraphs. The obtained graphs are vertex transitive and, for some values of the parameters, they constitute the best infinite families with asymptotically optimal (or quasi-optimal) diameter for their number of vertices]]>

Linear algebra and its applications

Vol. 569, p. 1-14

DOI: 10.1016/j.laa.2018.12.035

Date of publication: 2019

Abstract:

This is a survey on some known properties of the possible Moore graph (or graphs) ¿ with degree 57 and diameter 2. Moreover, we give some new results about it, such as the following. When we consider the distance partition of ¿ induced by a vertex subset C, the following graphs are distance-regular: The induced graph of the vertices at distance 1 from C when C is a set of 400 independent vertices; the induced graphs of the vertices at distance 2 from C when C is a vertex or an edge, and the line graph of ¿. Besides, ¿ is an edge-distance-regular graph.]]>

Journal of algebraic combinatorics

DOI: 10.1007/s10801-018-0862-y

Date of publication: 2019-01

Abstract:

We present a method to derive the complete spectrum of the lift Ga of a base digraph G, with voltage assignment a on a (finite) group G. The method is based on assigning to G a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Ga. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lov´asz and Babai concerning the spectra of Cayley digraphs]]>

Discrete applied mathematics

DOI: 10.1016/j.dam.2018.10.040

Date of publication: 2018-12-07

Abstract:

We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift Ga of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents Ga. In particular, such a matrix gives the quotient matrix of a regular partition of Ga, and when the involved group is Abelian, it completely determines the spectrum of Ga. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph]]>

Discrete mathematics

DOI: 10.1016/j.disc.2018.08.020

Date of publication: 2018-09-11

Abstract:

For a given graph G = (V, E), the degree mean rate of an edge uv ¿ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randic index of G in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randic index for graphs with order n large enough, when the minimum degree d is greater than (approximately) ¿1/3 , where ¿ is the maximum degree. As a by-product, this proves that almost all random (Erdos–Rényi) graphs satisfy the conjecture]]>

Discrete mathematics

Vol. 341, num. 10, p. 2872-2877

DOI: 10.1016/j.disc.2018.06.016

Date of publication: 2018-07

Abstract:

A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a complete enumeration of all optimal (1, 1)-regular mixed graphs with diameter three is presented, so proving that, in general, the proposed bound cannot be improved.]]>

Linear and multilinear algebra

DOI: 10.1080/03081087.2018.1491944

Date of publication: 2018-07

Abstract:

We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs G (among regular graphs with few distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex, where d+ 1 is the number of different eigenvalues of G. This can be seen as another version of the so-called spectral excess theorem, which characterizes in a similar way those regular graphs that are distance-regular.]]>

Journal of interconnection networks

Vol. 18, num. 2-3, p. 1-16

DOI: 10.1142/S0219265918500068

Date of publication: 2018-06-01

Abstract:

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 Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d,l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d,l) and CK(d,l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d,l) and CK(d,l) are maximally vertex-connected and super-edge-connected. Whereas K(d,l) are optimal with respect to the diameter, we show that sK(d,l) and CK(d,l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d,l) and sK(d,l)]]>

Journal of graph theory

Vol. 89, num. 4, p. 386-394

DOI: 10.1002/jgt.22257

Date of publication: 2018-04-24

Abstract:

Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore-like bound is attained in the case of diameter k = 3, and that bipartite mixed graphs of diameter k = 4 do not exist

Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore-like bound is attained in the case of diameter k = 3, and that bipartite mixed graphs of diameter k ≥ 4 do not exist.]]>

Workshop on Graph Spectra, Combinatorics and Optimization

p. 38-39

Presentation's date: 2018-01-27

Workshop on Graph Spectra, Combinatorics and Optimization

p. 56

Presentation's date: 2018-01-27

Workshop on Graph Spectra, Combinatorics and Optimization

p. 90

Presentation's date: 2018-01-26

Abstract:

We present a method to derive the complete spectrum of the lift $\Gamma^{\alpha}$ of a base digraph $\Gamma$, with coltage assignments on a (finite) group $G$. The method is based on assigning to $\Gamma$ a quotient-like matrix whose entries are elements of the group algebra $C[G]$, which fully represents $\Gamma^{\alpha}$.]]>

Electronic journal of graph theory and applications

Vol. 6, num. 2, p. 282-305

Date of publication: 2018

Abstract:

A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Hall’s Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks.

Published in: Electronic journal of graph theory and applications (http://www.ejgta.org)]]>

Linear algebra and its applications

Vol. 531, p. 210-219

DOI: 10.1016/j.laa.2017.05.046

Date of publication: 2017-10-15

Abstract:

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 CK(d,l) and the subKautz sK(d,2) digraphs were recently introduced by Böhmová, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz sK(d,2) and cyclic Kautz CK(d,3) digraphs, for all d=3, through the Hoffman–McAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity.]]>

The australasian journal of combinatorics

Vol. 69, num. 3, p. 368-374

Date of publication: 2017-10

Abstract:

We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift Ga of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents Ga. In particular, such a matrix gives the quotient matrix of a regular partition of Ga, and when the involved group is Abelian, it completely determines the spectrum of Ga. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph.

We study the relationship between two key concepts in the theory of digraphs, those of quotient digraphs and voltage digraphs. These techniques contract or expand a given digraph in order to study its characteristics,or to obtain more involved structures. As an application, we relate the spectrum of a digraph Γ, called a voltage digraph or base, with the spectrum of its lifted digraph Γα. We prove that all the eigenvalues of Γ (including multiplicities) are, in addition, eigenvalues of Γα. This study is carried out by introducing several reduced matrix representations of Γα. As an example of our techniques, we study some basic properties of the Alegre digraph and its base.]]>

Algebraic and Extremal Graph Theory Conference

p. 10

Presentation's date: 2017-08-10

Abstract:

We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift $\Gamma^\alpha$ of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents $\Gamma^\alpha$. In particular, such a matrix gives the quotient matrix of a regular partition of $\Gamma^\alpha$, and when the involved group is Abelian, it completely determines the spectrum of $\Gamma^\alpha$. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph.]]>

Algebraic and Extremal Graph Theory Conference

p. 1-10

Presentation's date: 2017-08-07

Encuentro Conjunto Real Sociedad Matemática Española - Sociedad Matemática Mexicana

p. 184

Presentation's date: 2017-06-20

Journal of graph theory

Vol. 85, num. 2, p. 395-399

DOI: 10.1002/jgt.22068

Date of publication: 2017-06

Abstract:

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices n_k of the k-iterated line digraph L_k(G), for k>= 0, where L_0(G) = G. We obtain this result by using the minimal polynomial of a quotient digraph pi(G) of G. We show some examples of this method applied to the so-called cyclic Kautz, the unicyclic, and the acyclic digraphs. In the first case, our method gives the enumeration of the ternary length-2 squarefree words of any length.]]>

Date: 2017

Abstract:

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 Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d,l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d,l) and CK(d,l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d,l) and CK(d,l) are maximally vertex-connected and super-edge-connected. Whereas K(d,l) are optimal with respect to the diameter, we show that sK(d,l) and CK(d,l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d,l) and sK(d,l).

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 Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d,l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d,l) and CK(d,l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d,l) and CK(d,l) are maximally vertex-connected and super-edge-connected. Whereas K(d,l) are optimal with respect to the diameter, we show that sK(d,l) and CK(d,l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d,l) and sK(d,l)]]>

Abstract:

Networks are present in our lives in numerous different environments: to name just a few, networks can model social relationships, they can model the Internet and links between web pages, they might model the spread of a virus infection between people, and they might represent computer processors/sensors that have to exchange information. This project aims to obtain new insights into the behaviour of networks, which are studied from a geometric and computational perspective. Thereto, the project brings together researchers from different areas such as computational geometry, discrete mathematics, graph drawing, and probability. Among of the topics of research are enumerative problems on geometric networks, crossing numbers, random networks, imprecise models of data, restricted orientation geometry. Combinatorial approaches are combined with algorithms. Algorithmic applications of networks are also studied in the context of unmanned aerial vehicles (UAVs) and in the context of musical information retrieval (MIR). The project contains the work packages: “Geometric networks”, ""Stochastic Geometry and Networks"", “Restricted orientation geometry”, “Graph-based algorithms for UAVs and for MIR”, and “Dissemination and gender equality promotion”. The project connects researchers from 14 universities located in Austria, Belgium, Canada, Chile, Czech Republic, Italy, Mexico, and Spain, who will collaborate and share their different expertise in order to obtain new knowledge on the combinatorics of networks and applications.]]>

Linear algebra and its applications

Vol. 529, p. 391-396

DOI: 10.1016/j.laa.2017.04.036

Date of publication: 2017

Abstract:

We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs.

We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well- known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs]]>

Filomat

Vol. 31, num. 20, p. 6551-6560

DOI: 10.2298/FIL1720551B

Date of publication: 2017

Abstract:

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

The australasian journal of combinatorics

Vol. 69, num. 3, p. 323-333

Date of publication: 2017

Abstract:

In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show the close relationship between lifted digraphs of voltage digraphs and line digraphs, which are two known ways to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs, namely, the De Bruijn and Kautz digraphs, where it is shown that both families can be seen as lifts of smaller De Bruijn digraphs with appropriate voltage assignments.

We study the relationship between two key concepts in the theory of digraphs, those of quotient digraphs and voltage digraphs. These techniques contract or expand a given digraph in order to study its characteristics,or to obtain more involved structures. As an application, we relate the spectrum of a digraph Γ, called a voltage digraph or base, with the spectrum of its lifted digraph Γα. We prove that all the eigenvalues of Γ (including multiplicities) are, in addition, eigenvalues of Γα. This study is carried out by introducing several reduced matrix representations of Γα. As an example of our techniques, we study some basic properties of the Alegre digraph and its base.]]>

Discrete applied mathematics

Vol. 219, p. 110-116

DOI: 10.1016/j.dam.2016.10.030

Date of publication: 2016-12

Abstract:

A mixed graph can be seen as a type of digraph containing some edges (or two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and literated line digraphs. These structures are proven to be useful in the problem of constructing dense graphs or digraphs, and this is related to the degree/diameter problem. Thus, our generalized approach gives rise to graphs that have also good ratio order/diameter. Moreover, we propose a general method for obtaining a sequence mixed diagraph by identifying some vertices of certain iterated line digraph. As a consequence, some results about distance-related parameters (mainly, the diameter and the average distance) of sequence mixed graphs are presented.]]>

International Workshop on Combinatorial and Computational Aspects of Optimization, Topology and Algebra

p. 12-13

Presentation's date: 2016-11-29

Distance in graphs 2016. A conference to celebrate the life and work of Mirka Miller

Presentation's date: 2016-07-20

Distance in graphs 2016. A conference to celebrate the life and work of Mirka Miller

Presentation's date: 2016-07-20

International Workshop on Optimal Network Topologies

p. 20

Presentation's date: 2016-07-14

Linear algebra and its applications

Vol. 500, p. 52-62

DOI: 10.1016/j.laa.2016.03.014

Date of publication: 2016-07-01

Abstract:

A digraph Gamma = (V, E) is a line digraph when every pair of vertices u, v is an element of V have either equal or disjoint in -neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that Gamma is a locally line digraph. In this paper we give a new method to obtain a digraph Gamma' cospectral with a given locally line digraph Gamma with diameter D, where the diameter D' of Gamma' is in the interval [D - 1, D + 1]. In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers. (C) 2016 Elsevier Inc. All rights reserved.]]>

GraphMasters Workshop

Presentation's date: 2016-01-30

Date: 2016

Abstract:

In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show their close relationship between voltage digraphs and line digraphs, which are two known approaches to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs. Namely, De Bruijn and Kautz digraphs.]]>

Journal of physics A. Mathematical and theoretical

Vol. 49, num. 22, p. 1-19

DOI: 10.1088/1751-8113/49/22/225202

Date of publication: 2016

Abstract:

It has been shown that many networks associated with complex systems are small-world (they have both a large local clustering coefficient and a small diameter) and also scale-free (the degrees are distributed according to a power law). Moreover, these networks are very often hierarchical, as they describe the modularity of the systems that are modeled. Most of the studies for complex networks are based on stochastic methods. However, a deterministic method, with an exact determination of the main relevant parameters of the networks, has proven useful. Indeed, this approach complements and enhances the probabilistic and simulation techniques and, therefore, it provides a better understanding of the modeled systems. In this paper we find the radius, diameter, clustering coefficient and degree distribution of a generic family of deterministic hierarchical small-world scale-free networks that has been considered for modeling real-life complex systems.]]>

Electronic journal of combinatorics

Vol. 23, num. 1, p. 1-23

Date of publication: 2016

Abstract:

The (¿,D)(¿,D) (degree/diameter) problem consists of finding the largest possible number of vertices nn among all the graphs with maximum degree ¿¿ and diameter DD. We consider the (¿,D)(¿,D) problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the (¿,2)(¿,2) problem, the number of vertices is n=¿+2n=¿+2; and for the (¿,3)(¿,3) problem, n=3¿-1n=3¿-1 if ¿¿ is odd and n=3¿-2n=3¿-2 if ¿¿ is even. Then, we prove that, for the general case of the (¿,D)(¿,D) problem, an upper bound on nn is approximately 3(2D+1)(¿-2)¿D/2¿3(2D+1)(¿-2)¿D/2¿, and another one is C(¿-2)¿D/2¿C(¿-2)¿D/2¿ if ¿=D¿=D and CC is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on nn for maximal planar bipartite graphs, which is approximately (¿-2)k(¿-2)k if D=2kD=2k, and 3(¿-3)k3(¿-3)k if D=2k+1D=2k+1, for ¿¿ and DD sufficiently large in both cases.

The (Δ,D)(Δ,D) (degree/diameter) problem consists of finding the largest possible number of vertices nn among all the graphs with maximum degree ΔΔ and diameter DD. We consider the (Δ,D)(Δ,D) problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the (Δ,2)(Δ,2) problem, the number of vertices is n=Δ+2n=Δ+2; and for the (Δ,3)(Δ,3) problem, n=3Δ−1n=3Δ−1 if ΔΔ is odd and n=3Δ−2n=3Δ−2 if ΔΔ is even. Then, we prove that, for the general case of the (Δ,D)(Δ,D) problem, an upper bound on nn is approximately 3(2D+1)(Δ−2)⌊D/2⌋3(2D+1)(Δ−2)⌊D/2⌋, and another one is C(Δ−2)⌊D/2⌋C(Δ−2)⌊D/2⌋ if Δ≥DΔ≥D and CC is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on nn for maximal planar bipartite graphs, which is approximately (Δ−2)k(Δ−2)k if D=2kD=2k, and 3(Δ−3)k3(Δ−3)k if D=2k+1D=2k+1, for ΔΔ and DD sufficiently large in both cases.]]>

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

GraphMasters Workshop

Presentation's date: 2014-11-01

Discrete Mathematics Days

p. 271-279

Presentation's date: 2014-07

Abstract:

The (A,D) (degree/diameter) problem consists of finding the largest possible number of vertices n among all the graphs with maximum degree and diameter D. We consider the (A ,D) problem for maximal planar bipartite graphs, that are simple planar graphs in which every face is a quadrangle. We obtain that for the (, 2) problem, the number of vertices is n = + 2; and for the (, 3) problem, n = 3-1 if is odd and n = 3-2 if is even. Then, we study the general case (A ,D) and obtain that an upper bound on n is approximately 3(2D+1)(-2)bD/2c, and another one is C( - 2)bD/2c if D and C is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on n for maximal planar bipartite graphs, which is approximately ( - 2)k if D = 2k, and 3( - 3)k if D = 2k + 1, for and D sufficiently large in both cases.

The (A ,D) (degree/diameter) problem consists of finding the largest possible number of vertices n among all the graphs with maximum degree and diameter D. We consider the (A ,D) problem for maximal planar bipartite graphs, that are simple planar graphs in which every face is a quadrangle. We obtain that for the ( , 2) problem, the number of vertices is n = + 2; and for the ( , 3) problem, n = 3 -1 if is odd and n = 3 -2 if is even. Then, we study the general case ( A ,D) and obtain that an upper bound on n is approximately 3(2D+1)( -2)bD/2c, and another one is C( - 2)bD/2c if D and C is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on n for maximal planar bipartite graphs, which is approximately ( - 2)k if D = 2k, and 3( - 3)k if D = 2k + 1, for and D sufficiently large in both cases.]]>

GraphMasters Workshop

Presentation's date: 2014-07

International Workshop on Optimal Network Topologies

p. 1

Presentation's date: 2014-07

Electronic journal of graph theory and applications

Vol. 2, num. 1, p. 1-17

Date of publication: 2014

Abstract:

We study the (;D) and (;N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, the latter obtained by changing the directions of all the arcs. The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree and the unilateral diameter D, whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered.

We study the (delta;D) and (delta;N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, the latter obtained by changing the directions of all the arcs. The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree and the unilateral diameter D , whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered.]]>

Electronic notes in discrete mathematics

Vol. 46, p. 73-80

Date of publication: 2014

Abstract:

The (¿;D) (degree/diameter) problem consists of nding the largest possible number of vertices n among all the graphs with maximum degree ¿ and diameter D. We consider the (¿;D) problem for maximal planar bipartite graphs, that are simple planar graphs in which every face is a quadrangle. We obtain that for the (¿; 2) problem, the number of vertices is n = ¿+2; and for the (¿; 3) problem, n = 3¿¿1 if ¿ is odd and n = 3¿ ¿ 2 if ¿ is even. Then, we study the general case (¿;D) and obtain that an upper bound on n is approximately 3(2D + 1)(¿ ¿ 2)¿D=2¿ and another one is C(¿ ¿ 2)¿D=2¿ if ¿ D and C is a sufficiently large constant. Our upper bound improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on n for maximal planar bipartite graphs, which is approximately (¿ ¿ 2)k if D = 2k, and 3(¿ ¿ 3)k if D = 2k + 1, for ¿ and D sufficiently large in both cases.

The (¿;D) (degree/diameter) problem consists of nding the largest possible number of vertices n among all the graphs with maximum degree ¿ and diameter D. We consider the (¿;D) problem for maximal planar bipartite graphs, that are simple planar graphs in which every face is a quadrangle. We obtain that for the (¿; 2) problem, the number of vertices is n = ¿+2; and for the (¿; 3) problem, n = 3¿¿1 if ¿ is odd and n = 3¿ ¿ 2 if ¿ is even. Then, we study the general case (¿;D) and obtain that an upper bound on n is approximately 3(2D + 1)(¿ ¿ 2)¿D=2¿ and another one is C(¿ ¿ 2)¿D=2¿ if ¿ D and C is a sufficiently large constant. Our upper bound improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on n for maximal planar bipartite graphs, which is approximately (¿ ¿ 2)k if D = 2k, and 3(¿ ¿ 3)k if D = 2k + 1, for ¿ and D sufficiently large in both cases.]]>

European journal of combinatorics

Vol. 38, p. 130-132

Date of publication: 2014

Abstract:

Corrigendum d'un article anteriorment publicat. DOI: 10.1016/j.ejc.2013.05.006]]>

AKCE international journal of graphs and combinatorics

Vol. 10, num. 3, p. 273-283

Date of publication: 2013-10

Abstract:

We give a quasi-complete solution of the (¿,N) problem for two well-known families of digraphs used as good models for large interconnection networks. In our study we also relate both families, the New Amsterdam and Manhattan digraphs, with the double-step graphs (or circulant graphs with degree two).]]>

European Conference on Combinatorics, Graph Theory and Applications

p. 91-96

Presentation's date: 2013-09-09

Abstract:

We study the (D;D) and (D;N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs. The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree D and the unilateral diameter D , whereas the second one consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for some infinitely many values of the number of vertices. Miller and Sirán [4] wrote a comprehensive survey about (D;D) and (D;N) problems. In particular, for the double-step graphs considering the standard diameter, the first problem was solved by Fiol, Yebra, Alegre and Valero [3], whereas Bermond, Iliades and Peyrat [2], and also Beivide, Herrada, Balcázar and Arruabarrena [1] solved the (D;N) problem. In the case of the double-step digraphs, also with the standard diameter, Morillo, Fiol and Fàbrega [5] solved the (D;D) problem and provided some infinite families of digraphs which solve the (D;N) problem for their corresponding numbers of vertices]]>

GraphMasters Workshop

p. 7

Presentation's date: 2013-06-26

GraphMasters Workshop

p. 11

Presentation's date: 2013-06-26

Abstract:

We study the (;D) and (;N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs. The rst problem consists of maximizing the number of vertices N of a digraph, given the maximum degree and the unilateral diameter D, whereas the second one (somehow dual of the rst) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the rst problem for every value of the unilateral diameter and the second one for some innitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered.]]>