Pasar al contenido principal

ESTUDIO MATEMATICO DE LOS FALLOS EN CASCADA EN SISTEMAS COMPLEJOS MEDIANTE INVARIANTES Y CENTRALIDADES EN GRAFOS. APLICACIONES A REDES REALES.

PGC2018-095471-B-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Generación de Conocimiento y Fortalecimiento Científico y Tecnológico del Sistema de I+D+i
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2018
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

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

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. 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. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the spectra and spectral radii of token graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G), has as vertices the (n/k) k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of Fk(G) in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of Fk(G) is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed., The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-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)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C-local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Bipartite biregular Moore graphs

  • Araujo Pardo, Martha Gabriela
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
A bipartite graph G=(V,E) with V=V1 U V2 is biregular if all the vertices of a stable set Vi have the same degree ri for i=1,2. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and Fàbrega. Besides, we propose some constructions of bipartite biregular graphs with diameter d and large number of vertices N(r1,r2;d), together with their spectra. In some cases of diameters d=3, 4, and 5, the new graphs attaining the Moore bound are unique up to isomorphism., The research of the first author is supported by CONACyT-México under Project 282280 and PAPIIT-México under Project IN101821, PASPA-DGAPA, and CONACYT Sabbatical Year 2020. The research of the second and third authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the second and fourth authors is supported by MICINN from the Spanish Government under project MTM2017-83271-R.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. Although most of the models are based on stochastic methods, some deterministic constructions have been recently proposed, because this allows a better computation of their properties. Here a new deterministic family of hierarchical networks is presented, which generalizes most of the previous proposals, such as the so-called binomial tree. The obtained graphs can be seen as graphs on alphabets (where vertices are labeled with words of a given alphabet, and the edges are defined by a specific rule relating different words). This allows us the characterization of their main distance-related parameters, such as the radius and diameter. Moreover, as a by-product, an efficient shortest-path local algorithm is proposed., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spec-tra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regularor not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. Research of the two first authors has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (D ) , is the minimum size of all the identifying codes of D . We establish for digraphs without digons with both vertices of in-degree one that −→ γID (LD ) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show that −→ γID (LD ) attains the equality for a digraph having a 1- factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

New results for the Mondrian art problem

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
The Mondrian problem consists of dissecting a square of side length n ∈ N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n ∈ N. We provide a sequence of square partitions such that d(n)/n2 tends to zero for n large enough. For the case of 'perfect' partitions, that is, with d(n) = 0, we show that, for any fixed powers s1, . . . , sm, a square with side length n = p s1 1 · · · p smm , can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n ≤ x) of squares not having a perfect partition, we prove that its 'density' n(x) x is asymptotic to (log(log(x))2 2 log x , which improves previous results., The research of C. Dalfó and N. López has been partially supported by grant MTM2017-86767-R (Spanish Ministerio de Ciencia e Innovación). The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by Spanish Ministerio de Ciencia e Innovación from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
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.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Huemer, Clemens|||0000-0001-7557-0823
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4, We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph 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. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that , the Laplacian spectrum of is contained in the Laplacian spectrum of . We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph and the star , respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement . This generalizes to tokens graphs a well-known property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of . Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Award-winning
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Discovering important nodes of complex networks based on laplacian spectra

  • Moradi Amani, Ali
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Jalili, Mahdi
  • Chen, Guanrong
  • Yu, Xinghuo
  • Stone, Lewi
© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Knowledge of the Laplacian eigenvalues of a network provides important insights into its structural features and dynamical behaviours. Node or link removal caused by possible outage events, such as mechanical and electrical failures or malicious attacks, significantly impacts the Laplacian spectra. This can also happen due to intentional node removal against which, increasing the algebraic connectivity is desired. In this article, an analytical metric is proposed to measure the effect of node removal on the Laplacian eigenvalues of the network. The metric is formulated based on the local multiplicity of each eigenvalue at each node, so that the effect of node removal on any particular eigenvalues can be approximated using only one single eigen-decomposition of the Laplacian matrix. The metric is applicable to undirected networks as well as strongly-connected directed ones. It also provides a reliable approximation for the “Laplacian energy” of a network. The performance of the metric is evaluated for several synthetic networks and also the American Western States power grid. Results show that this metric has a nearly perfect precision in correctly predicting the most central nodes, and significantly outperforms other comparable heuristic methods., This research was partly supported by the Erasmus+ KA107 grant. AMA, MJ, LS and XY were supported by the Australian Research Council through project No. DP170102303. MJ and XY are also supported by the Australian Research Council through project No. DP200101199. MAF was supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government with the European Regional Development Fund under project PGC2018-095471-B-I00, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Huemer, Clemens|||0000-0001-7557-0823
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' M C K ( d , l ) , and it is derived from the Kautz digraphs K ( d , l ) and from the so-called cyclic Kautz digraphs C K ( d , l ) . The cyclic Kautz digraphs C K ( d , l ) were defined as the digraphs whose vertices are labeled by all possible sequences a 1 … a l of length l , such that each character a i is chosen from an alphabet of d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a 1 ¿ a l . Their arcs are between vertices a 1 a 2 … a l and a 2 … a l a l + 1 , with a 1 ¿ a l and a 2 ¿ a l + 1 . Since C K ( d , l ) 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 M C K ( d , l ) are d -out-regular. Moreover, for t = 1 , we compute the number of vertices of the iterated line digraphs L t ( C K ( d , l ) ) ., The research of C. Dalfó has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under projects MTM2017-83271-R and PGC2018-095471-B-I00. 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 .
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Approximation and decomposition in lattices of clutters

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mier Vinué, Anna de|||0000-0002-2817-7807
A clutter on O is a family of subsets of O that are incomparable under inclusion. Given a collection S of clutters on O and another clutter ¿ on O, we study the problem of approximating and decomposing ¿ in terms of the clutters in S. We want to guarantee when these approximations exist not only for a single element ¿, but for all ¿ that belong to a family of clutters . We use the lattice structure of the collection of clutters to show that the existence of such approximations and decompositions for every clutter ¿ is equivalent to the fact that S contains a given family of irreducible elements determined by S and . We explicitly compute these irreducible families in some cases and apply our results to clutters arising from discrete objects such as matroids, graphs and secret sharing schemes., This work was partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under projects PGC2018-095471-B-I00 and PID2020-113082GB-I00; by AGAUR, Generalitat de Catalunya, from the Catalan Government under projects SGR-Cat 2021 00595 and SGR-Cat 2021 00585; by Universitat Politècnica de Catalunya under funds AGRUPUPC., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On symmetric association schemes and associated quotient-polynomial graphs

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Penjic, Safet
Let denote an undirected, connected, regular graph with vertex set , adjacency matrix , and distinct eigenvalues. Let denote the subalgebra of generated by . We refer to as the adjacency algebra of . In this paper we investigate algebraic and combinatorial structure of for which the adjacency algebra is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) has a standard basis ; (ii) for every vertex there exists identical distance-faithful intersection diagram of with cells; (iii) the graph is quotient-polynomial; and (iv) if we pick then has distinct eigenvalues if and only if . We describe the combinatorial structure of quotient-polynomial graphs with diameter and distinct eigenvalues. As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether is distance-regular or not and, more generally, which distance- matrices are polynomial in , giving also these polynomials., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The second author acknowledges the financial support from the Slovenian Research Agency (research program P1-0285 and research project J1-1695)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

  • Abiad, Aida
  • Coutinho, Gabriel
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Nogueira, Bruno
  • Zeijlemaker, Shanne
© 2022 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, The k-thpower of a graph G=(V,E), G^k, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of G^k which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well., The research of A. Abiad is partially supported by the FWO grant 1285921N. A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT. This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. B. Nogueira acknowledges grant PRPQ/ADRC from UFMG. The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Diego Gutiérrez, Víctor
The spectrum of a graph usually provides a lot of information about its combinatorial structure. Moreover,from the spectrum, the so-called predistance polynomials can be defined, as a generalization, for any graph, of the distancepolynomials of a distance-regular graph. Going further, the preintersection numbers generalize the intersection numbers ofa distance-regular graph. This paper describes, for any graph, the closed relationships between its spectrum, predistancepolynomials, and preintersection numbers. Then, some applications to derive combinatorial properties of the given graph,most of them related to some fundamental characterizations of distance-regularity, are presented. In particular, the so-called‘spectral excess theorem’ is revisited. This result states that a connected regular graph is distance-regular if and only if itsspectral excess, which is a value computed from the spectrum, equals the average excess, that is, the mean of the numbers ofvertices at maximum distance from every vertex., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the spectra and spectral radii of token graphs

  • Reyes Quiróz, Mónica Andrea
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
The version of record of this article, first published inBoletín de la Sociedad Matemática Mexicana, is available online at Publisher’s website: http://dx.doi.org/10.1007/s40590-023-00583-3, Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by , has as vertices the k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed., The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-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., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Martínez Barona, Berenice|||0000-0003-4336-6881
© 2020 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Given an integer ` = 1, a (1, = `)-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhood within C. In this paper, we prove that every k-iterated line digraph of minimum in-degree at least 2 and k = 2, or minimum indegree at least 3 and k = 1, admits a (1, = `)-identifying code with ` = 2, and in any case it does not admit a (1, = `)-identifying code for ` = 3. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087. The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. B. Martínez-Barona has received funding from the scholarship 254379/438356 from CONACYT from Mexico. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs and to a recent known family of mixed graphs (having edges with and without direction). As a byproduct, the existence of perfect codes in allows us to give a lower bound for the multiplicity of its eigenvalue -1., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Pavlíková, Sona
  • Siran, Josef
This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-021-01049-3, We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The authors S. Pavl´ıkov´a and J. Sir´aˇn acknowledge support from the ˇ APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the algebraic connectivity of some token graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
The k-token graph 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. It was proved that the algebraic connectivity of equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Biological basis of extensive pleiotropy between blood traits and cancer risk

  • Pardo Cea, Miguel Angel
  • Farré Ramon, Xavier
  • Esteve, Anna
  • Palade, Joanna
  • Espín García, Roderic
  • Alsop, Eric
  • Alorda Carreras, Marc
  • Blay Magriñá, Natàlia
  • Baiges Carrasco, Alexandra
  • Comellas Padró, Francesc de Paula|||0000-0003-4523-0240
  • de Cid, Rafael
  • Pujana, Miguel Angel
Background The immune system has a central role in preventing carcinogenesis. Alteration of systemic immune cell levels may increase cancer risk. However, the extent to which common genetic variation influences blood traits and cancer risk remains largely undetermined. Here, we identify pleiotropic variants and predict their underlying molecular and cellular alterations. Methods Multivariate Cox regression was used to evaluate associations between blood traits and cancer diagnosis in cases in the UK Biobank. Shared genetic variants were identified from the summary statistics of the genome-wide association studies of 27 blood traits and 27 cancer types and subtypes, applying the conditional/conjunctional falsediscovery rate approach. Analysis of genomic positions, expression quantitative trait loci, enhancers, regulatory marks, functionally defined gene sets, and bulk- and single-cell expression profiles predicted the biological impact of pleiotropic variants. Plasma small RNAs were sequenced to assess association with cancer diagnosis. Results The study identified 4093 common genetic variants, involving 1248 gene loci, that contributed to blood– cancer pleiotropism. Genomic hotspots of pleiotropism include chromosomal regions 5p15-TERT and 6p21-HLA. Genes whose products are involved in regulating telomere length are found to be enriched in pleiotropic variants. Pleiotropic gene candidates are frequently linked to transcriptional programs that regulate hematopoiesis and define progenitor cell states of immune system development. Perturbation of the myeloid lineage is indicated by pleiotropic associations with defined master regulators and cell alterations. Eosinophil count is inversely associated with cancer risk. A high frequency of pleiotropic associations is also centered on the regulation of small noncoding Y-RNAs. Predicted pleiotropic Y-RNAs show specific regulatory marks and are overabundant in the normal tissue and blood, The study was partially funded by the patient foundations GINKGO Apac del Berguedà and Toca-te-les, the Instituto de Salud Carlos III (grant PI21/01306; and CIBERONC and CIBERES), co-funded by the European Regional Development Fund (ERDF), “A way to build Europe”, the Generalitat de Catalunya (SGR 2017-449, 2017-1282, and 2021-184; and PERIS PFI-Salut SLT017-20-000076, Suport SLT017-20-000072, MedPerCan, and URDCat), NIH grant CA282303 (R.L), and CERCA Program of the Generalitat de Catalunya to IDIBELL and IGTP. This study makes use of data generated by the GCAT-Genomes for Life, cohort study of the Genomes of Catalonia, Fundació IGTP. GCAT was funded by the “Acción de Dinamización” of the Instituto de Salud Carlos III, Ministry of Economic Affairs and Digital Transformation (MINECO), and the Ministry of Health of the Generalitat of Catalunya (ADE 10/00026) and has additional support of the VEIS project (001-P-001647), co-funded by European Regional Development Fund (ERDF), “A way to build Europe” and the Instituto de Salud Carlos III (grant PI18/01512)., Objectius de Desenvolupament Sostenible::3 - Salut i Benestar
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the size of immune sets in the k-PULL infection model

  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Marcote Ordax, Francisco Javier|||0000-0002-5194-8593
  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)., This paper addresses immune sets in graphs, which are subsets of nodes that remain unaffected during the spread of influence, failure, or infection. The specific propagation model examined is the $k$-PULL infection rule, also referred to as bootstrap percolation. Studying immune sets offers important insights into the structural vulnerabilities and defensive capabilities of networks. In particular, we establish upper bounds for the size of minimal $k$-immune sets in graphs with a given maximum degree. Additionally, we focus on the $k$-immune number of a graph, defined as the minimum number of vertices in a $k$-immune set, and we derive bounds for this parameter. Lastly, we investigate the $k$-immune number of the Cartesian product of two graphs., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under projects 2017SGR–1087 and 2021SGR–00595., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A new class of polynomials from the spectrum of a graph, and its application to bound the k-independence number

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called k-partially walk-regular if the number of closed walks of a given length l = k, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also k-partially walk-regular for any k. In this paper, we introduce a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k-independence number of a k-partially walk-regular graph. With some examples and infinite families of graphs whose bounds are tight, we also show that the odd graph O` with ` odd has no 1-perfect code. Moreover, we show that our bound coincide, in general, with the Delsarte’s linear programming bound and the Lovász theta number ¿, the best ones to our knowledge. In fact, as a byproduct, it is shown that the given bounds also apply for ¿ and T, the Shannon capacity of a graph. Moreover, apart from the possible interest that the minor polynomials can have, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Uniform forcing and immune sets in graphs and hypergraphs

  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Zero forcing is an iterative coloring process on a graph that has been widely used in such different areas as the modelling of propagation phenomena in networks and the study of minimum rank problems in matrices and graphs. This paper deals with zero forcing on hypergraphs. (Representing a network by a hypergraph allows us to account for its community structure and for more general interactions between different subsets of nodes.) We consider two natural generalizations to hypergraphs of zero forcing on graphs (one of them already known) and, for each one of these generalizations we look into two clutters that play a significant role in the forcing process: the clutter of minimal forcing sets and the one of minimal immune sets. A formulation of immune sets in terms of neighbourhoods (hence without making reference to the iterative zero forcing process) is presented, highlighting the different behaviour of the distinct forcing rules. Moreover, we obtain the families of minimal forcing and minimal immune sets in the case of complete hypergraphs and we provide a full characterization of forcing and immune uniform clutters, both in the graph and in the hypergraph case., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Immune sets in monotone infection rules: characterization and complexity, Conjunts immunes en regles d'infecció monòtones: caracterització i complexitat, Conjuntos inmunes en reglas de infección monótonas: caracterización y complejidad

  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule , and to the combinatorial transversal relation between the families of inclusion-minimal -forcing and -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part ( -PUSH, -PUSH, -PUSH, -PULL, -PULL, and -wPULL), we prove the -Completeness of the decision problem associated to the corresponding -immune number of the graph., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing

  • Fàbrega Canudas, José|||0000-0002-4922-8562
  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
This is the peer reviewed version of the following article: Fàbrega, J.; Martí, J.; Muñoz, X. Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing. "Networks", 29 Juliol 2023, which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.22177. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited., In this article, we present a detailed study of the reach distance-layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance-layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance-layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR-1087., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New results for the Mondrian art problem

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
The Mondrian problem consists of dissecting a square of side length n ∈ N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n ∈ N. We provide a sequence of square partitions such that d(n)/n2 tends to zero for n large enough. For the case of 'perfect' partitions, that is, with d(n) = 0, we show that, for any fixed powers s1, . . . , sm, a square with side length n = p s1 1 · · · p smm , can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n ≤ x) of squares not having a perfect partition, we prove that its 'density' n(x) x is asymptotic to (log(log(x))2 2 log x , which improves previous results., The research of C. Dalfó and N. López has been partially supported by grant MTM2017-86767-R (Spanish Ministerio de Ciencia e Innovación). The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by Spanish Ministerio de Ciencia e Innovación from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
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ó Simó, 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' M C K ( d , l ) , and it is derived from the Kautz digraphs K ( d , l ) and from the so-called cyclic Kautz digraphs C K ( d , l ) . The cyclic Kautz digraphs C K ( d , l ) were defined as the digraphs whose vertices are labeled by all possible sequences a 1 … a l of length l , such that each character a i is chosen from an alphabet of d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a 1 ¿ a l . Their arcs are between vertices a 1 a 2 … a l and a 2 … a l a l + 1 , with a 1 ¿ a l and a 2 ¿ a l + 1 . Since C K ( d , l ) 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 M C K ( d , l ) are d -out-regular. Moreover, for t = 1 , we compute the number of vertices of the iterated line digraphs L t ( C K ( d , l ) ) ., The research of C. Dalfó has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under projects MTM2017-83271-R and PGC2018-095471-B-I00. 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 ., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Biological basis of extensive pleiotropy between blood traits and cancer risk

  • Pardo Cea, Miguel Angel
  • Farré Ramon, Xavier
  • Esteve, Anna
  • Palade, Joanna
  • Espín García, Roderic
  • Alsop, Eric
  • Alorda Carreras, Marc
  • Blay Magriñá, Natàlia
  • Baiges Carrasco, Alexandra
  • Comellas Padró, Francesc de Paula
  • de Cid, Rafael
  • Pujana, Miguel Angel
Background The immune system has a central role in preventing carcinogenesis. Alteration of systemic immune cell levels may increase cancer risk. However, the extent to which common genetic variation influences blood traits and cancer risk remains largely undetermined. Here, we identify pleiotropic variants and predict their underlying molecular and cellular alterations. Methods Multivariate Cox regression was used to evaluate associations between blood traits and cancer diagnosis in cases in the UK Biobank. Shared genetic variants were identified from the summary statistics of the genome-wide association studies of 27 blood traits and 27 cancer types and subtypes, applying the conditional/conjunctional falsediscovery rate approach. Analysis of genomic positions, expression quantitative trait loci, enhancers, regulatory marks, functionally defined gene sets, and bulk- and single-cell expression profiles predicted the biological impact of pleiotropic variants. Plasma small RNAs were sequenced to assess association with cancer diagnosis. Results The study identified 4093 common genetic variants, involving 1248 gene loci, that contributed to blood– cancer pleiotropism. Genomic hotspots of pleiotropism include chromosomal regions 5p15-TERT and 6p21-HLA. Genes whose products are involved in regulating telomere length are found to be enriched in pleiotropic variants. Pleiotropic gene candidates are frequently linked to transcriptional programs that regulate hematopoiesis and define progenitor cell states of immune system development. Perturbation of the myeloid lineage is indicated by pleiotropic associations with defined master regulators and cell alterations. Eosinophil count is inversely associated with cancer risk. A high frequency of pleiotropic associations is also centered on the regulation of small noncoding Y-RNAs. Predicted pleiotropic Y-RNAs show specific regulatory marks and are overabundant in the normal tissue and blood, The study was partially funded by the patient foundations GINKGO Apac del Berguedà and Toca-te-les, the Instituto de Salud Carlos III (grant PI21/01306; and CIBERONC and CIBERES), co-funded by the European Regional Development Fund (ERDF), “A way to build Europe”, the Generalitat de Catalunya (SGR 2017-449, 2017-1282, and 2021-184; and PERIS PFI-Salut SLT017-20-000076, Suport SLT017-20-000072, MedPerCan, and URDCat), NIH grant CA282303 (R.L), and CERCA Program of the Generalitat de Catalunya to IDIBELL and IGTP. This study makes use of data generated by the GCAT-Genomes for Life, cohort study of the Genomes of Catalonia, Fundació IGTP. GCAT was funded by the “Acción de Dinamización” of the Instituto de Salud Carlos III, Ministry of Economic Affairs and Digital Transformation (MINECO), and the Ministry of Health of the Generalitat of Catalunya (ADE 10/00026) and has additional support of the VEIS project (001-P-001647), co-funded by European Regional Development Fund (ERDF), “A way to build Europe” and the Instituto de Salud Carlos III (grant PI18/01512)., Objectius de Desenvolupament Sostenible::3 - Salut i Benestar, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the algebraic connectivity of some token graphs

  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
The k-token graph 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. It was proved that the algebraic connectivity of equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spec-tra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regularor not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. Research of the two first authors has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Discovering important nodes of complex networks based on laplacian spectra

  • Moradi Amani, Ali
  • Fiol Mora, Miquel Àngel
  • Jalili, Mahdi
  • Chen, Guanrong
  • Yu, Xinghuo
  • Stone, Lewi
© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Knowledge of the Laplacian eigenvalues of a network provides important insights into its structural features and dynamical behaviours. Node or link removal caused by possible outage events, such as mechanical and electrical failures or malicious attacks, significantly impacts the Laplacian spectra. This can also happen due to intentional node removal against which, increasing the algebraic connectivity is desired. In this article, an analytical metric is proposed to measure the effect of node removal on the Laplacian eigenvalues of the network. The metric is formulated based on the local multiplicity of each eigenvalue at each node, so that the effect of node removal on any particular eigenvalues can be approximated using only one single eigen-decomposition of the Laplacian matrix. The metric is applicable to undirected networks as well as strongly-connected directed ones. It also provides a reliable approximation for the “Laplacian energy” of a network. The performance of the metric is evaluated for several synthetic networks and also the American Western States power grid. Results show that this metric has a nearly perfect precision in correctly predicting the most central nodes, and significantly outperforms other comparable heuristic methods., This research was partly supported by the Erasmus+ KA107 grant. AMA, MJ, LS and XY were supported by the Australian Research Council through project No. DP170102303. MJ and XY are also supported by the Australian Research Council through project No. DP200101199. MAF was supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government with the European Regional Development Fund under project PGC2018-095471-B-I00, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Uniform forcing and immune sets in graphs and hypergraphs

  • Fàbrega Canudas, José
  • Martí Farré, Jaume
  • Muñoz López, Francisco Javier
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Zero forcing is an iterative coloring process on a graph that has been widely used in such different areas as the modelling of propagation phenomena in networks and the study of minimum rank problems in matrices and graphs. This paper deals with zero forcing on hypergraphs. (Representing a network by a hypergraph allows us to account for its community structure and for more general interactions between different subsets of nodes.) We consider two natural generalizations to hypergraphs of zero forcing on graphs (one of them already known) and, for each one of these generalizations we look into two clutters that play a significant role in the forcing process: the clutter of minimal forcing sets and the one of minimal immune sets. A formulation of immune sets in terms of neighbourhoods (hence without making reference to the iterative zero forcing process) is presented, highlighting the different behaviour of the distinct forcing rules. Moreover, we obtain the families of minimal forcing and minimal immune sets in the case of complete hypergraphs and we provide a full characterization of forcing and immune uniform clutters, both in the graph and in the hypergraph case., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. Although most of the models are based on stochastic methods, some deterministic constructions have been recently proposed, because this allows a better computation of their properties. Here a new deterministic family of hierarchical networks is presented, which generalizes most of the previous proposals, such as the so-called binomial tree. The obtained graphs can be seen as graphs on alphabets (where vertices are labeled with words of a given alphabet, and the edges are defined by a specific rule relating different words). This allows us the characterization of their main distance-related parameters, such as the radius and diameter. Moreover, as a by-product, an efficient shortest-path local algorithm is proposed., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Equivalent characterizations of the spectra of graphs and applications to measures of distance-regularity

  • Fiol Mora, Miquel Àngel
  • Fàbrega Canudas, José
  • Diego Gutiérrez, Víctor
The spectrum of a graph usually provides a lot of information about its combinatorial structure. Moreover,from the spectrum, the so-called predistance polynomials can be defined, as a generalization, for any graph, of the distancepolynomials of a distance-regular graph. Going further, the preintersection numbers generalize the intersection numbers ofa distance-regular graph. This paper describes, for any graph, the closed relationships between its spectrum, predistancepolynomials, and preintersection numbers. Then, some applications to derive combinatorial properties of the given graph,most of them related to some fundamental characterizations of distance-regularity, are presented. In particular, the so-called‘spectral excess theorem’ is revisited. This result states that a connected regular graph is distance-regular if and only if itsspectral excess, which is a value computed from the spectrum, equals the average excess, that is, the mean of the numbers ofvertices at maximum distance from every vertex., Peer Reviewed, Postprint (author's final draft)
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)

A note on a new general family of deterministic hierarchical networks

Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó Simó, Cristina
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel
  • Huemer, Clemens
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4, We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph 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. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that , the Laplacian spectrum of is contained in the Laplacian spectrum of . We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph and the star , respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement . This generalizes to tokens graphs a well-known property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of . Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Award-winning, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs and to a recent known family of mixed graphs (having edges with and without direction). As a byproduct, the existence of perfect codes in allows us to give a lower bound for the multiplicity of its eigenvalue -1., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
  • Pavlíková, Sona
  • Siran, Josef
This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-021-01049-3, We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The authors S. Pavl´ıkov´a and J. Sir´aˇn acknowledge support from the ˇ APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Immune sets in monotone infection rules: characterization and complexity, Conjunts immunes en regles d'infecció monòtones: caracterització i complexitat, Conjuntos inmunes en reglas de infección monótonas: caracterización y complejidad

  • Fàbrega Canudas, José
  • Martí Farré, Jaume
  • Muñoz López, Francisco Javier
© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule , and to the combinatorial transversal relation between the families of inclusion-minimal -forcing and -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part ( -PUSH, -PUSH, -PUSH, -PULL, -PULL, and -wPULL), we prove the -Completeness of the decision problem associated to the corresponding -immune number of the graph., Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the spectra and spectral radii of token graphs

  • Reyes, Mónica Andrea
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G), has as vertices the (n/k) k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of Fk(G) in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of Fk(G) is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed., The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-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)

On symmetric association schemes and associated quotient-polynomial graphs

  • Fiol Mora, Miquel Àngel
  • Penjic, Safet
Let denote an undirected, connected, regular graph with vertex set , adjacency matrix , and distinct eigenvalues. Let denote the subalgebra of generated by . We refer to as the adjacency algebra of . In this paper we investigate algebraic and combinatorial structure of for which the adjacency algebra is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) has a standard basis ; (ii) for every vertex there exists identical distance-faithful intersection diagram of with cells; (iii) the graph is quotient-polynomial; and (iv) if we pick then has distinct eigenvalues if and only if . We describe the combinatorial structure of quotient-polynomial graphs with diameter and distinct eigenvalues. As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether is distance-regular or not and, more generally, which distance- matrices are polynomial in , giving also these polynomials., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The second author acknowledges the financial support from the Slovenian Research Agency (research program P1-0285 and research project J1-1695)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Maria Camino Teófila
  • Dalfó Simó, Cristina
  • Martínez Barona, Berenice
© 2020 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Given an integer ` = 1, a (1, = `)-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhood within C. In this paper, we prove that every k-iterated line digraph of minimum in-degree at least 2 and k = 2, or minimum indegree at least 3 and k = 1, admits a (1, = `)-identifying code with ` = 2, and in any case it does not admit a (1, = `)-identifying code for ` = 3. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087. The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. B. Martínez-Barona has received funding from the scholarship 254379/438356 from CONACYT from Mexico. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (D ) , is the minimum size of all the identifying codes of D . We establish for digraphs without digons with both vertices of in-degree one that −→ γID (LD ) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show that −→ γID (LD ) attains the equality for a digraph having a 1- factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bipartite biregular Moore graphs

  • Araujo Pardo, Martha Gabriela
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
A bipartite graph G=(V,E) with V=V1 U V2 is biregular if all the vertices of a stable set Vi have the same degree ri for i=1,2. In this paper, we give an improved new Moore bound for an infinite family of such graphs with odd diameter. This problem was introduced in 1983 by Yebra, Fiol, and Fàbrega. Besides, we propose some constructions of bipartite biregular graphs with diameter d and large number of vertices N(r1,r2;d), together with their spectra. In some cases of diameters d=3, 4, and 5, the new graphs attaining the Moore bound are unique up to isomorphism., The research of the first author is supported by CONACyT-México under Project 282280 and PAPIIT-México under Project IN101821, PASPA-DGAPA, and CONACYT Sabbatical Year 2020. The research of the second and third authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the second and fourth authors is supported by MICINN from the Spanish Government under project MTM2017-83271-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the spectra and spectral radii of token graphs

  • Reyes Quiróz, Mónica Andrea
  • Dalfó Simó, Cristina
  • Fiol Mora, Miquel Àngel
The version of record of this article, first published inBoletín de la Sociedad Matemática Mexicana, is available online at Publisher’s website: http://dx.doi.org/10.1007/s40590-023-00583-3, Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by , has as vertices the k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, is the Johnson graph J(n, k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius (or maximum eigenvalue) of is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous’ spectral gap conjecture (which is now a theorem) is proposed., The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under Project 2017SGR1087 and by MICINN from the Spanish Government under Project PGC2018-095471-B-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., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the size of immune sets in the k-PULL infection model

  • Fàbrega Canudas, José
  • Marcote Ordax, Francisco Javier
  • Muñoz López, Francisco Javier
© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)., This paper addresses immune sets in graphs, which are subsets of nodes that remain unaffected during the spread of influence, failure, or infection. The specific propagation model examined is the $k$-PULL infection rule, also referred to as bootstrap percolation. Studying immune sets offers important insights into the structural vulnerabilities and defensive capabilities of networks. In particular, we establish upper bounds for the size of minimal $k$-immune sets in graphs with a given maximum degree. Additionally, we focus on the $k$-immune number of a graph, defined as the minimum number of vertices in a $k$-immune set, and we derive bounds for this parameter. Lastly, we investigate the $k$-immune number of the Cartesian product of two graphs., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under projects 2017SGR–1087 and 2021SGR–00595., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Approximation and decomposition in lattices of clutters

  • Martí Farré, Jaume
  • Mier Vinué, Anna de
A clutter on O is a family of subsets of O that are incomparable under inclusion. Given a collection S of clutters on O and another clutter ¿ on O, we study the problem of approximating and decomposing ¿ in terms of the clutters in S. We want to guarantee when these approximations exist not only for a single element ¿, but for all ¿ that belong to a family of clutters . We use the lattice structure of the collection of clutters to show that the existence of such approximations and decompositions for every clutter ¿ is equivalent to the fact that S contains a given family of irreducible elements determined by S and . We explicitly compute these irreducible families in some cases and apply our results to clutters arising from discrete objects such as matroids, graphs and secret sharing schemes., This work was partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under projects PGC2018-095471-B-I00 and PID2020-113082GB-I00; by AGAUR, Generalitat de Catalunya, from the Catalan Government under projects SGR-Cat 2021 00595 and SGR-Cat 2021 00585; by Universitat Politècnica de Catalunya under funds AGRUPUPC., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing

  • Fàbrega Canudas, José
  • Martí Farré, Jaume
  • Muñoz López, Francisco Javier
This is the peer reviewed version of the following article: Fàbrega, J.; Martí, J.; Muñoz, X. Distance-layer structure of the De Bruijn and Kautz digraphs: analysis and application to deflection routing. "Networks", 29 Juliol 2023, which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/net.22177. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited., In this article, we present a detailed study of the reach distance-layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance-layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance-layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description., Partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under project PGC2018-095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR-1087., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

  • Abiad, Aida
  • Coutinho, Gabriel
  • Fiol Mora, Miquel Àngel
  • Nogueira, Bruno
  • Zeijlemaker, Shanne
© 2022 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, The k-thpower of a graph G=(V,E), G^k, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of G^k which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well., The research of A. Abiad is partially supported by the FWO grant 1285921N. A. Abiad and M.A. Fiol gratefully acknowledge the support from DIAMANT. This research of M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. B. Nogueira acknowledges grant PRPQ/ADRC from UFMG. The authors would also like to thank Anurag Bishnoi for noticing a tight family for our bound (19)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A new class of polynomials from the spectrum of a graph, and its application to bound the k-independence number

  • Fiol Mora, Miquel Àngel
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called k-partially walk-regular if the number of closed walks of a given length l = k, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also k-partially walk-regular for any k. In this paper, we introduce a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k-independence number of a k-partially walk-regular graph. With some examples and infinite families of graphs whose bounds are tight, we also show that the odd graph O` with ` odd has no 1-perfect code. Moreover, we show that our bound coincide, in general, with the Delsarte’s linear programming bound and the Lovász theta number ¿, the best ones to our knowledge. In fact, as a byproduct, it is shown that the given bounds also apply for ¿ and T, the Shannon capacity of a graph. Moreover, apart from the possible interest that the minor polynomials can have, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. 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. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C-local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922