Pasar al contenido principal

ANALISIS DE PATRONES PUNTUALES ESPACIO-TEMPORALES EN NETWORKS; MODELIZACION BAJO NO ESTACIONARIEDAD Y/O ANISOTROPIA, ESTIMACION, PREDICCION Y EVALUACION DE RIESGOS

PID2020-115442RB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE LLEIDA

Resultados relacionados

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

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
The chordal ring (CR) graphs are a well-known family of graphs used to model some interconnection networks for computer systems in which all nodes are in a cycle. Generalizing the CR graphs, in this paper, we introduce the families of chordal multi-ring (CMR), chordal ring mixed (CRM), and chordal multi-ring mixed (CMRM) graphs. In the case of mixed graphs, we can have edges (without direction) and arcs (with direction). The chordal ring and chordal ring mixed graphs are bipartite and 3-regular. They consist of a number r (for 𝑟≥1) of (undirected or directed) cycles with some edges (the chords) joining them. In particular, for CMR, when 𝑟=1, that is, with only one undirected cycle, we obtain the known families of chordal ring graphs. Here, we used plane tessellations to represent our chordal multi-ring graphs. This allowed us to obtain their maximum number of vertices for every given diameter. Additionally, we computationally obtained their minimum diameter for any value of the number of vertices. Moreover, when seen as a lift graph (also called voltage graph) of a base graph on Abelian groups, we obtained closed formulas for the spectrum, that is, the eigenvalue multi-set of its adjacency matrix., This research has been funded by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. M. A. Fiol’s research was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Summary characteristics for multivariate function-valued spatial point process attributes

  • Eckardt, Matthias
  • Comas Rodríguez, Carles
  • Mateu, Jorge
Prompted by modern technologies in data acquisition, the statistical analysis of spatially distributed function-valued quantities has attracted a lot of attention in recent years. In particular, combinations of functional variables and spatial point processes yield a highly challenging instance of such modern spatial data applications. Indeed, the analysis of spatial random point configurations, where the point attributes themselves are functions rather than scalar-valued quantities, is just in its infancy, and extensions to function-valued quantities still remain limited. In this view, we extend current existing first- and second-order summary characteristics for real-valued point attributes to the case where, in addition to every spatial point location, a set of distinct function-valued quantities are available. Providing a flexible treatment of more complex point process scenarios, we build a framework to consider points with multivariate function-valued marks, and develop sets of different cross-function (cross-type and also multi-function cross-type) versions of summary characteristics that allow for the analysis of highly demanding modern spatial point process scenarios. We consider estimators of the theoretical tools and analyse their behaviour through a simulation study and two real data applications., The authors gratefully acknowledge financial support through the German Research Association and the Spanish Ministry of Science. Matthias Eckardt was funded by the Walter Benjamin grant 467634837 from the Deutsche Forschungsgemeinschaft. Jorge Mateu was partially funded by grant PID2019-107392RB-I00, from the Spanish Ministry of Science. Carles Comas was partially funded by grant PID2020-115442RB-I00 from MCIN/AEI/10.13039/ 501100011033 (Spanish Ministry of Science)
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Moore mixed graphs from Cayley graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
A Moore (r; z; k)-mixed graph G has every vertex with undirected degree r, directed in and outdegree z, diameter k, and number of vertices (or order) attaining the corresponding Moore bound M(r; z; k) for mixed graphs. When the order of G is close to M(r; z; k) vertices, we refer to it as an almost Moore graph. The first part of this paper is a survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. Then, in the second part of the paper, we give new results on the bipartite case. First, we show that Moore bipartite mixed graphs with diameter three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1; z; 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups. Our study is based on the line digraph technique, and on some results about when the line digraph of a Cayley digraph is again a Cayley digraph., This research has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RBI00.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On New Record Graphs Close to Bipartite Moore Graphs

  • Araujo Pardo, Martha Gabriela
  • López Lorenzo, Ignacio
The modelling of interconnection networks by graphs motivated the study of several extremal problems that involve well known parameters of a graph (degree, diameter, girth and order) and optimising one of the parameters given restrictions on some of the others. Here we focus on bipartite Moore graphs, that is, bipartite graphs attaining the optimum order, fixed either the degree/diameter or degree/girth. The fact that there are very few bipartite Moore graphs suggests the relaxation of some of the constraints implied by the bipartite Moore bound. First we deal with local bipartite Moore graphs. We find in some cases those local bipartite Moore graphs with local girths as close as possible to the local girths given by a bipartite Moore graph. Second, we construct a family of (q+2)-bipartite graphs of order 2(q2+q+5) and diameter 3, for q a power of prime. These graphs attain the record value for q=9 and improve the values for q=11 and q=13., Research of N. López was supported in part by the MCIN/AEI/10.13039/501100011033 through Grant PID2020-115442RB-I00 (Spanish Ministerio de Ciencia e Innovacion) and research of G. Araujo was supported by PASPA-DGAPA and CONACyT Sabbatical Stay 2020, CONACyT-México under Project 282280, 47510664 and PAPIIT-México under Projects IN107218, IN108121.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Token graphs of cayley graphs as lifts

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
This paper describes a general method for representing k-token graphs of Cayley graphs as lifts of voltage graphs. This allows us to construct line graphs of circulant graphs and Johnson graphs as lift graphs on cyclic groups. As an application of the method, we derive the spectra of the considered token graphs. The method can also be applied to dealing with other matrices, such as the Laplacian or the signless Laplacian, and to construct token digraphs of Cayley digraphs., The research of the first two authors has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020- 115442RB-I00. The second author’s research was also supported by a grant from the Universitat Polit`ecnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023. The third and the fourth authors gratefully acknowledge support for this research from APVV Research Grants 19-0308 and 22-0005, and VEGA Research Grants 1/0567/22 and 1/0069/23.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Note on the product of the largest and the smallest eigenvalue of a graph

  • Abiad, Aida
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this note, we use eigenvalue interlacing to derive an inequality between a graph’s maximum degree and its maximum and minimum adjacency eigenvalues. The equality case is fully characterized., A. Abiad is supported by the Dutch Research Council (NWO) through the grant VI.Vidi.213.085. The research of C. Dalfó and M. A. Fiol is supported by AGAUR from the Catalan Government via the project 2021SGR00434 and MICINN from the Spanish Government via the project PID2020-115442RB-I00. The Universitat Politecnica de Catalunya also supports M. A. Fiol’s research through the grants AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Almost Moore and the largest mixed graphs of diameters two and three

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
Almost Moore mixed graphs appear in the context of the degree/diameter problem as a class of extremal mixed graphs, in the sense that their order is one unit less than the Moore bound for such graphs. The problem of their existence has been considered just for diameter 2. In this paper, we give a complete characterization of these extremal mixed graphs for diameters 2 and 3. We also derive some optimal constructions for other diameters., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the spectra of token graphs of cycles and other graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Messegué, Arnau
The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is a known result that the algebraic connectivity (or second Laplacian eigenvalue) of Fk(G) equals the algebraic connectivity of G. In this paper, we first give results that relate the algebraic connectivities of a token graph and the same graph after removing a vertex. Then, we prove the result on the algebraic connectivity of 2-token graphs for two infinite families: the odd graphs Or for all r, and the multipartite complete graphs Kn for all n1,n2,…,nr In the case of cycles, we present a new method that allows us to compute the whole spectrum of F2(Cn). This method also allows us to obtain closed formulas that give asymptotically exact approximations for most of the eigenvalues of F2(Cn)., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Integer sequences from 𝑘-iterated line digraphs, Conference Information Technologies - Applications and Theory, ITAT 2024

  • Závacká, Dominika
  • Dalfó, Cristina
  • Miguel Ángel, Fiol
In this paper, we focus on integer sequences corresponding to the number of vertices in 𝑘-iterated line digraphs. We begin by introducing the core concepts related to digraphs. Then, we describe a method, proposed by Dalfó and Fiol, for calculating the order of 𝑘-iterated line digraphs. We explore various families of digraphs, such as De Bruijn, Kautz, Cyclic Kautz, and Square-free digraphs. To generate integer sequences representing the number of vertices in 𝑘-iterated line digraphs, we implement an algorithm that constructs induced subdigraphs by not allowing vertices containing forbidden subwords. The results include comparisons of the obtained integer sequences with those in the OEIS database and identification of new integer sequences. Our algorithm is implemented in the computational system GAP., D. Závacká’s research was partially supported by G-24-158-00 and VEGA 1/0437/23. She would like to thank her supervisor Tatiana Jajcayová for her guidance and suggestions. C. Dalfó and M. A. Fiol’s research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. M. A. Fiol’s research was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On inertia and ratio type bounds for the k-independence number of a graph and their relationship

  • Abiad, Aida
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Zeijlemaker, Sjanne
For k≥1, the k-independence number αk of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for αk, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials., The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N. The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On mixed radial Moore graphs of diameter 3

  • Ceresuela, Jesús M.
  • López Lorenzo, Ignacio
  • Chemisana Villegas, Daniel
Radial Moore graphs and digraphs are extremal graphs related to the Moore ones where the distance-preserving spanning tree is preserved for some vertices. This leads to classify them according to their proximity to being a Moore graph or digraph. In this paper we deal with mixed radial Moore graphs, where the mixed setting allows edges and arcs as different elements. An exhaustive computer search shows the top ranked graphs for an specific set of parameters. Moreover, we study the problem of their existence by providing two infinite families for different values of the degrees and diameter 3. One of these families turns out to be optimal., The authors would like to thank “Ministerio de Ciencia e Innovaci´on” of Spain, MCIN/AEI/10.13039/501100011033 (grant references PID2019-111536RBI00 and PID2020-115442RB-I00) and AGAUR (grants references 2017SGR1158 and 2017SGR1276). Research of J. M. Ceresuela was supported by Secretaria d’Universitats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya (grant 2020 FISDU 00596). D. Chemisana thanks “Instituci´o Catalana de Recerca i Estudis Avan¸cats (ICREA)” for the ICREA Acad`emia award.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Factored lifts of graphs and their spectra: the Abelian case

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
In this paper, we introduce the concept of factored lift, associated with a combined voltage graph, as a generalization of the lift graph. We present a new method for computing all the eigenvalues and eigenspaces of factored lifts when the underlying group is Abelian., The first two authors' research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The second author's research was also supported by a grant from the Universitat Politècnica de Catalunya, with reference AGRUPS-2024. The third and fourth authors acknowledge support of this research by the APVV Research Grants 22-0005 and 23-0076, and the VEGA Research Grants 1/0069/23 and 1/0011/25.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Some bounds on the Laplacian eigenvalues of token graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Messegué, Arnau
The k-token graph Fk(G) of a graph G on n vertices is the graph whose vertices are the n k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is known that the algebraic connectivity (or second Laplacian eigen- value) of Fk(G) equals the algebraic connectivity α(G) of G. In this paper, we give some bounds on the (Laplacian) eigenvalues of the k-token graph (including the algebraic connectivity) in terms of the h-token graph, with h ≤ k. For instance, we prove that if λ is an eigenvalue of Fk(G), but not of G, then λ ≥ kα(G) − k + 1. As a consequence, we conclude that if α(G) ≥ k, then α(Fh(G)) = α(G) for every h ≤ k., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Household photovoltaic systems optimization methodology based on graph theory reliability

  • Ceresuela, Jesús M.
  • Chemisana Villegas, Daniel
  • López Lorenzo, Ignacio
A novel passive strategy to overcome the inconveniences of possible failure or underperformance of the components of a household scale photovoltaic (PV) system is proposed. The developed methodology is based on network reliability and determines the optimal array topology to be implemented under certain constraints through the maximization of a merit function that considers three different aspects: the total power that a structure produces, the power per panel ratio and the average reliability of the structure. Every factor is weighted through a parameter that controls its relative importance in the merit function. The restriction implemented in this study corresponds to the inherent limits in the voltage and current input of an inverter. The optimization process has been developed for several scenarios considering different decision criteria. Intuitive results are obtained when the optimization relies on the power per unit module and also when reliability is the main contributor in the merit function. When power production is preferred, structures with large number of panels prove to be the best even when they are asymmetrically connected and thus some panels are underperforming. A case study of a particular inverter has been developed to gain insight in an example, computing the optimal structure in terms of the three parameters., The authors would like to thank ‘‘Ministerio de Ciencia e Innovación’’ of Spain, MCIN/AEI/10.13039/501100011033 (grant references PID2019-111536RB-I00 and PID2020-115442RB-I00). Research of J. M. Ceresuela was supported by Secretaria d’Universi tats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya(grant 2020 FISDU 00596). D. Chemisana thanks ‘‘Institució Catalana de Recerca i Estudis Avançats (ICREA)’’ for the ICREA Acadèmia award.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On two algebras of token graphs

  • Reyes, M. A.
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this article, we describe some properties of the Laplacian matrix Lk of Fk(G) and the Laplacian matrix L & strns;k of the k-token graph Fk(G & strns;) of its complement G & strns; . First, we provide a complete proof of a result from a previous article on the commutativity of the matrices Lk and L & strns;k . Based on this result, fixed the pair (n, k) and the graph G, we introduce a 'local' algebra L(G) , generated by the pair (Lk,L & strns;k) , showing its close relationship with the Bose-Mesner algebra of the Johnson graphs J(n, k). Finally, for fixed (n, k), we present a 'global' algebra A(n,k) that contains L(G) together with the Laplacian and adjacency matrices of the k-token graph of any graph G on n vertices., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. Also, it has a grant from the Research Vice-Rector of UdL.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Modeling road traffic safety based on point patterns of wildlife-vehicle collisions

  • Llagostera Blasco, Pol
  • Comas Rodríguez, Carles
  • López Lorenzo, Ignacio
Wildlife-vehicle collisions represent one of the main coexistence problems that appear between human populations and the environment. In general terms, this affects road safety, wildlife management, and the building of road infrastructures. These accidents are a great danger to the life and safety of car drivers, cause property damage to vehicles, and affect wildlife populations. In this work, we develop a new approach based on algorithms used to obtain minimum paths between vertices in weighted networks to get the optimal (safest) route between two points (departure and destination points) in a road structure based on wildlife-vehicle collision point patterns together with other road variables such as traffic volume (traffic flow information), road speed limits, and vegetation density around roads. For this purpose, we have adapted the road structure into a mathematical linear network as described in the field of Graph Theory and added weights to each linear segment based on the intensity of accidents. Then, the resulting network structure allows us to consider some graph theory methodologies to manipulate and apply different calculations to analyze the network. This new approach has been illustrated with a real data set involving the locations of 491 wildlife-vehicle collisions in a square region (40 km × 40 km) around the city of Lleida, during the period 2010–2014, in the region of Catalonia, North-East of Spain. Our results show the usefulness of our new approach to model road traffic safety based on point patterns of wildlife-vehicle collisions. As such, optimal path selection on linear networks based on wildlife-vehicle collisions can be considered to find the safest path between two pairs of points, avoiding more dangerous routes and even routes containing hotspots of accidents., The authors acknowledge the support of the MCIN/AEI/10.13039/501100011033 through Grant PID2020-115442RB-I00, from the Spanish Ministry of Science and Innovation.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Nonexistence of Almost Moore Digraphs of Degrees 4 and 5 with Self-Repeats

  • López Lorenzo, Ignacio
  • Messegué, Arnau
  • Miret, Josep M. (Josep Maria)
An almost Moore (d, k)-digraph is a regular digraph of degree d > 1, diameter k > 1 and order N(d, k) = d + d2 + · · · + dk . So far, their existence has only been shown for k = 2, whilst it is known that there are no such digraphs for k = 3, 4 and for d = 2, 3 when k ! 3. Furthermore, under certain assumptions, the nonexistence for the remaining cases has also been shown. In this paper, we prove that (4, k) and (5, k)-almost Moore digraphs with self-repeats do not exist for k ! 5., Supported in part by grants PID2020-115442RB-I00 and 2021SGR-00434. Supported in part by grants Margarita Salaand 2021SGR-00434. Supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On large regular (1, 1, k)-mixed graphs

  • Dalfó, Cristina
  • Erskine, G.
  • Exoo, G.
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
  • Massegué Buisan, Arnau
  • Tuite, J.
An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N., The research of C. Dalfó, M. A. Fiol, N. López, and A. Messegué has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RBI00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica, Catalonia with references AGRUPS-2022 and AGRUPS-2023. J. Tuite was supported by EPSRC grant EP/W522338/1.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Graph Theory-Based Characterization and Classification of Household Photovoltaics

  • Ceresuela, Jesús M.
  • Chemisana Villegas, Daniel
  • López Lorenzo, Ignacio
With the clear goal of improving photovoltaic (PV) technology performance towards nearly-zero energy buildings, a graph theory-based model that characterizes photovoltaic panel structures is developed. An algorithm to obtain all possible configurations of a given number of PV panels is presented and the results are exposed for structures using 3 to 7 panels. Two different classifications of all obtained structures are carried out: the first one regarding the maximum power they can produce and the second according to their capability to produce energy under a given probability that the solar panels will fail. Finally, both classifications are considered simultaneously through the expected value of power production. This creates structures that are, at the same time, reliable and efficient in terms of production. The parallel associations turn out to be optimal, but some other less expected configurations prove to be rated high., The authors would like to thank “Ministerio de Economía y Competitividad” and “Ministerio de Ciencia e Innovación” of Spain for the funding (grant reference ENE2016-81040-R and PID2019-111536RB-I00). Research of J. M. Ceresuela was supported by Secretaria d’Universitats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya (grant 2020 FISDU 00596). D. Chemisana thanks ”Institució Catalana de Recerca i Estudis Avançats (ICREA)” for the ICREA Acadèmia award. Research of N.López was supported in part by grant MTM2017-86767-R and PID2020-115442RB-I00 (Spanish Ministerio de Ciencia e Innovacion).
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' MCK(d,ℓ)MCK(d,ℓ), and it is derived from the Kautz digraphs K(d,ℓ)K(d,ℓ) and from the so-called cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ). The cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ) were defined as the digraphs whose vertices are labeled by all possible sequences a1…aℓa1…aℓ of length ℓℓ, such that each character aiai is chosen from an alphabet of d+1d+1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a1≠aℓa1≠aℓ. Their arcs are between vertices a1a2…aℓa1a2…aℓ and a2…aℓaℓ+1a2…aℓaℓ+1, with a1≠aℓa1≠aℓ and a2≠aℓ+1a2≠aℓ+1. Since CK(d,ℓ)CK(d,ℓ) do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that MCK(d,ℓ)MCK(d,ℓ) are dd-out-regular. Moreover, for t≥1t≥1, we compute the number of vertices of the iterated line digraphs Lt(CK(d,ℓ))Lt(CK(d,ℓ))., The research of C. Dalfo has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, grant PGC2018-095471-BI00 funded by MCIN/AEI/10.13039/501100011033 and ERDF “A way of making Europe”, by the European Union, and grant PID2020-115442RB-I00 from MCIN/AEI/10.13039/501100011033. The research of C. Huemer was supported by PID2019-104129GB-I00/AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. This work has 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
Publicación Artículo científico (JournalArticle)

Modeling road traffic safety based on point patterns of wildlife-vehicle collisions

  • Llagostera Blasco, Pol
  • Comas Rodríguez, Carles
  • López Lorenzo, Ignacio
Wildlife-vehicle collisions represent one of the main coexistence problems that appear between human populations and the environment. In general terms, this affects road safety, wildlife management, and the building of road infrastructures. These accidents are a great danger to the life and safety of car drivers, cause property damage to vehicles, and affect wildlife populations. In this work, we develop a new approach based on algorithms used to obtain minimum paths between vertices in weighted networks to get the optimal (safest) route between two points (departure and destination points) in a road structure based on wildlife-vehicle collision point patterns together with other road variables such as traffic volume (traffic flow information), road speed limits, and vegetation density around roads. For this purpose, we have adapted the road structure into a mathematical linear network as described in the field of Graph Theory and added weights to each linear segment based on the intensity of accidents. Then, the resulting network structure allows us to consider some graph theory methodologies to manipulate and apply different calculations to analyze the network. This new approach has been illustrated with a real data set involving the locations of 491 wildlife-vehicle collisions in a square region (40 km × 40 km) around the city of Lleida, during the period 2010–2014, in the region of Catalonia, North-East of Spain. Our results show the usefulness of our new approach to model road traffic safety based on point patterns of wildlife-vehicle collisions. As such, optimal path selection on linear networks based on wildlife-vehicle collisions can be considered to find the safest path between two pairs of points, avoiding more dangerous routes and even routes containing hotspots of accidents., The authors acknowledge the support of the MCIN/AEI/10.13039/501100011033 through Grant PID2020-115442RB-I00, from the Spanish Ministry of Science and Innovation.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Graph Theory-Based Characterization and Classification of Household Photovoltaics

  • Ceresuela, Jesús M.
  • Chemisana Villegas, Daniel
  • López Lorenzo, Ignacio
With the clear goal of improving photovoltaic (PV) technology performance towards nearly-zero energy buildings, a graph theory-based model that characterizes photovoltaic panel structures is developed. An algorithm to obtain all possible configurations of a given number of PV panels is presented and the results are exposed for structures using 3 to 7 panels. Two different classifications of all obtained structures are carried out: the first one regarding the maximum power they can produce and the second according to their capability to produce energy under a given probability that the solar panels will fail. Finally, both classifications are considered simultaneously through the expected value of power production. This creates structures that are, at the same time, reliable and efficient in terms of production. The parallel associations turn out to be optimal, but some other less expected configurations prove to be rated high., The authors would like to thank “Ministerio de Economía y Competitividad” and “Ministerio de Ciencia e Innovación” of Spain for the funding (grant reference ENE2016-81040-R and PID2019-111536RB-I00). Research of J. M. Ceresuela was supported by Secretaria d’Universitats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya (grant 2020 FISDU 00596). D. Chemisana thanks ”Institució Catalana de Recerca i Estudis Avançats (ICREA)” for the ICREA Acadèmia award. Research of N.López was supported in part by grant MTM2017-86767-R and PID2020-115442RB-I00 (Spanish Ministerio de Ciencia e Innovacion).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Note on the product of the largest and the smallest eigenvalue of a graph

  • Abiad, Aida
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this note, we use eigenvalue interlacing to derive an inequality between a graph’s maximum degree and its maximum and minimum adjacency eigenvalues. The equality case is fully characterized., A. Abiad is supported by the Dutch Research Council (NWO) through the grant VI.Vidi.213.085. The research of C. Dalfó and M. A. Fiol is supported by AGAUR from the Catalan Government via the project 2021SGR00434 and MICINN from the Spanish Government via the project PID2020-115442RB-I00. The Universitat Politecnica de Catalunya also supports M. A. Fiol’s research through the grants AGRUPS-2022 and AGRUPS-2023.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On two algebras of token graphs

  • Reyes, M. A.
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this article, we describe some properties of the Laplacian matrix Lk of Fk(G) and the Laplacian matrix L & strns;k of the k-token graph Fk(G & strns;) of its complement G & strns; . First, we provide a complete proof of a result from a previous article on the commutativity of the matrices Lk and L & strns;k . Based on this result, fixed the pair (n, k) and the graph G, we introduce a 'local' algebra L(G) , generated by the pair (Lk,L & strns;k) , showing its close relationship with the Bose-Mesner algebra of the Johnson graphs J(n, k). Finally, for fixed (n, k), we present a 'global' algebra A(n,k) that contains L(G) together with the Laplacian and adjacency matrices of the k-token graph of any graph G on n vertices., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. Also, it has a grant from the Research Vice-Rector of UdL.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Moore mixed graphs from Cayley graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
A Moore (r; z; k)-mixed graph G has every vertex with undirected degree r, directed in and outdegree z, diameter k, and number of vertices (or order) attaining the corresponding Moore bound M(r; z; k) for mixed graphs. When the order of G is close to M(r; z; k) vertices, we refer to it as an almost Moore graph. The first part of this paper is a survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. Then, in the second part of the paper, we give new results on the bipartite case. First, we show that Moore bipartite mixed graphs with diameter three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1; z; 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups. Our study is based on the line digraph technique, and on some results about when the line digraph of a Cayley digraph is again a Cayley digraph., This research has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RBI00.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Nonexistence of Almost Moore Digraphs of Degrees 4 and 5 with Self-Repeats

  • López Lorenzo, Ignacio
  • Messegué, Arnau
  • Miret, Josep M. (Josep Maria)
An almost Moore (d, k)-digraph is a regular digraph of degree d > 1, diameter k > 1 and order N(d, k) = d + d2 + · · · + dk . So far, their existence has only been shown for k = 2, whilst it is known that there are no such digraphs for k = 3, 4 and for d = 2, 3 when k ! 3. Furthermore, under certain assumptions, the nonexistence for the remaining cases has also been shown. In this paper, we prove that (4, k) and (5, k)-almost Moore digraphs with self-repeats do not exist for k ! 5., Supported in part by grants PID2020-115442RB-I00 and 2021SGR-00434. Supported in part by grants Margarita Salaand 2021SGR-00434. Supported in part by grants PID2021-124613OB-I00 and 2021SGR-00434
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' MCK(d,ℓ)MCK(d,ℓ), and it is derived from the Kautz digraphs K(d,ℓ)K(d,ℓ) and from the so-called cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ). The cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ) were defined as the digraphs whose vertices are labeled by all possible sequences a1…aℓa1…aℓ of length ℓℓ, such that each character aiai is chosen from an alphabet of d+1d+1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a1≠aℓa1≠aℓ. Their arcs are between vertices a1a2…aℓa1a2…aℓ and a2…aℓaℓ+1a2…aℓaℓ+1, with a1≠aℓa1≠aℓ and a2≠aℓ+1a2≠aℓ+1. Since CK(d,ℓ)CK(d,ℓ) do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that MCK(d,ℓ)MCK(d,ℓ) are dd-out-regular. Moreover, for t≥1t≥1, we compute the number of vertices of the iterated line digraphs Lt(CK(d,ℓ))Lt(CK(d,ℓ))., The research of C. Dalfo has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, grant PGC2018-095471-BI00 funded by MCIN/AEI/10.13039/501100011033 and ERDF “A way of making Europe”, by the European Union, and grant PID2020-115442RB-I00 from MCIN/AEI/10.13039/501100011033. The research of C. Huemer was supported by PID2019-104129GB-I00/AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. This work has 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
Publicación Artículo científico (JournalArticle)

Token graphs of cayley graphs as lifts

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
This paper describes a general method for representing k-token graphs of Cayley graphs as lifts of voltage graphs. This allows us to construct line graphs of circulant graphs and Johnson graphs as lift graphs on cyclic groups. As an application of the method, we derive the spectra of the considered token graphs. The method can also be applied to dealing with other matrices, such as the Laplacian or the signless Laplacian, and to construct token digraphs of Cayley digraphs., The research of the first two authors has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020- 115442RB-I00. The second author’s research was also supported by a grant from the Universitat Polit`ecnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023. The third and the fourth authors gratefully acknowledge support for this research from APVV Research Grants 19-0308 and 22-0005, and VEGA Research Grants 1/0567/22 and 1/0069/23.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On mixed radial Moore graphs of diameter 3

  • Ceresuela, Jesús M.
  • López Lorenzo, Ignacio
  • Chemisana Villegas, Daniel
Radial Moore graphs and digraphs are extremal graphs related to the Moore ones where the distance-preserving spanning tree is preserved for some vertices. This leads to classify them according to their proximity to being a Moore graph or digraph. In this paper we deal with mixed radial Moore graphs, where the mixed setting allows edges and arcs as different elements. An exhaustive computer search shows the top ranked graphs for an specific set of parameters. Moreover, we study the problem of their existence by providing two infinite families for different values of the degrees and diameter 3. One of these families turns out to be optimal., The authors would like to thank “Ministerio de Ciencia e Innovaci´on” of Spain, MCIN/AEI/10.13039/501100011033 (grant references PID2019-111536RBI00 and PID2020-115442RB-I00) and AGAUR (grants references 2017SGR1158 and 2017SGR1276). Research of J. M. Ceresuela was supported by Secretaria d’Universitats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya (grant 2020 FISDU 00596). D. Chemisana thanks “Instituci´o Catalana de Recerca i Estudis Avan¸cats (ICREA)” for the ICREA Acad`emia award.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On inertia and ratio type bounds for the k-independence number of a graph and their relationship

  • Abiad, Aida
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Zeijlemaker, Sjanne
For k≥1, the k-independence number αk of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for αk, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials., The research of Aida Abiad is partially supported by the FWO, Belgium grant 1285921N. The research of Cristina Dalfó and Miquel Àngel Fiol has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Household photovoltaic systems optimization methodology based on graph theory reliability

  • Ceresuela, Jesús M.
  • Chemisana Villegas, Daniel
  • López Lorenzo, Ignacio
A novel passive strategy to overcome the inconveniences of possible failure or underperformance of the components of a household scale photovoltaic (PV) system is proposed. The developed methodology is based on network reliability and determines the optimal array topology to be implemented under certain constraints through the maximization of a merit function that considers three different aspects: the total power that a structure produces, the power per panel ratio and the average reliability of the structure. Every factor is weighted through a parameter that controls its relative importance in the merit function. The restriction implemented in this study corresponds to the inherent limits in the voltage and current input of an inverter. The optimization process has been developed for several scenarios considering different decision criteria. Intuitive results are obtained when the optimization relies on the power per unit module and also when reliability is the main contributor in the merit function. When power production is preferred, structures with large number of panels prove to be the best even when they are asymmetrically connected and thus some panels are underperforming. A case study of a particular inverter has been developed to gain insight in an example, computing the optimal structure in terms of the three parameters., The authors would like to thank ‘‘Ministerio de Ciencia e Innovación’’ of Spain, MCIN/AEI/10.13039/501100011033 (grant references PID2019-111536RB-I00 and PID2020-115442RB-I00). Research of J. M. Ceresuela was supported by Secretaria d’Universi tats i Recerca del Departament d’Empresa i Coneixement de la Generalitat de Catalunya(grant 2020 FISDU 00596). D. Chemisana thanks ‘‘Institució Catalana de Recerca i Estudis Avançats (ICREA)’’ for the ICREA Acadèmia award.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the spectra of token graphs of cycles and other graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Messegué, Arnau
The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is a known result that the algebraic connectivity (or second Laplacian eigenvalue) of Fk(G) equals the algebraic connectivity of G. In this paper, we first give results that relate the algebraic connectivities of a token graph and the same graph after removing a vertex. Then, we prove the result on the algebraic connectivity of 2-token graphs for two infinite families: the odd graphs Or for all r, and the multipartite complete graphs Kn for all n1,n2,…,nr In the case of cycles, we present a new method that allows us to compute the whole spectrum of F2(Cn). This method also allows us to obtain closed formulas that give asymptotically exact approximations for most of the eigenvalues of F2(Cn)., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Some bounds on the Laplacian eigenvalues of token graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Messegué, Arnau
The k-token graph Fk(G) of a graph G on n vertices is the graph whose vertices are the n k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is known that the algebraic connectivity (or second Laplacian eigen- value) of Fk(G) equals the algebraic connectivity α(G) of G. In this paper, we give some bounds on the (Laplacian) eigenvalues of the k-token graph (including the algebraic connectivity) in terms of the h-token graph, with h ≤ k. For instance, we prove that if λ is an eigenvalue of Fk(G), but not of G, then λ ≥ kα(G) − k + 1. As a consequence, we conclude that if α(G) ≥ k, then α(Fh(G)) = α(G) for every h ≤ k., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Factored lifts of graphs and their spectra: the Abelian case

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
In this paper, we introduce the concept of factored lift, associated with a combined voltage graph, as a generalization of the lift graph. We present a new method for computing all the eigenvalues and eigenspaces of factored lifts when the underlying group is Abelian., The first two authors' research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The second author's research was also supported by a grant from the Universitat Politècnica de Catalunya, with reference AGRUPS-2024. The third and fourth authors acknowledge support of this research by the APVV Research Grants 22-0005 and 23-0076, and the VEGA Research Grants 1/0069/23 and 1/0011/25.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On large regular (1, 1, k)-mixed graphs

  • Dalfó, Cristina
  • Erskine, G.
  • Exoo, G.
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
  • Massegué Buisan, Arnau
  • Tuite, J.
An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N., The research of C. Dalfó, M. A. Fiol, N. López, and A. Messegué has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RBI00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica, Catalonia with references AGRUPS-2022 and AGRUPS-2023. J. Tuite was supported by EPSRC grant EP/W522338/1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Summary characteristics for multivariate function-valued spatial point process attributes

  • Eckardt, Matthias
  • Comas Rodríguez, Carles
  • Mateu, Jorge
Prompted by modern technologies in data acquisition, the statistical analysis of spatially distributed function-valued quantities has attracted a lot of attention in recent years. In particular, combinations of functional variables and spatial point processes yield a highly challenging instance of such modern spatial data applications. Indeed, the analysis of spatial random point configurations, where the point attributes themselves are functions rather than scalar-valued quantities, is just in its infancy, and extensions to function-valued quantities still remain limited. In this view, we extend current existing first- and second-order summary characteristics for real-valued point attributes to the case where, in addition to every spatial point location, a set of distinct function-valued quantities are available. Providing a flexible treatment of more complex point process scenarios, we build a framework to consider points with multivariate function-valued marks, and develop sets of different cross-function (cross-type and also multi-function cross-type) versions of summary characteristics that allow for the analysis of highly demanding modern spatial point process scenarios. We consider estimators of the theoretical tools and analyse their behaviour through a simulation study and two real data applications., The authors gratefully acknowledge financial support through the German Research Association and the Spanish Ministry of Science. Matthias Eckardt was funded by the Walter Benjamin grant 467634837 from the Deutsche Forschungsgemeinschaft. Jorge Mateu was partially funded by grant PID2019-107392RB-I00, from the Spanish Ministry of Science. Carles Comas was partially funded by grant PID2020-115442RB-I00 from MCIN/AEI/10.13039/ 501100011033 (Spanish Ministry of Science)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Integer sequences from 𝑘-iterated line digraphs, Conference Information Technologies - Applications and Theory, ITAT 2024

  • Závacká, Dominika
  • Dalfó, Cristina
  • Miguel Ángel, Fiol
In this paper, we focus on integer sequences corresponding to the number of vertices in 𝑘-iterated line digraphs. We begin by introducing the core concepts related to digraphs. Then, we describe a method, proposed by Dalfó and Fiol, for calculating the order of 𝑘-iterated line digraphs. We explore various families of digraphs, such as De Bruijn, Kautz, Cyclic Kautz, and Square-free digraphs. To generate integer sequences representing the number of vertices in 𝑘-iterated line digraphs, we implement an algorithm that constructs induced subdigraphs by not allowing vertices containing forbidden subwords. The results include comparisons of the obtained integer sequences with those in the OEIS database and identification of new integer sequences. Our algorithm is implemented in the computational system GAP., D. Závacká’s research was partially supported by G-24-158-00 and VEGA 1/0437/23. She would like to thank her supervisor Tatiana Jajcayová for her guidance and suggestions. C. Dalfó and M. A. Fiol’s research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. M. A. Fiol’s research was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
The chordal ring (CR) graphs are a well-known family of graphs used to model some interconnection networks for computer systems in which all nodes are in a cycle. Generalizing the CR graphs, in this paper, we introduce the families of chordal multi-ring (CMR), chordal ring mixed (CRM), and chordal multi-ring mixed (CMRM) graphs. In the case of mixed graphs, we can have edges (without direction) and arcs (with direction). The chordal ring and chordal ring mixed graphs are bipartite and 3-regular. They consist of a number r (for 𝑟≥1) of (undirected or directed) cycles with some edges (the chords) joining them. In particular, for CMR, when 𝑟=1, that is, with only one undirected cycle, we obtain the known families of chordal ring graphs. Here, we used plane tessellations to represent our chordal multi-ring graphs. This allowed us to obtain their maximum number of vertices for every given diameter. Additionally, we computationally obtained their minimum diameter for any value of the number of vertices. Moreover, when seen as a lift graph (also called voltage graph) of a base graph on Abelian groups, we obtained closed formulas for the spectrum, that is, the eigenvalue multi-set of its adjacency matrix., This research has been funded by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. M. A. Fiol’s research was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On New Record Graphs Close to Bipartite Moore Graphs

  • Araujo Pardo, Martha Gabriela
  • López Lorenzo, Ignacio
The modelling of interconnection networks by graphs motivated the study of several extremal problems that involve well known parameters of a graph (degree, diameter, girth and order) and optimising one of the parameters given restrictions on some of the others. Here we focus on bipartite Moore graphs, that is, bipartite graphs attaining the optimum order, fixed either the degree/diameter or degree/girth. The fact that there are very few bipartite Moore graphs suggests the relaxation of some of the constraints implied by the bipartite Moore bound. First we deal with local bipartite Moore graphs. We find in some cases those local bipartite Moore graphs with local girths as close as possible to the local girths given by a bipartite Moore graph. Second, we construct a family of (q+2)-bipartite graphs of order 2(q2+q+5) and diameter 3, for q a power of prime. These graphs attain the record value for q=9 and improve the values for q=11 and q=13., Research of N. López was supported in part by the MCIN/AEI/10.13039/501100011033 through Grant PID2020-115442RB-I00 (Spanish Ministerio de Ciencia e Innovacion) and research of G. Araujo was supported by PASPA-DGAPA and CONACyT Sabbatical Stay 2020, CONACyT-México under Project 282280, 47510664 and PAPIIT-México under Projects IN107218, IN108121.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Almost Moore and the largest mixed graphs of diameters two and three

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
Almost Moore mixed graphs appear in the context of the degree/diameter problem as a class of extremal mixed graphs, in the sense that their order is one unit less than the Moore bound for such graphs. The problem of their existence has been considered just for diameter 2. In this paper, we give a complete characterization of these extremal mixed graphs for diameters 2 and 3. We also derive some optimal constructions for other diameters., This research has been supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00. The research of M. A. Fiol was also supported by a grant from the Universitat Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023.