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.

Let $H$ be a graph possibly with loops and $G$ be a multigraph without loops. An $H$-coloring of $G$ is a function $c: E(G) \rightarrow V(H)$. We will say that $G$ is an $H$-colored multigraph, whenever we are taking a fixed $H$-coloring of $G$. The set of all the edges with end vertices $u$ and $v$ will be denoted by $E_{uv}$. We will say that $W=(v_0,e_0^1, \ldots, e_0^{k_0},v_1,e_1^1,\ldots,e_1^{k_1},v_2,\ldots,v_{n-1},e_{n-1}^1,\ldots,e_{n-1}^{k_{n-1}},v_n)$, where for each $i$ in $\{0,\ldots,n-1\}$, $k_i \geq 1$ and $e_i^j \in E_{v_iv_{i+1}}$ for every $j \in \{1,\ldots, k_i \}$, is a dynamic $H$-walk iff $c(e_i^{k_i})c(e_{i+1}^1)$ is an edge in $H$, for each $i \in \{0,\ldots,n-2\}$. We will say that a dynamic $H$-walk is a closed dynamic $H$-walk whenever $v_0=v_n$ and $c(e_{n-1}^{k_{n-1}})c(e_0^1)$ is an edge in $H$. Moreover, a closed dynamic $H$-walk is called dynamic $H$-cycle whenever $v_i\neq v_j$, for every $\{i,j\}\subseteq \{0,\ldots,v_{n-1}\}$. In particular, a dynamic $H$-walk is an $H$-walk whenever $k_i=1$, for every $i \in \{0,\ldots,n-1\}$, and when $H$ is a complete graph without loops, an $H$-walk is well known as a properly colored walk. In this work, we study the existence and length of dynamic $H$-cycles, dynamic $H$-trails and dynamic $H$-paths in $H$-colored multigraphs. To accomplish this, we introduce a new concept of color degree, namely, the \textit{dynamic degree}, which allows us to extend some classic results, as Ore's Theorem, for $H$-colored multigraphs. Also, we give sufficient conditions for the existence of hamiltonian dynamic $H$-cycles in $H$-colored multigraphs, and as a consequence, we obtain sufficient conditions for the existence of properly colored hamiltonian cycle in edge-colored multigraphs, with at least $c\geq 3$ colors., Comment: arXiv admin note: text overlap with arXiv:2207.03623

Let $G$ be a connected graph with adjacency matrix $A(G)$. The distance matrix $D(G)$ of $G$ has rows and columns indexed by $V(G)$ with $uv$-entry equal to the distance $\mathrm{dist}(u,v)$ which is the number of edges in a shortest path between the vertices $u$ and $v$. The transmission $\mathrm{trs}(u)$ of $u$ is defined as $\sum_{v\in V(G)}\mathrm{dist}(u,v)$. Let $\mathrm{trs}(G)$ be the diagonal matrix with the transmissions of the vertices of $G$ in the diagonal, and $\mathrm{deg}(G)$ the diagonal matrix with the degrees of the vertices in the diagonal. In this paper we investigate the Smith normal form (SNF) and the spectrum of the matrices $D^{\mathrm{deg}}_+(G):=\mathrm{deg}(G)+D(G)$, $D^{\mathrm{deg}}(G):=\mathrm{deg}(G)-D(G)$, $A^{\mathrm{trs}}_+(G):=\mathrm{trs}(G)+A(G)$ and $A^{\mathrm{trs}}(G):=\mathrm{trs}(G)-A(G)$. In particular, we explore how good the spectrum and the SNF of these matrices are for determining graphs up to isomorphism. We found that the SNF of $A^{\mathrm{trs}}$ has an interesting behaviour when compared with other classical matrices. We note that the SNF of $A^{\mathrm{trs}}$ can be used to compute the structure of the sandpile group of certain graphs. We compute the SNF of $D^{\mathrm{deg}}_+$, $D^{\mathrm{deg}}$, $A^{\mathrm{trs}}_+$ and $A^{\mathrm{trs}}$ for several graph families. We prove that complete graphs are determined by the SNF of $D^{\mathrm{deg}}_+$, $D^{\mathrm{deg}}$, $A^{\mathrm{trs}}_+$ and $A^{\mathrm{trs}}$. Finally, we derive some results about the spectrum of $D^{\mathrm{deg}}$ and $A^{\mathrm{trs}}$., Comment: 19 pages

Alternating Euler trails has been extensively studied for its diverse applications, for example, in genetic and molecular biology, social science and channel assignment in wireless networks, as well as for theoretical reasons. We will consider the following edge-coloring. Let $H$ be a graph possibly with loops and $G$ a graph without loops. An $H$-coloring of $G$ is a function $c: E(G) \rightarrow V(H)$. We will say that $G$ is an $H$-colored graph whenever we are taking a fixed $H$-coloring of $G$. A sequence $W=(v_0,e_0^1, \ldots, e_0^{k_0},v_1,e_1^1,\ldots,e_{n-1}^{k_{n-1}},v_n)$ in $G$, where for each $i \in \{0,\ldots, n-1\}$, $k_i \geq 1$ and $e_i^j = v_iv_{i+1}$ is an edge in $G$, for every $j \in \{1,\ldots, k_i \}$, is a dynamic $H$-trail if $W$ does not repeat edges and $c(e_i^{k_i})c(e_{i+1}^1)$ is an edge in $H$, for each $i \in \{0,\ldots,n-2\}$. In particular a dynamic $H$-trail is an alternating Euler trail when $H$ is a complete graph without loops and $k_i=1$, for every $i \in \{1,\ldots,n-1\}$. In this paper, we introduce the concept of dynamic $H$-trail, which arises in a natural way in the modeling of many practical problems, in particular, in theoretical computer science. We provide necessary and sufficient conditions for the existence of closed Euler dynamic $H$-trail in $H$-colored multigraphs. Also we provide polynomial time algorithms that allows us to convert a cycle in an auxiliary graph, $L_2^H(G)$, in a closed dynamic H-trail in $G$, and vice versa, where $L_2^H(G)$ is a non-colored simple graph obtained from $G$ in a polynomial time., Comment: 14 pages, 4 figures

It is well known that recurrent sandpile configurations can be characterized as the optimal solution of certain optimization problems. In this article, we present two new integer linear programming models, one that computes recurrent configurations and other that computes the order of the configuration. Finally, by using duality of linear programming, we are able to compute the identity configuration for the cone of a regular graph., Comment: Sandpile group, recurrent configurations, integer linear programming

We present enumeration results on the number of connected graphs up to 10 vertices for which there is at least one other graph with the same spectrum (a cospectral mate), or at least one other graph with the same Smith normal form (coinvariant mate) with respect to several matrices associated to a graph. The present data give some indication that possibly the Smith normal form of the distance Laplacian and the signless distance Laplacian matrices could be a finer invariant to distinguish graphs in cases where other algebraic invariants, such as those derived from the spectrum, fail. Finally, we show a new graph characterization using the Smith normal form of the signless distance Laplacian matrix.

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

Determinantal ideals of graphs generalize, among others, the spectrum and the Smith normal form (SNF) of integer matrices associated to graphs. In this work we investigate the relationship of the spectrum and the SNF with the determinantal ideals. We show that an eigenvalue divides the $k$-th invariant factor of its SNF if the eigenvalue belongs to a variety of the $k$-th univariate integer determinantal ideal of the matrix. This result has as a corollary a theorem of Rushanan. We also study graphs having the same determinantal ideals with at most one indeterminate; the socalled codeterminantal graphs, which generalize the concepts of cospectral and coinvariant graphs. We establish a necessary and sufficient condition for graphs to be codeterminantal on $\mathbb{R}[x]$, and we present some computational results on codeterminantal graphs up to 9 vertices. Finally, we show that complete graphs and star graphs are determined by the SNF of its distance Laplacian matrix., Comment: arXiv admin note: text overlap with arXiv:1401.1773 by other authors

A linear system is a pair $(P,\mathcal{L})$ where $\mathcal{L}$ is a family of subsets on a ground finite set $P$, such that $|l\cap l^\prime|\leq 1$, for every $l,l^\prime \in \mathcal{L}$. The elements of $P$ and $\mathcal{L}$ are called points and lines, respectively, and the linear system is called intersecting if any pair of lines intersect in exactly one point. A subset $T$ of points of $P$ is a transversal of $(P,\mathcal{L})$ if $T$ intersects any line, and the transversal number, $\tau(P,\mathcal{L})$, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system $(P,\mathcal{L})$ is a set $R$ of lines, such that any three of them have a common point, then the 2-packing number of $(P,\mathcal{L})$, $\nu_2(P,\mathcal{L})$, is the size of a maximum 2-packing set. It is known that the transversal number $\tau(P,\mathcal{L})$ is bounded above by a quadratic function of $\nu_2(P,\mathcal{L})$. An open problem is to haracterize the families of linear systems which satisfies $\tau(P,\mathcal{L})\leq \lambda\nu_2(P,\mathcal{L})$, for some $\lambda\geq1$. In this paper, we give an infinite family of linear systems $(P,\mathcal{L})$ which satisfies $\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})$ with smallest possible cardinality of $\mathcal{L}$, as well as some properties of $r$-uniform intersecting linear systems $(P,\mathcal{L})$, such that $\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})=r$. Moreover, we state a characterization of $4$-uniform intersecting linear systems $(P,\mathcal{L})$ with $\tau(P,\mathcal{L})=\nu_2(P,\mathcal{L})=4$., Comment: 11 pages, 3 figures, arXiv admin note: text overlap with arXiv:1509.03696

We give a detailed review of two algorithms that solve the minimization case of the assignment problem. The Bertsekas' auction algorithm and the Goldberg & Kennedy algorithm. We will show that these algorithms are equivalent in the sense that both perform equivalent steps in the same order. We also present experimental results comparing the performance of three algorithms for the assignment problem. They show the auction algorithm performs and scales better in practice than algorithms that are harder to implement but have better theoretical time complexity., Comment: 21 pages, 6 figures

Distance ideals generalize the Smith normal form of the distance matrix of a graph. The family of graphs with 2 trivial distance ideals contains the family of graphs whose distance matrix has at most 2 invariant factors equal to 1. Here we give an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. These are also related with other well known graph classes., Comment: Some typos were corrected

Recently, there have been found new relations between the zero forcing number and the minimum rank of a graph with the algebraic co-rank. We continue on this direction by giving a characterization of the graphs with real algebraic co-rank at most 2. This implies that for any graph with at most minimum rank at most 3, its minimum rank is bounded from above by its real algebraic co-rank., Comment: 8 pages, 2 figures. arXiv admin note: text overlap with arXiv:1710.03386

There are profound relations between the zero forcing number and minimum rank of a graph. We study the relation of both parameters with a third one, the algebraic co-rank; that is defined as the largest $i$ such that the $i$-th critical ideal is trivial. This gives a new perspective for bounding and computing these three graph parameters.

A linear system is a pair $(P,\mathcal{L})$ where $\mathcal{L}$ is a family of subsets on a ground finite set $P$ such that $|l\cap l^\prime|\leq 1$, for every $l,l^\prime \in \mathcal{L}$. If all elements of $\mathcal{L}$ of a linear system $(P,\mathcal{L})$, then the linear system is called $r$-uniform linear system. The transversal number of a linear system $(P,\mathcal{L})$, $\tau(P,\mathcal{L})$, is the minimum cardinality of a subset $\hat{P}\subseteq P$ satisfying $l\cap\hat{P}\neq\emptyset$, for every $l\in\mathcal{L}$. The 2-packing number of a linear system $(P,\mathcal{L})$, $\nu_2(P,\mathcal{L})$, is the maximum cardinality of a subset $R\subseteq\mathcal{L}$ such that, any three elements of $R$ don't have a common point (are triplewise disjoint), that is, if three elements are chosen in $R$, then they are not incidents in a common point. For $r\geq2$, let $(P,\mathcal{L})$ be an $r$-uniform linear system. In "{\sc M. A. Henning and A. Yeo:} {\it Hypergraphs with large transversal number,} Discrete Math. {\bf 313} (2013), no. 8, 959--966." Henning and Yeo state the following question: Is it true that if $(P,\mathcal{L})$ is an $r$-uniform linear system then $\tau(P,\mathcal{L})\leq\displaystyle\frac{|P|+|\mathcal{L}|}{r+1}$ holds for all $r\geq2$?. In this note, we give some results of $r$-uniform linear systems, whose 2-packing number is fixed, satisfying the inequality.

We introduce the concept of distance ideals of graphs, which can be regarded as a generalization of the Smith normal form and the spectra of the distance matrix of a graph. We obtain a classification of the graphs with at most one trivial distance ideal., Comment: 17 pages

Critical ideals generalize the critical group, Smith group and the characteristic polynomials of the adjacency and Laplacian matrices of a graph. We give a complete characterization of the digraphs with at most one trivial critical ideal. Which implies the characterizations of the digraphs whose critical group has one invariant factor equal to one, and the digraphs whose Smith group has one invariant factor equal to one., Comment: 12 pages, 4 figures

Let $G$ be a finite additive abelian group of odd order $n$, and let $G^*=G\setminus\{0\}$ be the set of non-zero elements. A starter for $G$ is a set $S=\{\{x_i,y_i\}:i=1,\ldots,\frac{n-1}{2}\}$ such that $\{x_1,\ldots,x_\frac{n-1}{2},y_1,\ldots,y_\frac{n-1}{2}\}=G^*$ and $\{\pm(x_i-y_i):i=1,\ldots,\frac{n-1}{2}\}=G^*$. Moreover, if $\left|\left\{x_i+y_i:i=1,\ldots,\frac{n-1}{2}\right\}\right|=\frac{n-1}{2}$, then $S$ is called a strong starter for $G$. A starter $S$ for $G$ is a $k$ quotient starter if there exists $Q\subseteq G^*$ of cardinality $k$ such that $y_i/x_i\in Q$ or $x_i/y_i\in Q$, for $i=1,\ldots,\frac{n-1}{2}$. In this paper, we give examples of two-quotient strong starters for $\mathbb{F}_q$, where $q=2^kt+1$ is a prime power with $k>1$ a positive integer and $t$ an odd integer greater than 1.

Motivated by a problem asked by Richter and by the long standing Harary-Hill conjecture, we study the relation between the crossing number of a graph $G$ and the crossing number of its cone $CG$, the graph obtained from $G$ by adding a new vertex adjacent to all the vertices in $G$. Simple examples show that the difference $cr(CG)-cr(G)$ can be arbitrarily large for any fixed $k=cr(G)$. In this work, we are interested in finding the smallest possible difference, that is, for each non-negative integer $k$, find the smallest $f(k)$ for which there exists a graph with crossing number at least $k$ and cone with crossing number $f(k)$. For small values of $k$, we give exact values of $f(k)$ when the problem is restricted to simple graphs, and show that $f(k)=k+\Theta (\sqrt {k})$ when multiple edges are allowed.

For central banks, managing the minting is one of the most important task since a shortage yields negative economic and social impacts, and the budget committed for minting is one of the largest within the central banks. Hence, the central bank requires to find the mixture of coins to be produced that satisfies the demand, inventory and production constraints while minimizing the cost. We propose a mixed-integer programming model that minimize the cost of minting by reducing the number of extra-shifts required while fulfilling the constraints. We also perform a simulation with data of a central bank which shows that the model reduces in 24\% the cost of extra-shifts used during 21 quarters, compared with the spreadsheet based approach used currently at the operation., Comment: 13 pages, 5 figures

This paper studies critical ideals of graphs with twin vertices, which are vertices with the same neighbors. A pair of such vertices are called replicated if they are adjacent, and duplicated, otherwise. Critical ideals of graphs having twin vertices have good properties and show regular patterns. Given a graph $G=(V,E)$ and ${\bf d}\in \mathbb{Z}^{|V|}$, let $G^{\bf d}$ be the graph obtained from $G$ by duplicating ${\bf d}_v$ times or replicating $-{\bf d}_v$ times the vertex $v$ when ${\bf d}_v>0$ or ${\bf d}_v<0$, respectively. Moreover, given $\delta\in \{0,1,-1\}^{|V|}$, let \[ \mathcal{T}_{\delta}(G)=\{G^{\bf d}: {\bf d}\in \mathbb{Z}^{|V|} \text{ such that } {\bf d}_v=0 \text{ if and only if }\delta_v=0 \text{ and } {\bf d}_v\delta_v>0 \text{ otherwise}\} \] be the set of graphs sharing the same pattern of duplication or replication of vertices. More than one half of the critical ideals of a graph in $\mathcal{T}_{\delta}(G)$ can be determined by the critical ideals of $G$. The algebraic co-rank of a graph $G$ is the maximum integer $i$ such that the $i$-{\it th} critical ideal of $G$ is trivial. We show that the algebraic co-rank of any graph in $\mathcal{T}_{\delta}(G)$ is equal to the algebraic co-rank of $G^{\delta}$. For a large enough ${\bf d}\in \mathbb{Z}^{V(G)}$, we show that the critical ideals of $G^{\bf d}$ have similar behavior to the critical ideals of the disjoint union of $G$ and some set $\{K_{n_v}\}_{\{v\in V(G)| d_v<0\}}$ of complete graphs and some set $\{T_{n_v}\}_{\{v\in V(G) \, |\, {\bf d}_v>0\}}$ of trivial graphs. Additionally, we pose important conjectures on the distribution of the algebraic co-rank of the graphs with twins vertices. These conjectures imply that twin-free graphs have a large algebraic co-rank, meanwhile a graph having small algebraic co-rank has at least one pair of twin vertices., Comment: 26 pages, 9 figures. Major changes from the previous version. Accepted in Advanced in Applied Mathematics

The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. In this article we provide a set of minimal forbidden graphs for the set of graphs with at most three trivial critical ideals. Then we use these forbidden graphs to characterize the graphs with at most three trivial critical ideals and clique number equal to 2 and 3., Comment: 33 pages, 3 figures

The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. A basic property of the critical ideals of graphs asserts that the graphs with at most k trivial critical ideals, $\Gamma_{\leq k}$, are closed under induced subgraphs. In this article we find the set of minimal forbidden subgraphs for $\Gamma_{\leq 2}$, and we use this forbidden subgraphs to get a classification of the graphs in $\Gamma_{\leq 2}$. As a consequence we give a classification of the simple graphs whose critical group has two invariant factors equal to one. At the end of this article we give two infinite families of forbidden subgraphs., Comment: 15 pages, 2 figures

The statistical analysis of tree structured data is a new topic in statistics with wide application areas. Some Principal Component Analysis (PCA) ideas were previously developed for binary tree spaces. In this study, we extend these ideas to the more general space of rooted and labeled trees. We re-define concepts such as tree-line and forward principal component tree-line for this more general space, and generalize the optimal algorithm that finds them. We then develop an analog of classical dimension reduction technique in PCA for the tree space. To do this, we define the components that carry the least amount of variation of a tree data set, called backward principal components. We present an optimal algorithm to find them. Furthermore, we investigate the relationship of these the forward principal components, and prove a path-independency property between the forward and backward techniques. We apply our methods to a data set of brain artery data set of 98 subjects. Using our techniques, we investigate how aging affects the brain artery structure of males and females. We also analyze a data set of organization structure of a large US company and explore the structural differences across different types of departments within the company.

In this article, we give a partial description of the sandpile group of the cone of the cartesian product of graphs in function of the sandpile group of the cone of their factors. Also, we introduce the concept of uniform homomorphism of graphs and prove that every surjective uniform homomorphism of graphs induces an injective homomorphism between their sandpile groups. As an application of these result we obtain an explicit description of a set of generators of the sandpile group of the cone of the hypercube of dimension d., Comment: 20 pages, 11 figures. The title was changed, other impruvements were made throughout the article. To appear in Linear Algebra and Its Applications