Search

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.

An antimagic labeling a connected graph $G$ is a bijection from the set of edges $E(G)$ to $\{1,2,\dots,|E(G)|\}$ such that all vertex sums are pairwise distinct, where the vertex sum at vertex $v$ is the sum of the labels assigned to edges incident to $v$. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than $K_2$ is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9--14]., Comment: 7 pages, 4 figures

A well-known conjecture by Lovasz and Plummer from the 1970s asserting that a bridgeless cubic graph has exponentially many perfect matchings was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture for the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically \(c\gamma ^n\), where \(c>0\) and \(\gamma \sim 1.14196\) is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations. (Supported by the Ministerio de Economia y Competitividad grant MTM2017-82166-P, and by the Special Research Program F50 Algorithmic and Enumerative Combinatorics of the Austrian Science Fund.).

"This is the peer reviewed version of the following article: Larrauri, L.; Müller, T.; Noy, M. Limiting probabilities of first order properties of random sparse graphs and hypergraphs. "Random structures and algorithms", 18 Agost 2021, vol. 60, núm. 3, p. 506-526., which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/rsa.21041. 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." Let Gn be the binomial random graph G(n, p = c/n) in the sparse regime, which as is well-known undergoes a phase transition at c = 1. Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence f, the limiting probability that Gn satisfies f as n ¿ 8 exists, and moreover it is an analytic function of c. In this paper we consider the closure Lc in [0, 1] of the set Lc of all limiting probabilities of first order sentences in Gn. We show that there exists a critical value c0 ˜ 0.93 such that Lc = [0, 1] when c = c0, whereas Lc misses at least one subinterval when c < c0. We extend these results to random d-uniform sparse hypergraphs, where the probability of a hyperedge is given by p = c/nd-1 .

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem. First author partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936.

For a given graph G = (V, E), the degree mean rate of an edge uv ∈ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randić index of G in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randić index for graphs with order n large enough, when the minimum degree δ is greater than (approximately) ∆1/3 , where ∆ is the maximum degree. As a by-product, this proves that almost all random (Erdös-Rényi) graphs satisfy the conjecture. This research is partially supported by the project 017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. 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.

This is a survey on some known properties of the possible Moore graph (or graphs) ϒ with degree 57 and diameter 2. Moreover, we give some new results about it, such as the following. When we consider the distance partition of ϒ induced by a vertex subset C, the following graphs are distance-regular: The induced graph of the vertices at distance 1 from C when C is a set of 400 independent vertices; the induced graphs of the vertices at distance 2 from C when C is a vertex or an edge, and the line graph of ϒ. Besides, ϒ is an edge-distance-regular graph. This research is partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. 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.

Let S be a set of vertices of a graph G. Let M[S] be the set of vertices built from the closed neighborhood N[S] of S, by iteratively applying the following propagation rule: if a vertex and all but exactly one of its neighbors are in M[S], then the remaining neighbor is also in M[S]. A set S is called a power dominating set of G if M[S]=V(G). The power domination number ¿P(G) of G is the minimum cardinality of a power dominating set. In this paper, we present some necessary conditions for two graphs G and H to satisfy 1=¿P(G*H)=2 for product graphs.

This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms. 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 work, 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=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . 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 a well-known property for Laplacian eigenvalues of graphs to token graphs. 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 research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. 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 work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922.

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., Comment: 19 pages, 3 figures, 2 tables

A bipartite graph $G=(V,E)$ with $V=V_1\cup V_2$ is biregular if all the vertices of a stable set $V_i$ have the same degree $r_i$ 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\`abrega.\\ Besides, we propose some constructions of bipartite biregular graphs with diameter $d$ and large number of vertices $N(r_1,r_2;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., Comment: 19 pages, 2 figures

We consider the spread of an infectious disease on a heterogeneous metapopulation defined by any (correlated or uncorrelated) network. The infection evolves under transmission, recovery and migration mechanisms. We study some spectral properties of a connectivity matrix arising from the continuous-time equations of the model. In particular we show that the classical sufficient condition of instability for the disease-free equilibrium, well known for the particular case of uncorrelated networks, works also for the general case. We give also an alternative condition that yields a more accurate estimation of the epidemic threshold for correlated (either assortative or dissortative) networks Supported by Ministry of Economy and Competitiveness of the Spanish Government grant numbers MTM2011-27739-C04-03 (first author) and DPI2011-25822 (second author). Also by Generalitat de Catalunya projects 2009-SGR-345 (first author) and 2009-SGR-1228 (second author).

A connected and undirected graph G of size n≥1 is said to be a sum basic equilibrium iff for every edge uv from G and any node v′ from G, when performing the swap of the edge uv for the edge uv′ the sum of the distances from u to all the other nodes is not strictly reduced. This concept comes from the so called Network Creation Games, a wide subject inside Algorithmic Game Theory that tries to better understand how Internet-like networks behave. It has been shown that the diameter of sum basic equilibria is 2O(logn√) in general and at most 2 for trees. In this paper we see that the upper bound of 2 not only holds for trees but for bipartite graphs, too. Specifically, we show that the only bipartite sum basic equilibrium networks are the complete bipartite graphs Kr,s with r,s≥1 . This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786.

Catalytic equations appear in several combinatorial applications, most notably in the numeration of lattice path and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size $n$ in various planar map classes grows asymptotically like $c\cdot n^{-5/2} \gamma^n$, for suitable positive constants $c$ and $\gamma$. Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is $n^{-3/2}$) and non-linear catalytic equations (where we have $n^{-5/2}$ as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive., Comment: 21 pages

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

The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k − 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and ℓ, with ℓ ∈ {2k − 2, 2k − 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs.

A classical result by Lov\'asz asserts that two graphs $G$ and $H$ are isomorphic if and only if they have the same left profile, that is, for every graph $F$, the number of homomorphisms from $F$ to $G$ coincides with the number of homomorphisms from $F$ to $H$. Dvor{\'{a}}k and later on Dell, Grohe, and Rattan showed that restrictions of the left profile to a class of graphs can capture several different relaxations of isomorphism, including equivalence in counting logics with a fixed number of variables (which contains fractional isomorphism as a special case) and co-spectrality (i.e., two graphs having the same characteristic polynomial). On the other side, a result by Chaudhuri and Vardi asserts that isomorphism is also captured by the right profile, that is, two graphs $G$ and $H$ are isomorphic if and only if for every graph $F$, the number of homomorphisms from $G$ to $F$ coincides with the number of homomorphisms from $H$ to $F$. In this paper, we embark on a study of the restrictions of the right profile by investigating relaxations of isomorphism that can or cannot be captured by restricting the right profile to a fixed class of graphs. Our results unveil striking differences between the expressive power of the left profile and the right profile. We show that fractional isomorphism, equivalence in counting logics with a fixed number of variables, and co-spectrality cannot be captured by restricting the right profile to a class of graphs. In the opposite direction, we show that chromatic equivalence cannot be captured by restricting the left profile to a class of graphs, while, clearly, it can be captured by restricting the right profile to the class of all cliques., Comment: 27 pages, 2 figures

We prove that for k ≪ 4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs. The first, second, and fourth authors were supported by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme/ERC grant agreement no. 648276 AUTAR. The third and fifth authors were supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ ERC grant agreement no. 279611 as well as by Swedish Research Council grants 621-2012-5645 and 2016-00782, and the second author did part of this work while at KTH Royal Institute of Technology supported by the same grants. The last author was supported by the Russian Foundation for Basic Research.

© 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.

© 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 a visibility representation of a graph G, the vertices are represented by nonoverlapping geometric objects, while the edges are represented as segments that only intersect the geometric objects associated with their end-vertices. Given a set P of n points, an Anchored Visibility Representation of a graph G with n vertices is a visibility representation such that for each vertex v of G, the geometric object representing v contains a point of P. We prove positive and negative results about the existence of anchored visibility representations under various models, both in 2D and in 3D space. We consider the case when the mapping between the vertices and the points is not given and the case when it is only partially given.

Electronic version of an article published as International journal of computational geometry and applications, 5 May 2020, vol. 29, núm. 4, p. 289-299. Article DOI 10.1142/S0218195919500109 © 2020 copyright World Scientific Publishing Company. Journal URL: https://www.worldscientific.com/doi/abs/10.1142/S0218195919500109 We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set S of points with each point either red or blue, does there exist a convex quadrangulation of S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922

We prove a tight upper bound on the independence polynomial (and total number of independent sets) of cubic graphs of girth at least 5. The bound is achieved by unions of the Heawood graph, the point/line incidence graph of the Fano plane. We also give a tight lower bound on the total number of independent sets of triangle-free cubic graphs. This bound is achieved by unions of the Petersen graph. We conjecture that in fact all Moore graphs are extremal for the scaled number of independent sets in regular graphs of a given minimum girth, maximizing this quantity if their girth is even and minimizing if odd. The Heawood and Petersen graphs are instances of this conjecture, along with complete graphs, complete bipartite graphs, and cycles., Calculations used in the proof are included with this arXiv submission as ancillary files

© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ A dominating set S of a graph is a metric-locating-dominating set if each vertex of the graph is uniquely distinguished by its distances from the elements of S , and the minimum cardinality of such a set is called the metric-location-domination number. In this paper, we undertake a study that, in general graphs and specific families, relates metric-locating-dominating sets to other special sets: resolving sets, dominating sets, locating-dominating sets and doubly resolving sets. We first characterize the extremal trees of the bounds that naturally involve metric-location-domination number, metric dimension and domination number. Then, we prove that there is no polynomial upper bound on the location-domination number in terms of the metric-location-domination number, thus extending a result of Henning and Oellermann. Finally, we show different methods to transform metric-locating-dominating sets into locating-dominating sets and doubly resolving sets. Our methods produce new bounds on the minimum cardinalities of all those sets, some of them concerning parameters that have not been related so far

We show that for all $d\in \{3,\ldots,n-1\}$ the size of the largest component of a random $d$-regular graph on $n$ vertices around the percolation threshold $p=1/(d-1)$ is $\Theta(n^{2/3})$, with high probability. This extends known results for fixed $d\geq 3$ and for $d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method., Comment: 10 pages

A mixed regular graph is a connected simple graph in which each vertex has both a fixed outdegree (the same indegree) and a fixed undirected degree. A mixed regular graphs is said to be optimal if there is not a mixed regular graph with the same parameters and bigger order. We present a construction that provides mixed graphs of undirected degree q , directed degree q − 1 2 and order 2 q 2 , for q being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to 9 q 2 − 4 q + 3 4 the defect of these mixed graphs is ( q − 2 2 ) 2 − 1 4 . In particular we obtain a known mixed Moore graph of order 18 , undirected degree 3 and directed degree 1 called Bosak’s graph and a new mixed graph of order 50 , undirected degree 5 and directed degree 2 , which is proved to be optimal.

Let $D(n,r)$ be a random $r$-out regular directed multigraph on the set of vertices $\{1,\ldots,n\}$. In this work, we establish that for every $r \ge 2$, there exists $\eta_r>0$ such that $\text{diam}(D(n,r))=(1+\eta_r+o(1))\log_r{n}$. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on $D(n,r)$. In particular, we determine the asymptotic behaviour of $\pi_{\max}$ and $\pi_{\min}$, the maximum and the minimum values of the stationary distribution. We show that with high probability $\pi_{\max} = n^{-1+o(1)}$ and $\pi_{\min}=n^{-(1+\eta_r)+o(1)}$. Our proof shows that the vertices with $\pi(v)$ near to $\pi_{\min}$ lie at the top of "narrow, slippery towers", such vertices are also responsible for increasing the diameter from $(1+o(1))\log_r n$ to $(1+\eta_r+o(1))\log_r{n}$., Comment: 31 pages

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. Received by the editors on February 20, 2020. Accepted for publication on May 27, 2020. Handling Editor: Sebastian M.Cioaba. Corresponding Author: Cristina Dalf ́o.†Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia (cristina.dalfo@udl.cat). Partiallysupported 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 2020research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922.‡Departament de Matem`atiques, Barcelona Graduate School of Mathematics, Universitat Polit`ecnica de Catalunya,Barcelona, Catalonia, (miguel.angel.fiol@upc.edu). Partially supported by AGAUR from the Catalan Government under project2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00.

We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922. This research is also supported by PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033. C. H. and R. I. S. were supported by MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1336 and 2017SGR1640. G. E. is also funded by an FPU of the Universidad de Alcalá.

Let $G$ be a graph of maximum degree $��$ and $k$ be an integer. The $k$-recolouring graph of $G$ is the graph whose vertices are $k$-colourings of $G$ and where two $k$-colourings are adjacent if they differ at exactly one vertex. It is well-known that the $k$-recolouring graph is connected for $k\geq ��+2$. Feghali, Johnson and Paulusma [Journal of Graph Theory, 83(4):340--358] showed that the $(��+1)$-recolouring graph is composed by a unique connected component of size at least $2$ and (possibly many) isolated vertices. In this paper, we study the proportion of isolated vertices (also called frozen colourings) in the $(��+1)$-recolouring graph. Our main contribution is to show that, if $G$ is connected, the proportion of frozen colourings of $G$ is exponentially smaller than the total number of colourings. This motivates the study of the Glauber dynamics on $(��+1)$-colourings. In contrast to the conjectured mixing time for $k\geq ��+2$ colours, we show that the mixing time of the Glauber dynamics for $(��+1)$-colourings can be of quadratic order. Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs., 16 pages

A $k$-coloring of a graph $G$ is a $k$-partition $\Pi=\{S_1,\ldots,S_k\}$ of $V(G)$ into independent sets, called \emph{colors}. A $k$-coloring is called \emph{neighbor-locating} if for every pair of vertices $u,v$ belonging to the same color $S_i$, the set of colors of the neighborhood of $u$ is different from the set of colors of the neighborhood of $v$. The neighbor-locating chromatic number $\chi _{_{NL}}(G)$ is the minimum cardinality of a neighbor-locating coloring of $G$. We establish some tight bounds for the neighbor-locating chromatic number of a graph, in terms of its order, maximum degree and independence number. We determine all connected graphs of order $n\geq 5$ with neighbor-locating chromatic number $n$ or $n-1$. We examine the neighbor-locating chromatic number for two graph operations: join and disjoint union, and also for two graph families: split graphs and Mycielski graphs., Comment: 20 pages, 4 figures

In recent years, researchers have realized the difficulties of fitting power-law distributions properly. These difficulties are higher in Zipfian systems, due to the discreteness of the variables and to the existence of two representations for these systems, i.e., two versions depending on the random variable to fit: rank or size. The discreteness implies that a power law in one of the representations is not a power law in the other, and vice versa. We generate synthetic power laws in both representations and apply a state-of-the-art fitting method to each of the two random variables. The method (based on maximum likelihood plus a goodness-of-fit test) does not fit the whole distribution but the tail, understood as the part of a distribution above a cutoff that separates non-power-law behavior from power-law behavior. We find that, no matter which random variable is power-law distributed, using the rank as the random variable is problematic for fitting, in general (although it may work in some limit cases). One of the difficulties comes from recovering the “hidden” true ranks from the empirical ranks. On the contrary, the representation in terms of the distribution of sizes allows one to recover the true exponent (with some small bias when the underlying size distribution is a power law only asymptotically). Support from projects FIS2012-31324, FIS2015-71851-P, TIN2017-89244-R, PGC-FIS2018-099629-B-I00, María de Maeztu Program MDM-2014-0445, from Spanish MINECO; 2014SGR-1307, 2017SGR-856 (MACDA) from AGAUR; and the Collaborative Mathematics Project from Fundación La Caixa (I.S.) is acknowledged.

In this paper we consider a subdivision of a given network and we show how the group inverse matrix of the normalized laplacian of the subdivision network is related to the group inverse matrix of the normalized laplacian of the initial given network. Our approach establishes a relationship between solutions of related Poisson problems on both structures and takes advantage on the properties of the group inverse matrix. As a consequence we get formulae for effective resistances and the Kirchhoff Index of the subdivision network expressed in terms of its corresponding in the base network. Finally, we study two examples where the base network are the star and the wheel, respectively.

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-61792-9_18 We study the flip graph of higher order Delaunay triangulations. A triangulation of a set S of n points in the plane is order-k Delaunay if for every triangle its circumcircle encloses at most k points of S. The flip graph of S has one vertex for each possible triangulation of S, and an edge connecting two vertices when the two corresponding triangulations can be transformed into each other by a flip (i.e., exchanging the diagonal of a convex quadrilateral by the other one). The flip graph is an essential structure in the study of triangulations, but until now it had been barely studied for order-k Delaunay triangulations. In this work we show that, even though the order-k flip graph might be disconnected for k = 3, any order-k triangulation can be transformed into some other order-k triangulation by at most k - 1 flips, such that the intermediate triangulations are of order at most 2k - 2, in the following settings: (1) for any k = 0 when S is in convex position, and (2) for any k = 5 and any point set S. Our results imply that the flip distance between two order-k triangulations is O(kn), as well as an efficient enumeration algorithm. E.A. was supported by RFBR, project number 20-01-00488. P.B. was partially supported by NSERC. P.C. was supported by CONACYT, MX. R.S. was supported by MINECO through the Ramón y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.

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 Cayley graphs of abelian groups. Such groups can be constructed using a generalization to Zn of the concept of congruence in 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. The research of C. Dalfó has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant agreement no. 734922.

© 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).

We develop splitting techniques to study Lyubeznik numbers of cover ideals of graphs which allow us to describe them for large families of graphs including forests, cycles, wheels and cactus graphs. More generally we are able to compute all the Bass numbers and the shape of the injective resolution of local cohomology modules by considering the connected components of the corresponding subgraphs. Indeed our method gives us a very simple criterion for the vanishing of these local cohomology modules in terms of the connected components., 31 pages

This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of mathematics and music on march 2020, available online at: http://www.tandfonline.com/10.1080/17459737.2020.1726690. Abstract scales are formalized as a cyclic group of classes of projection functions related to iterations of the scale generator. Their representatives in the frequency domain are used to built cyclic sequences of tone iterates satisfying the closure condition. The refinement of cyclic sequences with regard to the best closure provides a constructive algorithm that allows to determine cyclic scales avoiding continued fractions. New proofs of the main properties are obtained as a consequence of the generating procedure. When the scale tones are generated from the two elementary factors associated with the generic widths of the step intervals we get the partition of the octave leading to the fundamental Bézout’s identity relating several characteristic scale indices. This relationship is generalized to prove a new relationship expressing the partition that the frequency ratios associated with the two sizes composing the different step-intervals induce to a specific set of octaves.

For any $r$-graph $H$, we consider the problem of finding a rainbow $H$-factor in an $r$-graph $G$ with large minimum $\ell$-degree and an edge-colouring that is suitably bounded. We show that the asymptotic degree threshold is the same as that for finding an $H$-factor., Comment: 10 pages

List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs. J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P.

An $\epsilon$-distance-uniform graph is one in which from every vertex, all but an $\epsilon$-fraction of the remaining vertices are at some fixed distance $d$, called the critical distance. We consider the maximum possible value of $d$ in an $\epsilon$-distance-uniform graph with $n$ vertices. We show that for $\frac1n \le \epsilon \le \frac1{\log n}$, there exist $\epsilon$-distance-uniform graphs with critical distance $2^{\Omega(\frac{\log n}{\log \epsilon^{-1}})}$, disproving a conjecture of Alon et al. that $d$ can be at most logarithmic in $n$. We also show that our construction is best possible, in the sense that an upper bound on $d$ of the form $2^{O(\frac{\log n}{\log \epsilon^{-1}})}$ holds for all $\epsilon$ and $n$., Comment: 12 pages, 1 figure

Spatial networks are networks where nodes are located in a space equipped with a metric. Typically, the space is two-dimensional and until recently and traditionally, the metric that was usually considered was the Euclidean distance. In spatial networks, the cost of a link depends on the edge length, i.e. the distance between the nodes that define the edge. Hypothesizing that there is pressure to reduce the length of the edges of a network requires a null model, e.g. a random layout of the vertices of the network. Here we investigate the properties of the distribution of the sum of edge lengths in random linear arrangement of vertices, that has many applications in different fields. A random linear arrangement consists of an ordering of the elements of the nodes of a network being all possible orderings equally likely. The distance between two vertices is one plus the number of intermediate vertices in the ordering. Compact formulae for the 1st and 2nd moments about zero as well as the variance of the sum of edge lengths are obtained for arbitrary graphs and trees. We also analyze the evolution of that variance in Erdos–Rényi graphs and its scaling in uniformly random trees. Various developments and applications for future research are suggested.

For a fixed degree sequence $\mathcal{D}=(d_1,...,d_n)$, let $G(\mathcal{D})$ be a uniformly chosen (simple) graph on $\{1,...,n\}$ where the vertex $i$ has degree $d_i$. In this paper we determine whether $G(\mathcal{D})$ has a giant component with high probability, essentially imposing no conditions on $\mathcal{D}$. We simply insist that the sum of the degrees in $\mathcal{D}$ which are not 2 is at least $\lambda(n)$ for some function $\lambda$ going to infinity with $n$. This is a relatively minor technical condition, and when $\mathcal{D}$ does not satisfy it, both the probability that $G(\mathcal{D})$ has a giant component and the probability that $G(\mathcal{D})$ has no giant component are bounded away from $1$., Comment: 42 pages, to appear in Probability Theory and Related Fields

A digraph Γ =(V, E) is a line digraph when every pair of vertices u, v∈V have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that Γ is a locally line digraph. In this paper we give a new method to obtain a di-graph Γ′ cospectral with a given locally line digraph Γ with diameter D, where the diameter D′ of Γ′ is in the interval [D−1, D+1]. In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers. This research is supported by the Ministerio de Ciencia e Innovación and the European Regional Development Fund under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147.

© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ This paper generalizes and unifies the existing spectral bounds on the k-independence number of a graph, which is the maximum size of a set of vertices at pairwise distance greater than k. The previous bounds known in the literature follow as a corollary of the main results in this work.Weshow that for most cases our bounds outperform the previous known bounds. Some infinite families of graphs where the bounds are tight are also presented. Finally, as a byproduct, we derive some spectral lower bounds for the diameter of a graph.

We study Nash equilibria and the price of anarchy in the classic model of Network Creation Games introduced by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker in 2003. This is a selfish network creation model where players correspond to nodes in a network and each of them can create links to the other n−1 players at a prefixed price α>0. The player’s goal is to minimise the sum of her cost buying edges and her cost for using the resulting network. One of the main conjectures for this model states that the price of anarchy, i.e. the relative cost of the lack of coordination, is constant for all α. This conjecture has been confirmed for α=O(n1−δ) with δ≥1/logn and for α>4n−13. The best known upper bound on the price of anarchy for the remaining range is 2O(logn√) . We give new insights into the structure of the Nash equilibria for α>n and we enlarge the range of the parameter α for which the price of anarchy is constant. Specifically, we prove that for any small ϵ>0, the price of anarchy is constant for α>n(1+ϵ) by showing that any biconnected component of any non-trivial Nash equilibrium, if it exists, has at most a constant number of nodes. This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786.

A (1, ≤ ℓ)-identifying code in digraph D is a dominating subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs. This research is supported by the Catalan Research Council under project 2014SGR1147. The second and third authors have also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.

We introduce the (G,H)-isomorphism game, a new two-player non-local game that classical players can win with certainty iff the graphs G and H are isomorphic. We then define quantum and non-signalling isomorphisms by considering perfect quantum and non-signalling strategies for this game. We prove that non-signalling isomorphism coincides with fractional isomorphism, giving the latter an operational interpretation. We show that quantum isomorphism is equivalent to the feasibility of two polynomial systems obtained by relaxing standard integer programs for graph isomorphism to Hermitian variables. Finally, we provide a reduction from linear binary constraint system games to isomorphism games. This reduction provides examples of quantum isomorphic graphs that are not isomorphic, implies that the tensor product and commuting operator frameworks result in different notions of quantum isomorphism, and proves that both relations are undecidable. National Research Foundation (NRF) Accepted version AA was partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR), and by MINECO through TIN2013-48031-C4-1-P (TASSAT2). This work was carried out while LM was at the University of Bristol and supported by UK EPSRC under grant EP/L021005/1. This work was also carried out while DR was at University College London and supported by Cambridge Quantum Computing Ltd. and UK EPSRC, as well as Simone Severini and Fernando Brandao. RŠ is partially supported by grant GA ČR P202-12-G061 and by grant LL1201 ERC CZ of the Czech Ministry of Education, Youth and Sports. SS is supported by the Royal Society, the EPSRC, and the National Natural Science Foundation of China (NSFC). AV is supported in part by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13. Part of this work was done while AA, DR, and SS were visiting the Simons Institute for the Theory of Computing.

Suppose that there is a family of $n$ random points $X_v$ for $v \in V$, independently and uniformly distributed in the square $\left[-\sqrt{n}/2,\sqrt{n}/2\right]^2$ of area $n$. We do not see these points, but learn about them in one of the following two ways. Suppose first that we are given the corresponding random geometric graph $G$, where distinct vertices $u$ and $v$ are adjacent when the Euclidean distance $d_E(X_u,X_v)$ is at most $r$. If the threshold distance $r$ satisfies $n^{3/14} \ll r \ll n^{1/2}$, then the following holds with high probability. Given the graph $G$ (without any geometric information), in polynomial time we can approximately reconstruct the hidden embedding, in the sense that, `up to symmetries', for each vertex $v$ we find a point within distance about $r$ of $X_v$; that is, we find an embedding with `displacement' at most about $r$. Now suppose that, instead of being given the graph $G$, we are given, for each vertex $v$, the ordering of the other vertices by increasing Euclidean distance from $v$. Then, with high probability, in polynomial time we can find an embedding with the much smaller displacement error $O(\sqrt{\log n})$.

© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ A (simple) clutter is a family of pairwise incomparable subsets of a finite set . We say that a clutter is a domination clutter if there is at least a graph such that the collection of the inclusion-minimal dominating sets of vertices of is equal to . Given a clutter , we are interested in determining if it is a domination clutter and, if this is not the case, we want to find domination clutters in some sense close to it: the domination completions of . Here we will focus on the family of clutters containing all the subsets with the same cardinality; the uniform clutters of maximum size. Specifically, we characterize those clutters in this family that are domination clutters and, in any other case, we prove that the domination completions exist. Moreover, we then demonstrate that the clutter is uniquely determined by some of its domination completions, in the sense that can be recovered from some of these domination completions by using a suitable operation between clutters.

A identifying code in a digraph D is a subset C of vertices of D such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighbourhoods within C. In this paper, we give some suffcient conditions for a digraph of minimum in-degree to admit a identifying code. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree and girth at least 7 admits a identifying code. Moreover, we prove that every 1-in-regular digraph has a identifying code if and only if the girth of the digraph is at least. We also characterize all the 2-in-regular digraphs admitting a identifying code. This research has been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Generalitat de Catalunya. The last two authors have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. B. Martínez-Barona has been supported by the National Council of Science and Technology (CONACyT) of Mexico, Scholarship 438356.