Source author record

M. A. Fiol

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.SP Discrete Mathematics math.AP math.GR Social and Information Networks

Catalog footprint

Research overview

40works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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

Almost Moore mixed graphs\/} appear in the context of the degree/diameter problem as a class of extremal mixed graphs, in the sense that their order is one unit less than the Moore bound for such graphs. The problem of their existence has been considered just for diameter $2$ . In this paper, we give a complete characterization of these extremal mixed graphs for diameters 2 and 3. We also derive some optimal constructions for other diameters.

preprint2022arXiv

On the algebraic connectivity of token graphs

We study the algebraic connectivity (or second Laplacian eigenvalue) of token graphs, also called symmetric powers of graphs. The $k$ -token graph $F_k(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$ . Recently, it was conjectured that the algebraic connectivity of $F_k(G)$ equals the algebraic connectivity of $G$ . In this paper, we prove the conjecture for new infinite families of graphs, such as trees and graphs with maximum degree large enough.

preprint2020arXiv

An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs

We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can attain. We first show these bounds can be improved if we know more details about the order of some elements of the generating set. Based on these improvements, we present some new families of mixed graphs. For every fixed value of the degree, these families have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal.

preprint2020arXiv

Decompositions of a rectangle into non-congruent rectangles of equal area

In this paper, we deal with a simple geometric problem: Is it possible to partition a rectangle into $k$ non-congruent rectangles of equal area? This problem is motivated by the so-called `Mondrian art problem' that asks a similar question for dissections with rectangles of integer sides. Here, we generalize the Mondrian problem by allowing rectangles of real sides. In this case, we show that the minimum value of $k$ for a rectangle to have a `perfect Mondrian partition' (that is, with non-congruent equal-area rectangles) is seven. Moreover, we prove that such a partition is unique (up to symmetries) and that there exist exactly two proper perfect Mondrian partitions for $k=8$ . Finally, we also prove that any square has a perfect Mondrian decomposition for $k\ge 7$ .

preprint2020arXiv

New results for the Mondrian art problem

The Mondrian problem consists of dissecting a square of side length $n\in \NN$ 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 \in \NN$. We provide a sequence of square partitions such that $d(n)/n^2$ 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 $s_1,\ldots, s_m$ , a square with side length $n=p_1^{s_1}\cdots p_m^{s_m}$ , can have a perfect Mondrian partition only if $p_1$ satisfies a given lower bound. Moreover, if $n(x)$ is the number of side lengths $x$ (with $n\le x$ ) of squares not having a perfect partition, we prove that its `density' $\frac{n(x)}{x}$ is asymptotic to $\frac{(\log(\log(x))^2}{2\log x}$ , which improves previous results.

preprint2020arXiv

New results on the degree/diameter problem of mixed Abelian Cayley graphs

Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case in which such graphs are Cayley graphs of Abelian groups. These groups can be constructed by using a generalization to $\mathbb{Z}^n$ of the concept of congruence in $\mathbb{Z}$ . Here we use this approach to present some families of mixed graphs, which, for every fixed value of the degree, have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal.

preprint2020arXiv

On symmetric association schemes and associated quotient-polynomial graphs

Let $Γ$ denote an undirected, connected, regular graph with vertex set $X$ , adjacency matrix $A$ , and ${d+1}$ distinct eigenvalues. Let ${\mathcal A}={\mathcal A}(Γ)$ denote the subalgebra of Mat $_X({\mathbb C})$ generated by $A$ . We refer to ${\mathcal A}$ as the {\it adjacency algebra} of $Γ$ . In this paper we investigate algebraic and combinatorial structure of $Γ$ for which the adjacency algebra ${\mathcal A}$ is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) ${\mathcal A}$ has a standard basis $\{I,F_1,\ldots,F_d\}$ ; (ii) for every vertex there exists identical distance-faithful intersection diagram of $Γ$ with $d+1$ cells; (iii) the graph $Γ$ is quotient-polynomial; and (iv) if we pick $F\in \{I,F_1,\ldots,F_d\}$ then $F$ has $d+1$ distinct eigenvalues if and only if span $\{I,F_1,\ldots,F_d\}=$ span $\{I,F,\ldots,F^d\}$ . We describe the combinatorial structure of quotient-polynomial graphs with diameter $2$ and $4$ distinct eigenvalues. As a consequence of the technique from the paper we give an algorithm which computes the number of distinct eigenvalues of any Hermitian matrix using only elementary operations. When such a matrix is the adjacency matrix of a graph $Γ$ , a simple variation of the algorithm allow us to decide wheter $Γ$ is distance-regular or not. In this context, we also propose an algorithm to find which distance- $i$ matrices are polynomial in $A$ , giving also these polynomials.

preprint2016arXiv

A new general family of deterministic hierarchical networks

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 the diameter. Moreover, as a by product, an efficient shortest-path local algorithm is proposed.

preprint2016arXiv

A note on the order of iterated line digraphs

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

preprint2016arXiv

Cospectral digraphs from locally line digraphs

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

preprint2016arXiv

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

As it is well known, the spectrum ${\rm sp\,} Γ$ (of the adjacency matrix $A$ ) of a graph $Γ$ , with $d$ distinct eigenvalues other than its spectral radius $λ_0$ , usually provides a lot of information about the structure of $G$ . Moreover, from ${\rm sp\,}Γ$ we can define the so-called predistance polynomials $p_0,\ldots,p_d\in {\mathbb R}_d[x]$ , with ${\rm dgr\,} p_i=i$ , $i=0,\ldots,d$ , which are orthogonal with respect to the scalar product $\langle f, g\rangle_Γ =\frac{1}{n}{\rm tr\,}(f(A)g(A))$ and normalized in such a way that $\|p_i\|_Γ^2=p_i(λ_0)$ . They can be seen as a generalization for any graph of the distance polynomials of a distance-regular graph. Going further, we consider the preintersection numbers $ξ_{ij}^h$ for $i,j,h\in\{0,\ldots,d\}$ , which generalize the intersection numbers of a distance-regular graph, and they are the Fourier coefficients of $p_ip_j$ in terms of the basis $\{p_h\}_{0\le h\le d}$ . The aim of this paper is to show that, for any graph $Γ$ , the information contained in its spectrum, predistance polynomials, and preintersection numbers is equivalent. Also, we give some characterizations of distance-regularity which are based on the above concepts. For instance, we comment upon the so-called spectral excess theorem stating that a connected regular graph $G$ is distance-regular if and only if its spectral excess, which is the value of $p_d$ at $λ_0$ , equals the average excess, that is, the mean of the numbers of vertices at extremal distance $d$ from every vertex.

preprint2016arXiv

From expanded digraphs to lifts of voltage digraphs and line digraphs

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

preprint2016arXiv

On bipartite mixed graphs

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

preprint2016arXiv

On middle cube graphs

We study a family of graphs related to the $n$ -cube. The middle cube graph of parameter $k$ is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors).

preprint2016arXiv

Sequence mixed graphs

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

preprint2016arXiv

Some Spectral and Quasi-Spectral Characterizations of Distance-Regular Graphs

In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth.

preprint2015arXiv

Abelian Cayley digraphs with asymptotically large order for any given degree

Abelian Cayley digraphs can be constructed by using a generalization to $Z^n$ of the concept of congruence in $Z$ . Here we use this approach to present a family of such digraphs, which, for every fixed value of the degree, have asymptotically large number of vertices as the diameter increases. Up to now, the best known asymptotically dense results were all non-constructive.

preprint2015arXiv

Deterministic hierarchical networks

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

preprint2015arXiv

Distance mean-regular graphs

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $Γ$ be a graph with vertex set $V$ , diameter $D$ , adjacency matrix $A$ , and adjacency algebra ${\cal A}$ . Then, $Γ$ is $distance$ $mean$ - $regular$ when, for a given $u\in V$ , the averages of the intersection numbers $p_{ij}^h(u,v)=|Γ_i(u)\cap Γ_j(v)|$ (number of vertices at distance $i$ from $u$ and distance $j$ from $v$ ) computed over all vertices $v$ at a given distance $h\in \{0,1,\ldots,D\}$ from $u$ , do not depend on $u$ . In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $Γ$ and, hence, they generate a subalgebra of ${\cal A}$ . Some other algebras associated to distance mean-regular graphs are also characterized.

preprint2015arXiv

Quotient-polynomial graphs

As a generalization of orbit-polynomial and distance-regular graphs, we introduce the concept of a quotient-polynomial graph. In these graphs every vertex $u$ induces the same regular partition around $u$ , where all vertices of each cell are equidistant from $u$ . Some properties and characterizations of such graphs are studied. For instance, all quotient-polynomial graphs are walk-regular and distance-polynomial. Also, we show that every quotient-polynomial graph generates a (symmetric) association scheme.

preprint2014arXiv

A spectral characterization of strongly distance-regular graphs with diameter four

A graph $G$ with $d+1$ distinct eigenvalues is called strongly distance-regular if $G$ itself is distance-regular, and its distance- $d$ graph $G_d$ is strongly-regular. In this note we provide a spectral characterization of those distance-regular graphs with diameter $d=4$ which are strongly distance-regular. As a byproduct, it is shown that all bipartite strongly distance-regular graphs with such a diameter are antipodal.

preprint2014arXiv

Comments on "Extremal Cayley digraphs of finite Abelian groups" [Intercon. Networks 12 (2011), no. 1-2, 125--135]

We comment on the paper "Extremal Cayley digraphs of finite Abelian groups" [Intercon. Networks 12 (2011), no. 1-2, 125--135]. In particular, we give some counterexamples to the results presented there, and provide a correct result for degree two.

preprint2014arXiv

Distance-regular graphs where the distance- $d$ graph has fewer distinct eigenvalues

Let the Kneser graph $K$ of a distance-regular graph $Γ$ be the graph on the same vertex set as $Γ$ , where two vertices are adjacent when they have maximal distance in $Γ$ . We study the situation where the Bose-Mesner algebra of $Γ$ is not generated by the adjacency matrix of $K$ . In particular, we obtain strong results in the so-called `half antipodal' case.

preprint2014arXiv

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

Let $Γ$ be a distance-regular graph with diameter $d$ and Kneser graph $K=Γ_d$ , the distance- $d$ graph of $Γ$ . We say that $Γ$ is partially antipodal when $K$ has fewer distinct eigenvalues than $Γ$ . In particular, this is the case of antipodal distance-regular graphs ( $K$ with only two distinct eigenvalues), and the so-called half-antipodal distance-regular graphs ( $K$ with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with $d$ distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance $d$ from every vertex. This can be seen as a general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.

preprint2013arXiv

Algebraic characterizations of regularity properties in bipartite graphs

Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph G is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented.

preprint2013arXiv

An Interlacing Approach for Bounding the Sum of Laplacian Eigenvalues of Graphs

We apply eigenvalue interlacing techniques for obtaining lower and upper bounds for the sums of Laplacian eigenvalues of graphs, and characterize equality. This leads to generalizations of, and variations on theorems by Grone, and Grone and Merris. As a consequence we obtain inequalities involving bounds for some well-known parameters of a graph, such as edge-connectivity, and the isoperimetric number.

preprint2013arXiv

Some results on the structure of multipoles in the study of snarks

Multipoles are the pieces we obtain by cutting some edges of a cubic graph. As a result of the cut, a multipole $M$ has dangling edges with one free end, which we call semiedges. Then, every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which satisfies the Parity Lemma. Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable. Some results on the states and structure of the so-called color complete and color closed multipoles are presented. In particular, we give lower and upper linear bounds on the minimum order of a color complete multipole, and compute its exact number of states. Given two multipoles $M_1$ and $M_2$ with the same number of semiedges, we say that $M_1$ is reducible to $M_2$ if the state set of $M_2$ is a non-empty subset of the state set of $M_1$ and $M_2$ has less vertices than $M_1$ . The function $v(m)$ is defined as the maximum number of vertices of an irreducible multipole with $m$ semiedges. The exact values of $v(m)$ are only known for $m\le 5$ . We prove that tree and cycle multipoles are irreducible and, as a byproduct, that $v(m)$ has a linear lower bound.

preprint2013arXiv

The spectral excess theorem for distance-biregular graphs

The spectral excess theorem for distance-regular graphs states that a regular (connected) graph is distance-regular if and only if its spectral-excess equals its average excess. A bipartite graph is distance-biregular when it is distance-regular around each vertex and the intersection array only depends on the stable set such a vertex belongs to. In this note we derive a new version of the spectral excess theorem for bipartite distance-biregular graphs.

preprint2012arXiv

A differential approach for bounding the index of graphs under perturbations

This paper presents bounds for the variation of the spectral radius $λ(G)$ of a graph $G$ after some perturbations or local vertex/edge modifications of $G$ . The perturbations considered here are the connection of a new vertex with, say, $g$ vertices of $G$ , the addition of a pendant edge (the previous case with $g=1$ ) and the addition of an edge. The method proposed here is based on continuous perturbations and the study of their differential inequalities associated. Within rather economical information (namely, the degrees of the vertices involved in the perturbation), the best possible inequalities are obtained. In addition, the cases when equalities are attained are characterized. The asymptotic behavior of the bounds obtained is also discussed. For instance, if $G$ is a connected graph and $G_u$ denotes the graph obtained from $G$ by adding a pendant edge at vertex $u$ with degree $δ_u$ , then, $λ(G_u)\le λ(G)+\frac{δ_u}{λ^3(G)}+\textrm{o}(\frac{1}{λ^3(G)}).$

preprint2012arXiv

A note on the voting problem

Let $v(n)$ be the minimum number of voters with transitive preferences which are needed to generate any strong preference pattern (ties not allowed) on $n$ candidates. Let $k=\lfloor \log_2 n\rfloor$ . We show that $v(n)\le n-k$ if $n$ and $k$ have different parity, and $v(n)\le n-k+1$ otherwise.

preprint2012arXiv

A simple and fast heuristic algorithm for edge-coloring of graphs

A simple but empirically efficient heuristic algorithm for the edge-coloring of graphs is presented. Its basic idea is the displacement of "conflicts" (repeated colors in the edges incident to a vertex) along paths of adjacent vertices whose incident edges are recolored by swapping alternating colors (that is, doing a Kempe interchange). The results of performance tests on random cubic and $Δ$ -regular graphs are presented, and a full implementation of the algorithm is given to facilitate its use and the reproducibility of results.

preprint2012arXiv

Edge-distance-regular graphs are distance-regular

A graph is edge-distance-regular when it is distance-regular around each of its edges and it has the same intersection numbers for any edge taken as a root. In this paper we give some (combinatorial and algebraic) proofs of the fact that every edge-distance-regular graph $\G$ is distance-regular and homogeneous. More precisely, $\G$ is edge-distance-regular if and only if it is bipartite distance-regular or a generalized odd graph. Also, we obtain the relationships between some of their corresponding parameters, mainly, the distance polynomials and the intersection numbers.

preprint2012arXiv

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some "weights" (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights "regularize" the graph, and hence allow us to define a kind of regular partition, called "pseudo-regular," intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity $Θ^*$ of a connected graph $\G$, with $n$ vertices and (adjacency matrix) eigenvalues $λ_1>λ_2\ge\...\ge λ_n$ , satisfies $$ Θ\le Θ^* \le \frac{\|\vecnu\|^2}{1-\frac{λ_1}{λ_n}} $$ where $Θ$ is the (standard) Shannon capacity and $\vecnu$ is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived. spectrum are derived.

preprint2012arXiv

Moments in graphs

Let $G$ be a connected graph with vertex set $V$ and a {\em weight function} $ρ$ that assigns a nonnegative number to each of its vertices. Then, the {\em $ρ$ -moment} of $G$ at vertex $u$ is defined to be $M_G^ρ(u)=\sum_{v\in V} ρ(v)\dist (u,v) $, where $\dist(\cdot,\cdot)$ stands for the distance function. Adding up all these numbers, we obtain the {\em $ρ$ -moment of $G$ }: $$ M_G^ρ=\sum_{u\in V}M_G^ρ(u)=1/2\sum_{u,v\in V}\dist(u,v)[ρ(u)+ρ(v)]. $$ This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the {\em Wiener index} $W(G)$ , when $ρ(u)=1/2$ for every $u\in V$ , and the {\em degree distance} $D'(G)$ , obtained when $ρ(u)=δ(u)$ , the degree of vertex $u$ . In this paper we derive some exact formulas for computing the $ρ$ -moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding $ρ$ -moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same $ρ$ -moment for every $ρ$ (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.

preprint2012arXiv

Number of walks and degree powers in a graph

This note deals with the relationship between the total number of $k$ -walks in a graph, and the sum of the $k$ -th powers of its vertex degrees. In particular, it is shown that the the number of all $k$ -walks is upper bounded by the sum of the $k$ -th powers of the degrees.

preprint2012arXiv

On congruence in Z^n and the dimension of a multidimensional circulant

From a generalization to $Z^n$ of the concept of congruence we define a family of regular digraphs or graphs called multidimensional circulants, which turn out to be Cayley (di)graphs of Abelian groups. This paper is mainly devoted to show the relationship between the Smith normal form for integral matrices and the dimensions of such (di)graphs, that is the minimum ranks of the groups they can arise from. In particular, those 2-step multidimensional circulants which are circulants, that is Cayley (di)graphs of cyclic groups, are fully characterized. In addition, a reasoning due to Lawrence is used to prove that the cartesian product of $n$ circulants with equal number of vertices $p>2$ , $p$ a prime, has dimension $n$ .

preprint2012arXiv

On some approaches to the spectral excess theorem for nonregular graphs

The Spectral Excess Theorem (SPET) for distance-regular graphs states that a regular (connected) graph is distance-regular if and only if its spectral-excess equals its average excess. Recently, some local or global approaches to the SPET have been used to obtain new versions of the theorem for nonregular graphs, and also to study the problem of characterizing the graphs which have the corresponding distance-regularity property. In this paper, some of these versions are related and compared, and some of their results are improved. As a result, a sufficient condition for a graph to be distance-polynomial is obtained.

preprint2012arXiv

On the local spectra of the subconstituents of a vertex set and completely pseudo-regular codes

The local spectrum of a vertex set in a graph has been proven to be very useful to study some of its metric properties. It also has applications in the area of pseudo-distance-regularity around a set and can be used to obtain quasi-spectral characterizations of completely (pseudo-)regular codes. In this paper we study the relation between the local spectrum of a vertex set and the local spectrum of each of its subconstituents. Moreover, we obtain a new characterization for completely pseudo-regular codes, and consequently for completely regular codes, in terms of the relation between the local spectrum of an extremal set of vertices and the local spectrum of its antipodal set. We also present a new proof of the version of the Spectral Excess Theorem for extremal sets of vertices.

preprint2012arXiv

Pseudo-distance-regularised graphs are distance-regular or distance-biregular

The concept of pseudo-distance-regularity around a vertex of a graph is a natural generalization, for non-regular graphs, of the standard distance-regularity around a vertex. In this note, we prove that a pseudo-distance-regular graph around each of its vertices is either distance-regular or distance-biregular. By using a combinatorial approach, the same conclusion was reached by Godsil and Shawe-Taylor for a distance-regular graph around each of its vertices. Thus, our proof, which is of an algebraic nature, can also be seen as an alternative demonstration of Godsil and Shawe-Taylor's theorem.

preprint2012arXiv

The (Δ,D) and (Δ,N) problems for New Amsterdam and Manhattan digraphs

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

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

M. A. Fiol

Research overview

Is this your work?

40 publications

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

On the algebraic connectivity of token graphs

An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs

Decompositions of a rectangle into non-congruent rectangles of equal area

New results for the Mondrian art problem

New results on the degree/diameter problem of mixed Abelian Cayley graphs

On symmetric association schemes and associated quotient-polynomial graphs

A new general family of deterministic hierarchical networks

A note on the order of iterated line digraphs

Cospectral digraphs from locally line digraphs

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

From expanded digraphs to lifts of voltage digraphs and line digraphs

On bipartite mixed graphs

On middle cube graphs

Sequence mixed graphs

Some Spectral and Quasi-Spectral Characterizations of Distance-Regular Graphs

Abelian Cayley digraphs with asymptotically large order for any given degree

Deterministic hierarchical networks

Distance mean-regular graphs

Quotient-polynomial graphs

A spectral characterization of strongly distance-regular graphs with diameter four

Comments on "Extremal Cayley digraphs of finite Abelian groups" [Intercon. Networks 12 (2011), no. 1-2, 125--135]

Distance-regular graphs where the distance-ddd graph has fewer distinct eigenvalues

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

Algebraic characterizations of regularity properties in bipartite graphs

An Interlacing Approach for Bounding the Sum of Laplacian Eigenvalues of Graphs

Some results on the structure of multipoles in the study of snarks

The spectral excess theorem for distance-biregular graphs

A differential approach for bounding the index of graphs under perturbations

A note on the voting problem

A simple and fast heuristic algorithm for edge-coloring of graphs

Edge-distance-regular graphs are distance-regular

Eigenvalue interlacing and weight parameters of graphs

Moments in graphs

Number of walks and degree powers in a graph

On congruence in Z^n and the dimension of a multidimensional circulant

On some approaches to the spectral excess theorem for nonregular graphs

On the local spectra of the subconstituents of a vertex set and completely pseudo-regular codes

Pseudo-distance-regularised graphs are distance-regular or distance-biregular

The (Δ,D) and (Δ,N) problems for New Amsterdam and Manhattan digraphs

See the researcher in context

Building this map preview

Distance-regular graphs where the distance- $d$ graph has fewer distinct eigenvalues

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