Search

We focus on strongly connected, strong for short, digraphs since in this setting distance is defined for every pair of vertices. Distance ideals generalize the spectrum and Smith normal form of several distance matrices associated with strong digraphs. We introduce the concept of pattern which allow us to characterize the family $\Gamma_1$ of digraphs with only one trivial distance ideal over ${\mathbb Z}$. This result generalizes an analogous result for undirected graphs that states that connected graphs with one trivial ideal over $\mathbb{Z}$ consists of either complete graphs or complete bipartite graphs. It turns out that the strong digraphs in $\Gamma_1$ consists in the circuit with 3 vertices and a family $\Lambda$ of strong digraphs that contains complete graphs and complete bipartite graphs, regarded as digraphs. We also compute all distance ideals of some strong digraphs in the family $\Lambda$. Then, we explore circuits, which turn out to be an infinite family of minimal forbidden digraphs, as induced subdigraphs, for the strong digraphs in $\Gamma_1$. This suggests that a characterization of $\Gamma_1$ in terms of forbidden induced subdigraphs is harder than using patterns., Comment: 18 pages, 10 figures

The Abelian sandpile model was the first example of a self-organized critical system studied by Bak, Tang and Wiesenfeld. The dynamics of the sandpiles occur when the grains topple over a graph. In this study, we allow the graph to evolve over time and change the topology at each stage. This turns out in the occurrence of phenomena impossible in the classical sandpile models. For instance, configurations over evolutive graphs that are always unstable. We also experiment with the stabilization of configurations with a large number of grains at the center over evolutive graphs, this allows us to obtain interesting fractals. Finally, we obtain some power laws associated with some evolutive graphs., Comment: 13 pages, 7 figures, 2 codes

It is well known that the spectrum and the Smith normal form of a matrix can be computed in polynomial time. Thus, it is interesting to explore how good are these parameters for distinguishing graphs. This is relevant since it is related to the Graph Isomorphism Problem (GIP), which asks to determine whether two graphs are isomorphic. In this paper, we explore the computational advantages of using the spectrum and the Smith normal form of two matrices associated with a graph. By considering the SNF or the spectrum of two matrices of a graph as a single parameter, we compute the number of non-isomorphic graphs with the same parameter with up to 9 vertices, and with up to 10 vertices when the number of graphs with 9 vertices with the same parameter is less than 1000. Focusing on the best 20 combinations of matrices for graphs with 10 vertices, we notice that the number of such graphs with a mate is less than 100 in any of these 20 cases. This computational result improves on similar previous explorations. Therefore, the use of the spectrum or the SNF of two matrices at the same time shows a substantial improvement in distinguishing graphs.

The search for a highly discriminating and easily computable invariant to distinguish graphs remains a challenging research topic. Here we focus on cospectral graphs whose complements are also cospectral (generalized cospectral), and on coinvariant graphs (same Smith normal form) whose complements are also coinvariant (generalized coinvariant). We show a new characterization of generalized cospectral graphs in terms of codeterminantal graphs. We also establish the Smith normal form of some graph classes for certain associated matrices, and as an application, we prove that the Smith normal form can be used to uniquely determine star graphs. Finally, for graphs up to 10 vertices, we present enumeration results on the number of generalized cospectral graphs and generalized coinvariant graphs with respect to several associated matrices.

The utility of a matrix satisfying the Strong Spectral Property has been well established particularly in connection with the inverse eigenvalue problem for graphs. More recently the class of graphs in which all associated symmetric matrices possess the Strong Spectral Property (denoted $G^{SSP}$) were studied, and along these lines we aim to study properties of graphs that exhibit a so-called barbell partition. Such a partition is a known impediment to membership in the class $G^{SSP}$. In particular we consider the existence of barbell partitions under various standard and useful graph operations.

In~\cite{algorithmic} was given an algorithm that computes arithmetical structures on matrices. We use some of the ideas contained there to get an algorithm that computes arithmetical structures over dominated polynomials. A dominated polynomial is an integer multivariate polynomial such that contains a monomial which is divided by all its monomials., Comment: This article correspond to an unpublished part of article arXiv:2101.05238

Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing, and provide constructions of infinite families of pairs of cospectral graphs which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.

If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $\pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.

We compute the sandpile groups of families of planar graphs having a common weak dual by evaluating the indeterminates of the critical ideals of the weak dual at the lengths of the cycles bounding the interior faces. This method allow us to determine the algebraic structure of the sandpile groups of outerplanar graphs, and can be used to compute the sandpile groups of many other planar graph families. Finally, we compute the identity element for the sandpile groups of the dual graphs of many outerplane graphs., Comment: 21 pages

We give a characterization of the graphs with at most three trivial characteristic ideals. This implies the complete characterization of the regular graphs whose critical groups have at most three invariant factors equal to 1 and the characterization of the graphs whose Smith groups have at most 3 invariant factors equal to 1. We also give an alternative and simpler way to obtain the characterization of the graphs whose Smith groups have at most 3 invariant factors equal to 1, and a list of minimal forbidden graphs for the family of graphs with Smith group having at most 4 invariant factors equal to 1., Comment: 21 pages