 Research group
 COMBGRAF  Combinatorics, Graph Theory and Applications
 Department
 Department of Applied Mathematics IV
 School
 Barcelona School of Telecommunications Engineering (ETSETB)
 fiolma4.upc.edu
 Contact details
 UPC directory
Scientific and technological production


Corrigendum to "Algebraic characterizations of regularity properties in bipartite graphs" Eur. J. Combin. 34 (2013) 12231231
Abiad, Aida; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
European journal of combinatorics
Date of publication: 2014
Journal article
View Share Reference managers 
ID routing mechanism for opportunistic multihop networks
Agusti Torra, Anna; Cervello Pastor, Cristina; Fiol Mora, Miquel Àngel
IEEE communications letters
Date of publication: 201312
Journal article
Read the abstract View Share Reference managersThis letter proposes a general packet delivery mechanism in which routing decisions are taken on the basis of the identifiers assigned to each node. Such identifiers depend on the position of each node in the network, and their purpose is to simplify as much as possible the communication process between each pair of nodes. The proposal is based on building trees as the Routing Protocol for LowPower and Lossy Networks (RPL), described in RFC 6550, does. Then, each node of the tree receives a unique identifier following a hierarchical scheme. Hence, every two nodes of the tree can communicate with each other performing simple bitwise XOR operations at intermediate nodes instead of building, storing and maintaining complex routing tables. 
A simple and fast heuristic algorithm for edgecoloring of graphs
Fiol Mora, Miquel Àngel; Vilaltella Castanyer, Joan
AKCE International Journal of Graphs and Combinatorics
Date of publication: 201310
Journal article
Read the abstract View Share Reference managersA simple but empirically efficient heuristic algorithm for the edgecoloring of graphs is presented. Its basic idea is the displacement of 'conflicts' (repeated colors in the edges incident to a vertex) along paths of adjacent vertices whose incident edges are recolored by swapping alternating colors (that is, doing a Kempe interchange). The results of performance tests on random cubic and ¿ regular graphs are presented, and a full implementation of the algorithm is given to facilitate its use and the reproducibility of results. 
The spectral excess theorem for distancebiregular graphs
Fiol Mora, Miquel Àngel
Electronic journal of combinatorics
Date of publication: 20130816
Journal article
Read the abstract Access to the full text Share Reference managersThe spectral excess theorem for distanceregular graphs states that a regular (connected) graph is distanceregular if and only if its spectralexcess equals its average excess. A bipartite graph G is distancebiregular when it is distanceregular around each vertex and the intersection array only depends on the stable set such a vertex belongs to. In this note we derive a new version of the spectral excess theorem for bipartite distancebiregular graphs.
The spectral excess theorem for distanceregular graphs states that a regular (connected) graph is distanceregular if and only if its spectralexcess equals its average excess. A bipartite graph 
Connectivity: properties and structure
Balbuena Martinez, Maria Camino Teofila; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel
Date of publication: 20131205
Book chapter
Read the abstract View Share Reference managersConnectivity is one of the central concepts of graph theory, from both a theoret ical and a practical point of view. Its theoretical implications are mainly based on the existence of nice maxmin characterization results, such as Menger¿s theorems. In these theorems, one condition which is clearly necessary also turns out to be sufficient. Moreover, these results are closely related to some other key theorems in graph theory: Ford and Fulkerson¿s theorem about flows and Hall¿s theorem on perfect matchings. With respect to the applications, the study of connectivity parameters of graphs and digraphs is of great interest in the design of reliable and faulttolerant interconnection or communication networks. Since graph connectivity has been so widely studied, we limit ourselves here to the presentation of some of the key results dealing with finite simple graphs and digraphs. For results about infinite graphs and connectivity algorithms the reader can consult, for instance, Aharoni and Diestel [AhDi94], Gibbons [Gi85], Halin [Ha00], Henzinger, Rao, and Gabow [HeRaGa00], Wigderson [Wi92]. For further details, we refer the reader to some of the good textbooks and surveys available on the subject: Berge [Be76], Bermond, Homobono, and Peyrat [BeHoPe89], Frank [Fr90, Fr94, Fr95], Gross and Yellen [GrYe06], Hellwig and Volkmann [HeVo08], Lov ´asz [Lo93], Mader [Ma79], Oellermann [Oe96], Tutte [Tu66]. 
Further topics in connectivity
Balbuena Martinez, Maria Camino Teofila; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel
Date of publication: 20131205
Book chapter
Read the abstract View Share Reference managersContinuing the study of connectivity, initiated in §4.1 of the Handbook, we survey here some (sufficient) conditions under which a graph or digraph has a given connectivity or edgeconnectivity. First, we describe results concerning maximal (vertex or edge) connectivity. Next, we deal with conditions for having (usually lower) bounds for the connectivity parameters. Finally, some other general connectivity measures, such as one instance of the socalled ¿conditional connectivity,¿ are considered. For unexplained terminology concerning connectivity, see §4.1. 
The (Delta,D) and (Delta,N) problems in doublestep digraphs with unilateral diameter
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
European Conference on Combinatorics, Graph Theory and Applications
Presentation's date: 20130909
Presentation of work at congresses
View Share Reference managers 
Moments in graphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Discrete applied mathematics
Date of publication: 2013
Journal article
Read the abstract Access to the full text Share Reference managersThis parameter generalizes, or it is closely related to, some wellknown graph invariants, such as the Wiener index W (G), when rho(u) = 1/2 for every u is an element of V, and the degree distance D'(G), obtained when rho(u) = delta(u), the degree of vertex u. In this paper we derive some exact formulas for computing the rhomoment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding rhomoments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same rhomoment for every rho (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.
Let G be a connected graph with vertex set V and a weight function that assigns a nonnegative number to each of its vertices. Then, the moment of G at vertex u is de ned to be M G(u) = P v2V (v) dist(u; v), where dist( ; ) stands for the distance function. Adding up all these numbers, we obtain the moment of G: This parameter generalizes, or it is closely related to, some wellknown graph invari ants, such as the Wiener index W(G), when (u) = 1=2 for every u 2 V , and the degree distance D0(G), obtained when (u) = (u), the degree of vertex u. In this paper we derive some exact formulas for computing the moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same moment for every (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.
Postprint (author’s final draft) 
The Manhattan product of digraphs
Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
Electronic Journal of Graph Theory and Applications
Date of publication: 2013
Journal article
Read the abstract Access to the full text Share Reference managersWe study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other networks with similar good properties. It is shown that if all the factors of such a product are (directed) cycles, then the digraph obtained is a Manhattan street network, a widely studied topology for modeling some interconnection networks. To this respect, it is proved that many properties of these networks, such as high symmetries, reduced diameter and the presence of Hamiltonian cycles, are shared by the Manhattan product of some digraphs. Moreover, we show that the Manhattan product of two Manhattan streets networks is also a Manhattan street network. Finally, some sufficient conditions for the Manhattan product of two Cayley digraphs to be also a Cayley digraph are given. Throughout our study we use some interesting recent concepts, such as the unilateral distance and related graph invariants. 
On some approaches to the spectral excess theorem for nonregular graphs
Fiol Mora, Miquel Àngel
Journal of combinatorial theory. Series A
Date of publication: 201308
Journal article
Read the abstract View Share Reference managersThe spectral excess theorem for distanceregular graphs states that a regular (connected) graph is distanceregular if and only if its spectral excess equals its average excess. Recently, some local as well as global approaches to this result have been used to obtain new versions of the theorem for nonregular graphs, and also to study the problem of characterizing those graphs which have the corresponding distanceregularity property. In this paper such approaches are compared and related. In particular, a recent inequality of Lee and Weng for nonregular graphs, which is similar to the one that leads to the spectral excess theorem, is improved. As a consequence, we obtain new characterizations of some properties related to that of distanceregularity. For instance, a sufficient condition for to be distancepolynomial is obtained. 
The (¿,D) and (¿,N) problems for New Amsterdam and Manhattan digraphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
AKCE International Journal of Graphs and Combinatorics
Date of publication: 201310
Journal article
Read the abstract View Share Reference managersWe give a quasicomplete solution of the (¿,N) problem for two wellknown 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 doublestep graphs (or circulant graphs with degree two). 
Algebraic Characterizations of Regularity Properties in Bipartite Graphs
Abiad Monge, Aida; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
European journal of combinatorics
Date of publication: 2013
Journal article
Read the abstract View Share Reference managersRegular and distanceregular characterizations of general graphs are wellknown. In particular, the spectral excess theorem states that a connected graph GG is distanceregular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distanceregularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distanceregularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented. 
Edgedistanceregular graphs are distanceregular
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Delorme, Charles; Fiol Mora, Miquel Àngel; Suzuki, Hiroshi
Journal of combinatorial theory. Series A
Date of publication: 2013
Journal article
Read the abstract View Share Reference managersEdgedistanceregular graph; Homogeneous graph; Bipartite distanceregular graph; Generalized odd graph; Orthogonal polynomials 
Characterizing distanceregular graphs that are edgedistanceregular
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
ESF Research Conferences
Presentation's date: 201206
Presentation of work at congresses
Share Reference managers 
Edgedistance regular graphs are distance regular
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Delorme, Charles; Fiol Mora, Miquel Àngel; Suzuki, Hiroshi
ICTPIPM Workshop and Conference in Combinatorics and Graph Theory
Presentation's date: 20120910
Presentation of work at congresses
Share Reference managers 
A short proof of the oddgirth theorem
Van Dam, Edwin R; Fiol Mora, Miquel Àngel
Electronic journal of combinatorics
Date of publication: 20120809
Journal article
View Share Reference managers 
Optimización y problemas extremales en teoria de grafos y combinatoria. Aplicacions a les redes de comunicación
Aguilo Gost, Francisco de Asis Luis; Abiad Monge, Aida; Andrés Yebra, José Luis; Barriere Figueroa, Eulalia; Cámara Vallejo, Marc; Ball, Simeon Michael; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Garriga Valle, Ernest; Gomez Marti, Jose; Llado Sanchez, Anna; López Masip, Susana Clara; Miralles De La Asuncion, Alicia; Mitjana Riera, Margarida; Muñoz Lopez, Francisco Javier; Pelayo Melero, Ignacio Manuel; Pérez Mansilla, Sonia; Rius Font, Miquel; Serra Albo, Oriol; Vena, Lluis; Vilaltella Castanyer, Joan; Zaragoza Monroig, Maria Luisa; Espona Dones, Margarida; Sau Valls, Ignasi; Montejano Cantoral, Amanda; Perarnau Llobet, Guillem; Moragas Vilarnau, Jordi; Vena Cros, Lluís; Andres Yebra, Jose Luis; Fiol Mora, Miquel Àngel
Participation in a competitive project
Share 
Pseudodistanceregularized graphs are distanceregular or distancebiregular
Fiol Mora, Miquel Àngel
Linear algebra and its applications
Date of publication: 2012
Journal article
View Share Reference managers 
Edgedistanceregular graphs
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
European Conference on Combinatorics, Graph Theory and Applications
Presentation's date: 20110831
Presentation of work at congresses
Share Reference managers 
Performance analysis of the sentbutsure strategy for optical burst and packet switched networks
Agusti Torra, Anna; Cervello Pastor, Cristina; Fiol Mora, Miquel Àngel
Performance evaluation
Date of publication: 201101
Journal article
Read the abstract View Share Reference managersThis work proposes an analytical model to characterize the performance of a lossfree transmission strategy for Optical Burst and Packet Switched Networks, which ensures that a burst/packet will successfully reach its destination once it has been scheduled in the first link of its path. In this paper this strategy is called SentButSure (SBS) because it avoids losses in any intermediate node. The SBS strategy combines a routing and wavelength assignment scheme with simple contention resolution mechanisms. As a result, new burst/packet allocation attempts in an intermediate node only contend with bursts/packets in transit coming from a single input link. Moreover, bursts/packets in transit always have priority over bursts/packets whose transmission has not been scheduled yet. These two main features of the SBS strategy allow us to develop an analytical model based on a twopriority M/G/1 queueing model to characterize the network performance. 
Edgedistanceregular graphs
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Journal of combinatorial theory. Series A
Date of publication: 2011
Journal article
Read the abstract View Share Reference managersEdgedistanceregularity is a concept recently introduced by the authors which is similar to that of distanceregularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edgedistanceregular when it is distanceregular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edgedistanceregular if and only if its kincidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distanceregular graphs is proved, so giving a quasispectral characterization of edgedistanceregularity. Finally, it is shown that every nonbipartite graph which is both distanceregular and edgedistanceregular is a generalized odd graph. 
On perturbations of almost distanceregular graphs
Dalfo Simo, Cristina; Van Dam, Edwin R; Fiol Mora, Miquel Àngel
Linear algebra and its applications
Date of publication: 2011
Journal article
View Share Reference managers 
Dual concepts of almost distanceregularity and the spectral excess theorem
Dalfo Simo, Cristina; Van Dam, Edwin R; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Discrete mathematics
Date of publication: 2011
Journal article
View Share Reference managers 
ALGEBRAIC AND COMBINATORIC APPROACH TO PSEUDODISTANCEREGULARITY OF GRAPHS AND COMPLETELY PSEUDOREGULAR CODES.
Cámara Vallejo, Marc
Defense's date: 20110615
Department of Applied Mathematics IV, Universitat Politècnica de Catalunya
Theses
Share Reference managers 
ALGEBRAIC AND COMBINATORIC APPROACH TO PSEUDODISTANCEREGULARITY OF GRAPHS AND COMPLETELY PSEUDOREGULAR CODES
Cámara Vallejo, Marc
Defense's date: 20110615
Department of Applied Mathematics IV, Universitat Politècnica de Catalunya
Theses
View Share Reference managers 
A differential approach for bounding the index of graphs under perturbations
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Date: 201103
Report
Access to the full text Share Reference managers 
Edgedistanceregular graphs
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Date: 20110311
Report
Read the abstract Access to the full text Share Reference managersEdgedistanceregularity is a concept recently introduced by the authors which is similar to that of distanceregularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edgedistanceregular when it is distanceregular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edgedistanceregular if and only if its kincidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distanceregular graphs is proved, so giving a quasispectral characterization of edgedistanceregularity. Finally, it is shown that every nonbipartite graph which is both distanceregular and edgedistanceregular is a generalized odd graph. 
A differential approach for bounding the index of graphs under perturbations
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Electronic journal of combinatorics
Date of publication: 20110902
Journal article
Read the abstract Access to the full text Share Reference managersThis paper presents bounds for the variation of the spectral radius (G) of a graph G after some perturbations or local vertex/edge modifications of G. The perturbations considered here are the connection of a new vertex with, say, g vertices of G, the addition of a pendant edge (the previous case with g = 1) and the addition of an edge. The method proposed here is based on continuous perturbations and the study of their differential inequalities associated. Within rather economical information (namely, the degrees of the vertices involved in the perturbation), the best possible inequalities are obtained. In addition, the cases when equalities are attained are characterized. The asymptotic behavior of the bounds obtained is also discussed. 
Edge distanceregular graphs
Cámara Vallejo, Marc; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Electronic notes in discrete mathematics
Date of publication: 2011
Journal article
Read the abstract Access to the full text Share Reference managersEdgedistanceregularity is a concept recently introduced by the authors which is similar to that of distanceregularity, but now the graph is seen from each of its edges instead of from its vertices. More precisely, a graph Γ with adjacency matrix A is edgedistanceregular when it is distanceregular around each of its edges and with the same intersection numbers for any edge taken as a root. In this paper we study this concept, give some of its properties, such as the regularity of Γ, and derive some characterizations. In particular, it is shown that a graph is edgedistanceregular if and only if its kincidence matrix is a polynomial of degree k in A multiplied by the (standard) incidence matrix. Also, the analogue of the spectral excess theorem for distanceregular graphs is proved, so giving a quasispectral characterization of edgedistanceregularity. Finally, it is shown that every nonbipartite graph which is both distanceregular and edgedistanceregular is a generalized odd graph.
* distanceregularity; * local spectra; * predistance polynomials; * the spectral excess theorem; * generalized odd graphs 
When almost distance regularity attains distance regularity
Dalfo Simo, Cristina; Van Dam, Edwin R; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
International Workshop on Optimal Network Topologies
Presentation's date: 20100610
Presentation of work at congresses
View Share Reference managers 
Dual concepts of almost distanceregularity and the spectral excess theorem
Dalfo Simo, Cristina; Van Dam, Edwin R; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
International Workshop on Optimal Network Topologies
Presentation of work at congresses
Access to the full text Share Reference managers 
A mathematical model for dynamic memory networks
Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Serra Albo, Oriol; Andrés Yebra, José Luis
International Workshop on Optimal Network Topologies
Presentation's date: 20100611
Presentation of work at congresses
Read the abstract Access to the full text Share Reference managersThe aim of this paper is to bring together the work done several years ago by M.A. Fiol and the other authors to formulate a quite general mathematical model for a kind of permutation networks known as dynamic memories. A dynamic memory is constituted by an array of cells, each storing one datum, and an interconnection network between the cells that allows the constant circulation of the stored data. The objective is to design the interconnection network in order to have short access time and a simple memory control. We review how most of the proposals of dynamic memories that have appeared in the literature fit in this general model, and how it can be used to design new structures with good access properties. Moreover, using the idea of projecting a digraph onto a de Bruijn digraph, we propose new structures for dynamic memories with vectorial capabilities. Some of these new proposals are based on iterated line digraphs, which have been widely and successfully used by M.A. Fiol and his coauthors to solve many different problems in graph theory. 
Combinatorial vs. Algebraic Characterizations of Completely PseudoRegular Codes
Cámara Vallejo, Marc; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Electronic journal of combinatorics
Date of publication: 20100308
Journal article
View Share Reference managers 
Grafs, amics i coneguts
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
Butlletí de la Societat Catalana de Matemàtiques
Date of publication: 2010
Journal article
Read the abstract Access to the full text Share Reference managersCom és ben sabut, un graf és un objecte matemàtic que modelitza l’existència d’una certa relació entre parells d’elements d’un conjunt donat. Aleshores, és natural que molts dels primers resultats sobre grafs facin referència a relacions entre persones o grups de persones. En aquest article, comentem quatre resultats d’aquest tipus, els quals tenen relació amb diverses teories generals de grafs i les seves aplicacions: el lema de les encaixades de mans (relacionat amb la coloració de grafs i l’àlgebra booleana), un lema sobre els coneguts i desconeguts en una festa (amb la teoria de Ramsey), un lema sobre els amics en comú (amb la distànciaregularitat i la teoria de codis) i el teorema de les noces de Hall (amb la connectivitat de les xarxes). Aquestes quatre àrees de la teoria de grafs, amb problemes sovint fàcils de plantejar però molt difícils de resoldre, s’han desenvolupat extensament i actualment són motiu de nombrosos treballs de recerca. Com a exemples de resultats i problemes representatius d’aquestes àrees, els quals són motiu de discussió en aquest treball que presentem, podem citar els següents: el teorema dels quatre colors (T4C), els nombres de Ramsey, els problemes d’existència de grafs distànciaregulars i de codis completament regulars i, finalment, l’estudi de les propietats topològiques de les xarxes d’interconnexió. 
A simple proof of the spectral excess theorem for distanceregular graphs
Fiol Mora, Miquel Àngel; Gago Alvarez, Silvia; Garriga Valle, Ernest
Linear algebra and its applications
Date of publication: 20100415
Journal article
Read the abstract View Share Reference managersThe spectral excess theorem provides a quasispectral characterization for a (regular) graph Γ with d+1 distinct eigenvalues to be distanceregular graph, in terms of the excess (number of vertices at distance d) of each of its vertices. The original approach, due to Fiol and Garriga in 1997, was obtained by using a local approach, so giving a characterization of the socalled pseudodistanceregularity around a vertex. In this paper we present a new simple projection method based in a global point of view, and where the mean excess plays an essential role. 
Characterizing (l,m)walkregular graphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga, Ernest
Linear algebra and its applications
Date of publication: 2010
Journal article
View Share Reference managers 
The local spectra of regular line graphs
Fiol Mora, Miquel Àngel; Mitjana Riera, Margarida
Discrete mathematics
Date of publication: 201002
Journal article
View Share Reference managers 
The geometry of tspreads in kwalkregular graphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Journal of graph theory
Date of publication: 201008
Journal article
Read the abstract Access to the full text Share Reference managersA graph is walkregular if the number of closed walks of length rooted at a given vertex is a constant through all the vertices for all . For a walkregular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its dspreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a threedimensional case) and we compute its parameters. Moreover, the results are generalized to the case of kwalkregular graphs, a family which includes both walkregular and distanceregular graphs, and their tspreads or vertices at distance t from each other. 
Graph labelings and decompositions by partitioning sets of integers
Moragas Vilarnau, Jordi
Defense's date: 20100614
Department of Applied Mathematics IV, Universitat Politècnica de Catalunya
Theses
Read the abstract Access to the full text Share Reference managersAquest treball és una contribució a l'estudi de diferents problemes que sorgeixen de dues àrees fortament connexes de la Teoria de Grafs: etiquetaments i descomposicions. Molts etiquetaments de grafs deuen el seu origen als presentats l'any 1967 per Rosa. Un d'aquests etiquetaments, àmpliament conegut com a etiquetament graceful, va ser definit originalment com a eina per atacar la conjectura de Ringel, la qual diu que el graf complet d'ordre 2m+1 pot ser descompost en m copies d'un arbre donat de mida m. Aquí, estudiem etiquetaments relacionats que ens donen certes aproximacions a la conjectura de Ringel, així com també a una altra conjectura de Graham i Häggkvist que, en una forma dèbil, demana la descomposició d'un graf bipartit complet per un arbre donat de mida apropiada. Les principals contribucions que hem fet en aquest tema són la prova de la darrera conjectura per grafs bipartits complets del doble de mida essent descompostos per arbres de gran creixement i un nombre primer d'arestes, i la prova del fet que cada arbre és un subarbre gran de dos arbres pels quals les dues conjectures es compleixen respectivament. Aquests resultats estan principalment basats en una aplicació del mètode polinomial d'Alon. Un altre tipus d'etiquetaments, els etiquetaments magic, també són tractats aquí. Motivats per la noció de quadrats màgics de Teoria de Nombres, en aquest tipus d'etiquetaments volem asignar nombres enters a parts del graf (vèrtexs, arestes, o vèrtexs i arestes) de manera que la suma de les etiquetes assignades a certes subestructures del graf sigui constant. Desenvolupem tècniques basades en particions de certs conjunts d'enters amb algunes condicions additives per construir etiquetaments cyclemagic, un nou tipus d'etiquetament introduït en aquest treball i que estén la noció clàssica d'etiquetament magic. Els etiquetaments magic no donen cap descomposició de grafs, però les tècniques usades per obtenirlos estan al nucli d'un altre problema de descomposició, l'ascending subgraph decomposition (ASD). Alavi, Boals, Chartrand, Erdös i Oellerman, van conjecturar l'any 1987 que tot graf té un ASD. Aquí, estudiem l'ASD per grafs bipartits, una classe de grafs per la qual la conjectura encara no ha estat provada. Donem una condició necessària i una de suficient sobre la seqüència de graus d'un estable del graf bipartit de manera que admeti un ASD en que cada factor sigui un star forest. Les tècniques utilitzades estan basades en l'existència de brancaacoloriments en multigrafs bipartits. També tractem amb el sumset partition problem, motivat per la conjectura ASD, que demana una partició de [n] de manera que la suma dels elements de cada part sigui igual a un valor prescrit. Aquí donem la millor condició possible per la versió modular del problema que ens permet provar els millors resultats ja coneguts en el cas enter per n primer. La prova està de nou basada en el mètode polinomial.
This work is a contribution to the study of various problems that arise from two strongly connected areas of the Graph Theory: graph labelings and graph decompositions. Most graph labelings trace their origins to the ones presented in 1967 by Rosa. One of these labelings, widely known as the graceful labeling, originated as a means of attacking the conjecture of Ringel, which states that the complete graph of order 2m+1 can be decomposed into m copies of a given tree of size m. Here, we study related labelings that give some approaches to Ringel's conjecture, as well as to another conjecture by Graham and Häggkvist that, in a weak form, asks for the decomposition of a complete bipartite graph by a given tree of appropriate size. Our main contributions in this topic are the proof of the latter conjecture for double sized complete bipartite graphs being decomposed by trees with large growth and prime number of edges, and the proof of the fact that every tree is a large subtree of two trees for which both conjectures hold respectively. These results are mainly based on a novel application of the socalled polynomial method by Alon. Another kind of labelings, the magic labelings, are also treated. Motivated by the notion of magic squares in Number Theory, in these type of labelings we want to assign integers to the parts of a graph (vertices, edges, or vertices and edges) in such a way that the sums of the labels assigned to certain substructures of the graph remain constant. We develop techniques based on partitions of certain sets of integers with some additive conditions to construct cyclemagic labelings, a new brand introduced in this work that extends the classical magic labelings. Magic labelings do not provide any graph decomposition, but the techniques that we use to obtain them are the core of another decomposition problem, the ascending subgraph decomposition (ASD). In 1987, was conjectured by Alavi, Boals. Chartrand, Erdös and Oellerman that every graph has an ASD. Here, we study ASD of bipartite graphs, a class of graphs for which the conjecture has not been shown to hold. We give a necessary and a sufficient condition on the one sided degree sequence of a bipartite graph in order that it admits an ASD by star forests. Here the techniques are based on the existence of edgecolorings in bipartite multigraphs. Motivated by the ASD conjecture we also deal with the sumset partition problem, which asks for a partition of [n] in such a way that the sum of the elements of each part is equal to a prescribed value. We give a best possible condition for the modular version of the sumset partition problem that allows us to prove the best known results in the integer case for n a prime. The proof is again based on the polynomial method. 
Graphs, Friends and Acquaintances
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
Date: 20100423
Report
Read the abstract Access to the full text Share Reference managersAs is well known, a graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Therefore, it is not surprising that many of the first results concerning graphs made reference to relationships between people or groups of people. In this article, we comment on four results of this kind, which are related to various general theories on graphs and their applications: 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 distanceregularity 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, which are discussed in this paper, we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distanceregular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks. 
On Almost DistanceRegular Graphs
Van Dam, Edwin R; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gorissen, Bram
Date: 20100312
Report
Access to the full text Share Reference managers 
On almost distanceregular graphs
Dalfo Simo, Cristina; Van Dam, Edwin R; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gorissen, Bram
Journal of combinatorial theory. Series A
Date of publication: 2010
Journal article
Read the abstract View Share Reference managersDistanceregular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distanceregular graphs, we study ‘almost distanceregular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distanceregular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walkregular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distanceregularity and walkregularity called mwalkregularity. Another studied concept is that of mpartial distanceregularity or, informally, distanceregularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distanceregularity, such as their common generalization of ( ,m)walkregularity. We introduce the concepts of punctual distanceregularity and punctual walkregularity as a fundament upon which almost distanceregular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distanceregular becomes whole distanceregular. We also give several characterizations of punctually distanceregular graphs that are generalizations of the spectral excess theorem. 
Characterizing (l, m)walkregular graphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Linear algebra and its applications
Date of publication: 20101230
Journal article
View Share Reference managers 
Loadbalanced wavelength assignment strategies for optical burst/packet switching networks
Agusti Torra, Anna; Cervello Pastor, Cristina; Fiol Mora, Miquel Àngel
IET communications
Date of publication: 200903
Journal article
Read the abstract View Share Reference managersLossfree schemes are defined to ensure successful packet/burst transmissions in optical packet/burst switching networks. To this end, they rely on a collisionfree routing and wavelength assignment (CFRWA) scheme combined with simple contention resolution mechanisms that guarantee the absence of losses in intermediate links. Here, the CFRWA problem is studied. In particular, by using graph theory, the problem of finding CFRWA schemes that minimise the number of wavelengths to serve a given traffic matrix is set. The problem is simplified when it is formulated by using predefined sets of noncolliding paths. Within this framework, the problem is shown to be equivalent to finding a given vertexset colouring of the socalled restriction digraph. Here, two heuristic algorithms are proposed to obtain such vertexset colourings. One of them provides a suitable CFRWA without having to solve the minimisation problem. By way of example, the proposed method is applied to the NSFNet and the EON network providing quasioptimal results. 
A Routing and Wavelength Assignment Strategy for Successful Transmission in Optical Networks
Agusti Torra, Anna; Cervello Pastor, Cristina; Fiol Mora, Miquel Àngel
Journal of interconnection networks
Date of publication: 200901
Journal article
View Share Reference managers 
The hierarchical product of graphs
Barriere Figueroa, Eulalia; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
Discrete applied mathematics
Date of publication: 200901
Journal article
View Share Reference managers 
On the hierarchical product of graphs and the generalized binomial tree
Barriere Figueroa, Eulalia; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel
Linear and multilinear algebra
Date of publication: 2009
Journal article
View Share Reference managers 
Number of walks and degree powers in a graph
Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Discrete mathematics
Date of publication: 200904
Journal article
Share Reference managers 
On kWalkRegular graphs
Dalfo Simo, Cristina; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Electronic journal of combinatorics
Date of publication: 200904
Journal article
Share Reference managers 
Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes
Cámara Vallejo, Marc; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Electronic journal of combinatorics
Date of publication: 200907
Journal article
View Share Reference managers
Filter results
UPC network collaboration
Reference managers
Continue