Skip to main content

TECNICAS DE OPTIMIZACION EN TEORIA DE GRAFOS, GRUPOS Y COMBINATORIA. APLICACIONES A REDES, ALGORITMOS Y PROTOCOLOS DE COMUNICACION.

MTM2014-60127-P

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D (Excelencia / Generación de Conocimiento)
Call year 2014
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Secretaría de Estado de Educación, Formación Profesional y Universidades
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 54
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Iterated line digraphs are asymptotically dense

  • Dalfó, Cristina
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., This research is supported by projects MINECO MTM2014-60127-P, and 2014SGR1147 of the Catalan Government. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A note on the order of iterated line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
Given a digraph G, we propose a new method to find therecurrence equation for the number of vertices nk of the k-iterated linedigraph Lk(G), for k≥0, where L0(G)=G. We obtain this result by usingthe minimal polynomial of a quotient digraph π(G) of G, This research is supported by the Ministerio de Economía y Competitividad and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

(Di)graph products, labelings and related results

  • López Masip, Susana-Clara
Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ⊗h-product of digraphs, the weak tensor product of graphs and the weak ⊗h-product of graphs., Reseach supported by the Spanish Government under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó, Cristina
  • Huemer, Clemens
  • Salas Piñón, Julián
The (∆, D) (degree/diameter) problem consists of finding the largest possiblenumber of verticesnamong all the graphs with maximum degree ∆ and diameter D. We consider the (∆, 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) 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 prove that, for the general case of the (∆, D) problem, 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 bounds improve for our kind of graphs theone given by Fellows, Hell and Seyffarth for general planar graphs. We also givea lower bound onnfor maximal planar bipartite graphs, which is approximately (∆−2)D/2 if D is even, and 3(∆−3)D/2 if D is odd, for ∆ and D sufficiently largein both cases., Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2014-60127-P, and by the Catalan Research Council under project 2014SGR1147.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

From Subkautz Digraphs to Cyclic Kautz Digraphs

  • Dalfó, Cristina
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, `) 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)., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A new labeling construction from the ⊗h-product

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Prabu, M.
The -product that is referred in the title was introduced in 2008 as a generalization of the Kronecker product of digraphs. Many relations among labelings have been obtained since then, always using as a second factor a family of super edge-magic graphs with equal order and size. In this paper, we introduce a new labeling construction by changing the role of the factors. Using this new construction the range of applications grows up considerably. In particular, we can increase the information about magic sums of cycles and crowns., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The spectra of subKautz and cyclic Kautz digraphs

  • Dalfó, Cristina
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 recently introduced by B¨ohmov´a, 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 HoffmanMcAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

New constructions for the n-queens problem

  • Bača, Martin
  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Semaničová-Feňovčíková, Andrea
Let D be a digraph, possibly with loops. A queen labeling of D is a bijective function l:V(G)⟶{1,2,…,|V(G)|} such that, for every pair of arcs in E(D), namely (u, v) and (u′,v′) we have (i) l(u)+l(v)≠l(u′)+l(v′) and (ii) l(v)−l(u)≠l(v′)−l(u′). Similarly, if the two conditions are satisfied modulo n=|V(G)|, we define a modular queen labeling. There is a bijection between (modular) queen labelings of 1-regular digraphs and the solutions of the (modular) n-queens problem. The ⊗h-product was introduced in 2008 as a generalization of the Kronecker product and since then, many relations among labelings have been established using the ⊗h-product and some particular families of graphs. In this paper, we study some families of 1-regular digraphs that admit (modular) queen labelings and present a new construction concerning to the (modular) n-queens problem in terms of the ⊗h-product, which in some sense complements a previous result due to Pólya., The research conducted in this document by the first and the fourth authors has been supported by APVV-15-0116 and VEGA 1/0233/18. The research conducted by second author has been supported by MTM2014-60127-P. Fund-ing was provided by Agentúra Ministerstva Skolstva, Vedy, Vyskumu a Sportu SR (Grant No. APVV-15-0116) and Ministerio de Educación, Cultura y Deporte (Grant No. MTM2014-60127-P), respectively.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

From expanded digraphs to lifts of voltage digraphs and line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
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., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 rese
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On quotient digraphs and voltage digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
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., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Sequence Mixed Graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
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 iterated 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 digraph by identifying some vertices of a 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., This research is supported by the Ministerio de Ciencia e Innovación, and the European Regional Development Fund under project MTM2014-60127-P (C. D. and M. A. F.), the Catalan Research Council under project 2014SGR1147 (C. D. and M. A. F.). The author N. L. has been supported in part by grant MTM2013-46949-P, from Ministerio de Economía y Competitividad, Spain
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The diameter of cyclic Kautz digraphs

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
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., Research of C. Dalfo is supported by projects MINECO MTM2014-60127-P, and AGAUR 2014SGR1147. Research of C. Huemer is supported by projects MINECO MTM2015-63791-R, and AGAUR 2014SGR46. C. Dalfo and C. Huemer have also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Cospectral digraphs from locally line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
A digraph Γ =(V, E) is a line digraph when every pair of vertices u, v∈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 Γ is a locally line digraph. In this paper we give a new method to obtain a di-graph Γ′ cospectral with a given locally line digraph Γ with diameter D, where the diameter D′ of Γ′ 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., This research is supported by the Ministerio de Ciencia e Innovación and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

Proinsulin protects against age-related cognitive loss through anti-inflammatory convergent pathways

  • Corpas, Rubén
  • Hernández-Pinto, Alberto M.
  • Porquet, David
  • Hernández-Sánchez, Catalina
  • Bosch, Fátima
  • Comellas, Francesc
  • De la Rosa, Enrique J.
  • Sanfeliu, Coral
40 p.-5 fig., Brain inflammaging is increasingly considered as contributing to age-related cognitive loss and neurodegeneration. Despite intensive research in multiple models, no clinically effective pharmacological treatment has been found yet. Here, in the mouse model of brain senescence SAMP8, we tested the effects of proinsulin, a promising neuroprotective agent that was previously proven to be effective in mouse models of retinal neurodegeneration. Proinsulin is the precursor of the hormone insulin but also upholds developmental physiological effects, particularly as a survival factor for neural cells. Adeno-associated viral vectors of serotype 1 bearing the human proinsulin gene were administered intramuscularly to obtain a sustained release of proinsulin into the blood stream, which was able to reach the target area of the hippocampus. SAMP8 mice and the control strain SAMR1 were treated at 1 month of age. At 6 months, behavioral testing exhibited cognitive loss in SAMP8 mice treated with the null vector. Remarkably, the cognitive performance achieved in spatial and recognition tasks by SAMP8 mice treated with proinsulin was similar to that of SAMR1 mice. In the hippocampus, proinsulin induced the activation of neuroprotective pathways and the downstream signaling cascade, leading to the decrease of neuroinflammatory markers. Furthermore, the decrease of astrocyte reactivity was a central effect, as demonstrated in the connectome network of changes induced by proinsulin. Therefore, the neuroprotective effects of human proinsulin unveil a new pharmacological potential therapy in the fight against cognitive loss in the elderly., This work was supported by grants: CSD2010-00045 to CS and EJdlR, from the Spanish Ministerio de Economía y Competitividad (MINECO), SAF2016-77703-C2-2-R to CS and MTM2014-60127-P to FC from MINECO and European Regional Development Fund (ERDF), and TRACE (PET08-0282) to FB and EJdlR, from the Spanish Ministerio de Ciencia e Innovación (MICINN)., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Contribución de congreso (ConferenceOutput)

Proinsulin therapy protects against neuroinflammaging and cognitive loss in senescence-accelerated mice

  • Sanfeliu, Coral
  • Corpas, Rubén
  • Hernández-Pinto, Alberto M.
  • Porquet, David
  • Hernández-Sánchez, Catalina
  • Bosch, Fátima
  • Ortega-Aznar, Arantxa
  • Comellas, Francesc
  • De la Rosa, Enrique J.
Trabajo presentado en el IUBMB Focused Meeting on «Molecular aspects of aging and longevity», celebrado en Atenas, del 16 al 19 de octubre de 2017, Chronic low-grade neuroinflammation is tightly associated with brain age-related changes and it is considered a crucial derangement that paves the way to neurodegeneration and dementia. Among other ailments, inflammation may lead to insulin resistance that is a risk factor for Alzheimer’s disease. In this scenario, the hormone precursor proinsulin may have a potential pharmacological use in preventing neuronal death. Proinsulin is a bioactive molecule regulating neural cell death in embryonic processes and it was proven neuroprotective in mouse models of retinal neurodegeneration. We aimed to prove the geroprotective effect of a chronic proinsulin treatment against neuroinflammaging and memory loss in the senescence-accelerated mouse SAMP8. We used a gene therapy procedure through peripheral muscle transduction with an adeno-associated viral vector bearing the human proinsulin gene (AAV-hPi) that yielded sustained release of proinsulin into the bloodstream. One-month old male mice of the SAMP8 strain and the control strain SAMR1 were injected with AAV-hPi or AAV-null vectors. At 6 months of age, proinsulin-treated SAMP8 mice showed totally preserved cognitive capacities both in spatial and recognition paradigms of learning and memory, in contrast to those SAMP8 mice injected with the null vector. Hippocampus analysis showed that proinsulin activated Akt and ATF1/CREB signaling pathways in both SAMR1 and SAMP8 mice. Furthermore, we identified a significant decrease of neuroinflammatory markers in the hippocampus of SAMP8 mice to levels of SAMR1 mice. Strikingly, the marker of astrocyte reactivity GFAP was decreased in both SAMR1 and SAMP8. Furthermore, the connectome network build with all changes induced by proinsulin showed that the decrease of astrocyte reactivity was a central effect in proinsulin neuroprotection. Therefore, the preventive and protective effects of human proinsulin against neuroinflammaging and senescence-related cognitive loss unveil a potential geroprotective therapy to increase healthy brain aging., This study was supported by CSD2010-00045, SAF2016-77703-C2-2-R, MTM2014-60127-P, MINECO and ERDF; PET08-0282, TRACE., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

About (k,l)-kernels, semikernels and Grundy functions in partial line digraphs

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • Galeana Sánchez, Hortensia
  • Guevara Aguirre, Nucuy-kak
Let D be a digraph of minimum in-degree at least 1. We prove that for any two natural numbers k, l such that 1 = l = k, the number of (k, l)-kernels of D is less than or equal to the number of (k, l)-kernels of any partial linedigraph LD. Moreover, if l < k and the girth of D is at least l+1, then these two numbers are equal. We also prove that the number of semikernels of D is equal to the number of semikernels of LD. Furthermore, we introduce the concept of (k, l)-Grundy function as a generalization of the concept of Grundy function and we prove that the number of (k, l)-Grundy functions of D is equal to the number of (k, l)-Grundy functions of any partial line digraph LD., This research was supported by the Ministerio de Educación y Ciencia, Spain, the European Regional Development Fund (ERDF) under project MTM2014-60127-P, by CONACyT-México under project 219840 and by UNAM-DGAPA-PAPIIT IN104717 and IN115816., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6, Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Deterministic hierarchical networks

  • Barrière Figueroa, Eulalia|||0000-0002-5692-6879
  • Comellas Padró, Francesc de Paula|||0000-0003-4523-0240
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Layer structure of De Bruijn and Kautz digraphs: an application to deflection routing

  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
In the main part of this paper we present polynomial expressions for the cardinalities of some sets of interest of the nice distance-layer structure of the well-known De Bruijn and Kautz digraphs. More precisely, given a vertex $v$, let $S_{i}^\star(v)$ be the set of vertices at distance $i$ from $v$. We show that $|S_{i}^\star(v)|=d^i-a_{i-1}d^{i-1}-\cdots -a_{1} d-a_{0}$, where $d$ is the degree of the digraph and the coefficients $a_{k}\in\{0,1\}$ are explicitly calculated. Analogously, let $w$ be a vertex adjacent from $v$ such that $S_{i}^\star(v)\cap S_j^{\ast}(w)\neq \emptyset$ for some $j$. We prove that $\big |S_{i}^\star(v) \cap S_j^{\ast}(w) \big |=d^i-b_{i-1}d^{i-1}-\ldots -b_{1} d-b_{0},$ where the coefficients $b_{t}\in\{0,1\}$ are determined from the coefficients $a_k$ of the polynomial expression of $|S_{i}^\star(v)|$. An application to deflection routing in De Bruijn and Kautz networks serves as motivation for our study. It is worth-mentioning that our analysis can be extended to other families of digraphs on alphabet or to general iterated line digraphs., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Caterpillars have antimagic orientations

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
An antimagic labeling of a directed graph D with m arcs is a bijection from the set of arcs of D to {1, . . . , m} such that all oriented vertex sums of vertices in D are pairwise distinct, where the oriented vertex sum of a vertex u is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Hefetz, Mütze, and Schwartz [3] conjectured that every connected graph admits an antimagic orientation, where an antimagic orientation of a graph G is an orientation of G which has an antimagic labeling. We use a constructive technique to prove that caterpillars, a well-known subclass of trees, have antimagic orientations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Rainbow connectivity of Moore cages of girth 6

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • Fresán Figueroa, J.
  • González Moreno, Diego
  • Olsen, Mika
Let be an edge-colored graph. A path of is said to be rainbow if no two edges of have the same color. An edge-coloring of is a rainbow-coloring if for any two distinct vertices and of there are at least internally vertex-disjoint rainbow -paths. The rainbow-connectivity of a graph is the minimum integer such that there exists a rainbow -coloring using colors. A -cage is a -regular graph of girth and minimum number of vertices denoted . In this paper we focus on . It is known that and when the -cage is called a Moore cage. In this paper we prove that the rainbow -connectivity of a Moore -cage satisfies that . It is also proved that the rainbow 3-connectivity of the Heawood graph is 6 or 7., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

(Di)graph products, labelings and related results

  • López Masip, Susana Clara|||0000-0003-2438-913X
Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ¿h-product of digraphs, the weak tensor product of graphs and the weak ¿h-product of graphs.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Huemer, Clemens|||0000-0001-7557-0823
  • Salas Piñon, Julián
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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Uniform clutters and dominating sets of graphs

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Ruiz Muñoz, José Luis|||0000-0002-2245-7752
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Cospectral digraphs from locally line digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A note on the order of iterated line digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Bounds on the k-restricted arc connectivity of some bipartite tournaments

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • González Moreno, Diego
  • Olsen, Mika
For k¿=¿2, a strongly connected digraph D is called -connected if it contains a set of arcs W such that contains at least k non-trivial strong components. The k-restricted arc connectivity of a digraph D was defined by Volkmann as . In this paper we bound for a family of bipartite tournaments T called projective bipartite tournaments. We also introduce a family of “good” bipartite oriented digraphs. For a good bipartite tournament T we prove that if the minimum degree of T is at least then where N is the order of the tournament. As a consequence, we derive better bounds for circulant bipartite tournaments., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On Hamiltonian alternating cycles and paths

  • Claverol, Mercè
  • García, Alfredo
  • Garijo, Delia
  • Seara, Carlos
  • Tejel, Javier
We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Deterministic hierarchical networks

  • Barrière Figueroa, Eulalia
  • Comellas Padró, Francesc de Paula
  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
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., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

New constructions for the n-queens problem

  • Bača, Martin
  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Semaničová-Feňovčíková, Andrea
Let D be a digraph, possibly with loops. A queen labeling of D is a bijective function l:V(G)⟶{1,2,…,|V(G)|} such that, for every pair of arcs in E(D), namely (u, v) and (u′,v′) we have (i) l(u)+l(v)≠l(u′)+l(v′) and (ii) l(v)−l(u)≠l(v′)−l(u′). Similarly, if the two conditions are satisfied modulo n=|V(G)|, we define a modular queen labeling. There is a bijection between (modular) queen labelings of 1-regular digraphs and the solutions of the (modular) n-queens problem. The ⊗h-product was introduced in 2008 as a generalization of the Kronecker product and since then, many relations among labelings have been established using the ⊗h-product and some particular families of graphs. In this paper, we study some families of 1-regular digraphs that admit (modular) queen labelings and present a new construction concerning to the (modular) n-queens problem in terms of the ⊗h-product, which in some sense complements a previous result due to Pólya., The research conducted in this document by the first and the fourth authors has been supported by APVV-15-0116 and VEGA 1/0233/18. The research conducted by second author has been supported by MTM2014-60127-P. Fund-ing was provided by Agentúra Ministerstva Skolstva, Vedy, Vyskumu a Sportu SR (Grant No. APVV-15-0116) and Ministerio de Educación, Cultura y Deporte (Grant No. MTM2014-60127-P), respectively.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Uniform clutters and dominating sets of graphs

  • Martí Farré, Jaume
  • Mora Giné, Mercè
  • Ruiz Muñoz, José Luis
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

(Di)graph products, labelings and related results

  • López Masip, Susana Clara
Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ¿h-product of digraphs, the weak tensor product of graphs and the weak ¿h-product of graphs., Postprint (updated version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Cospectral digraphs from locally line digraphs

  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
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., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Bounds on the k-restricted arc connectivity of some bipartite tournaments

  • Balbuena Martínez, Maria Camino Teófila
  • González Moreno, Diego
  • Olsen, Mika
For k¿=¿2, a strongly connected digraph D is called -connected if it contains a set of arcs W such that contains at least k non-trivial strong components. The k-restricted arc connectivity of a digraph D was defined by Volkmann as . In this paper we bound for a family of bipartite tournaments T called projective bipartite tournaments. We also introduce a family of “good” bipartite oriented digraphs. For a good bipartite tournament T we prove that if the minimum degree of T is at least then where N is the order of the tournament. As a consequence, we derive better bounds for circulant bipartite tournaments., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Sequence Mixed Graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
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 iterated 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 digraph by identifying some vertices of a 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., This research is supported by the Ministerio de Ciencia e Innovación, and the European Regional Development Fund under project MTM2014-60127-P (C. D. and M. A. F.), the Catalan Research Council under project 2014SGR1147 (C. D. and M. A. F.). The author N. L. has been supported in part by grant MTM2013-46949-P, from Ministerio de Economía y Competitividad, Spain
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Rainbow connectivity of Moore cages of girth 6

  • Balbuena Martínez, Maria Camino Teófila
  • Fresán Figueroa, J.
  • González Moreno, Diego
  • Olsen, Mika
Let be an edge-colored graph. A path of is said to be rainbow if no two edges of have the same color. An edge-coloring of is a rainbow-coloring if for any two distinct vertices and of there are at least internally vertex-disjoint rainbow -paths. The rainbow-connectivity of a graph is the minimum integer such that there exists a rainbow -coloring using colors. A -cage is a -regular graph of girth and minimum number of vertices denoted . In this paper we focus on . It is known that and when the -cage is called a Moore cage. In this paper we prove that the rainbow -connectivity of a Moore -cage satisfies that . It is also proved that the rainbow 3-connectivity of the Heawood graph is 6 or 7., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

(Di)graph products, labelings and related results

  • López Masip, Susana-Clara
Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ⊗h-product of digraphs, the weak tensor product of graphs and the weak ⊗h-product of graphs., Reseach supported by the Spanish Government under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Layer structure of De Bruijn and Kautz digraphs: an application to deflection routing

  • Fàbrega Canudas, José
  • Martí Farré, Jaume
  • Muñoz López, Francisco Javier
In the main part of this paper we present polynomial expressions for the cardinalities of some sets of interest of the nice distance-layer structure of the well-known De Bruijn and Kautz digraphs. More precisely, given a vertex $v$, let $S_{i}^\star(v)$ be the set of vertices at distance $i$ from $v$. We show that $|S_{i}^\star(v)|=d^i-a_{i-1}d^{i-1}-\cdots -a_{1} d-a_{0}$, where $d$ is the degree of the digraph and the coefficients $a_{k}\in\{0,1\}$ are explicitly calculated. Analogously, let $w$ be a vertex adjacent from $v$ such that $S_{i}^\star(v)\cap S_j^{\ast}(w)\neq \emptyset$ for some $j$. We prove that $\big |S_{i}^\star(v) \cap S_j^{\ast}(w) \big |=d^i-b_{i-1}d^{i-1}-\ldots -b_{1} d-b_{0},$ where the coefficients $b_{t}\in\{0,1\}$ are determined from the coefficients $a_k$ of the polynomial expression of $|S_{i}^\star(v)|$. An application to deflection routing in De Bruijn and Kautz networks serves as motivation for our study. It is worth-mentioning that our analysis can be extended to other families of digraphs on alphabet or to general iterated line digraphs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A new labeling construction from the ⊗h-product

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Prabu, M.
The -product that is referred in the title was introduced in 2008 as a generalization of the Kronecker product of digraphs. Many relations among labelings have been obtained since then, always using as a second factor a family of super edge-magic graphs with equal order and size. In this paper, we introduce a new labeling construction by changing the role of the factors. Using this new construction the range of applications grows up considerably. In particular, we can increase the information about magic sums of cycles and crowns., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues

  • Fiol Mora, Miquel Àngel
The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6, Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

From expanded digraphs to lifts of voltage digraphs and line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
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., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 rese
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The spectra of subKautz and cyclic Kautz digraphs

  • Dalfó, Cristina
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 recently introduced by B¨ohmov´a, 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 HoffmanMcAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

About (k,l)-kernels, semikernels and Grundy functions in partial line digraphs

  • Balbuena Martínez, Maria Camino Teófila
  • Galeana Sánchez, Hortensia
  • Guevara Aguirre, Nucuy-kak
Let D be a digraph of minimum in-degree at least 1. We prove that for any two natural numbers k, l such that 1 = l = k, the number of (k, l)-kernels of D is less than or equal to the number of (k, l)-kernels of any partial linedigraph LD. Moreover, if l < k and the girth of D is at least l+1, then these two numbers are equal. We also prove that the number of semikernels of D is equal to the number of semikernels of LD. Furthermore, we introduce the concept of (k, l)-Grundy function as a generalization of the concept of Grundy function and we prove that the number of (k, l)-Grundy functions of D is equal to the number of (k, l)-Grundy functions of any partial line digraph LD., This research was supported by the Ministerio de Educación y Ciencia, Spain, the European Regional Development Fund (ERDF) under project MTM2014-60127-P, by CONACyT-México under project 219840 and by UNAM-DGAPA-PAPIIT IN104717 and IN115816., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The diameter of cyclic Kautz digraphs

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
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., Research of C. Dalfo is supported by projects MINECO MTM2014-60127-P, and AGAUR 2014SGR1147. Research of C. Huemer is supported by projects MINECO MTM2015-63791-R, and AGAUR 2014SGR46. C. Dalfo and C. Huemer have also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Iterated line digraphs are asymptotically dense

  • Dalfó, Cristina
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., This research is supported by projects MINECO MTM2014-60127-P, and 2014SGR1147 of the Catalan Government. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A note on the order of iterated line digraphs

  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
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., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On quotient digraphs and voltage digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
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., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó Simó, Cristina
  • Huemer, Clemens
  • Salas Piñon, Julián
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., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

From Subkautz Digraphs to Cyclic Kautz Digraphs

  • Dalfó, Cristina
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, `) 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)., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Caterpillars have antimagic orientations

  • Lozano Boixadors, Antoni
An antimagic labeling of a directed graph D with m arcs is a bijection from the set of arcs of D to {1, . . . , m} such that all oriented vertex sums of vertices in D are pairwise distinct, where the oriented vertex sum of a vertex u is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Hefetz, Mütze, and Schwartz [3] conjectured that every connected graph admits an antimagic orientation, where an antimagic orientation of a graph G is an orientation of G which has an antimagic labeling. We use a constructive technique to prove that caterpillars, a well-known subclass of trees, have antimagic orientations., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A note on the order of iterated line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
Given a digraph G, we propose a new method to find therecurrence equation for the number of vertices nk of the k-iterated linedigraph Lk(G), for k≥0, where L0(G)=G. We obtain this result by usingthe minimal polynomial of a quotient digraph π(G) of G, This research is supported by the Ministerio de Economía y Competitividad and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Cospectral digraphs from locally line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
A digraph Γ =(V, E) is a line digraph when every pair of vertices u, v∈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 Γ is a locally line digraph. In this paper we give a new method to obtain a di-graph Γ′ cospectral with a given locally line digraph Γ with diameter D, where the diameter D′ of Γ′ 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., This research is supported by the Ministerio de Ciencia e Innovación and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó, Cristina
  • Huemer, Clemens
  • Salas Piñón, Julián
The (∆, D) (degree/diameter) problem consists of finding the largest possiblenumber of verticesnamong all the graphs with maximum degree ∆ and diameter D. We consider the (∆, 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) 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 prove that, for the general case of the (∆, D) problem, 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 bounds improve for our kind of graphs theone given by Fellows, Hell and Seyffarth for general planar graphs. We also givea lower bound onnfor maximal planar bipartite graphs, which is approximately (∆−2)D/2 if D is even, and 3(∆−3)D/2 if D is odd, for ∆ and D sufficiently largein both cases., Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2014-60127-P, and by the Catalan Research Council under project 2014SGR1147.
Dipòsit Digital de Documents de la UAB
Publication Artículo científico (JournalArticle)

Disease networks identify specific conditions and pleiotropy influencing multimorbidity in the general population

  • Amell, A.
  • Roso-Llorach, Albert|||0000-0002-9264-0405
  • Palomero, L.
  • Cuadras, Daniel|||0000-0001-8780-1764
  • Galván-Femenía, Iván|||0000-0002-6124-3730
  • Serra-Musach, J.
  • Comellas, Francesc|||0000-0003-4523-0240
  • de Cid, Rafael|||0000-0003-3579-6777
  • Pujana, Miguel Angel|||0000-0003-3222-4044
  • Violán, Concepció|||0000-0003-3309-5360
Multimorbidity is an emerging topic in public health policy because of its increasing prevalence and socio-economic impact. However, the age- and gender-dependent trends of disease associations at fine resolution, and the underlying genetic factors, remain incompletely understood. Here, by analyzing disease networks from electronic medical records of primary health care, we identify key conditions and shared genetic factors influencing multimorbidity. Three types of diseases are outlined: "central", which include chronic and non-chronic conditions, have higher cumulative risks of disease associations; "community roots" have lower cumulative risks, but inform on continuing clustered disease associations with age; and "seeds of bursts", which most are chronic, reveal outbreaks of disease associations leading to multimorbidity. The diseases with a major impact on multimorbidity are caused by genes that occupy central positions in the network of human disease genes. Alteration of lipid metabolism connects breast cancer, diabetic neuropathy and nutritional anemia. Evaluation of key disease associations by a genome-wide association study identifies shared genetic factors and further supports causal commonalities between nervous system diseases and nutritional anemias. This study also reveals many shared genetic signals with other diseases. Collectively, our results depict novel population-based multimorbidity patterns, identify key diseases within them, and highlight pleiotropy influencing multimorbidity.