On graphs with 2 trivial distance ideals (Q2174093)

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, the author gives an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. They are also related with other well known graph classes. Let \(G=(V,E)\) be a connected graph and \(X_G=\{x_u : u \in V(G)\}\) a set of indeterminates. The distance \(d_G(u,v)\) between the vertices \(u\) and \(v\) is the number of edges of a shortest path between them. Let \(\operatorname{diag}(X_G)\) denote the diagonal matrix with the indeterminates in the diagonal. The distance matrix \(D(G)\) of \(G\) is the matrix with rows and columns indexed by the vertices of \(G\) where the \(uv\)-entry is equal to \(d_G(u,v)\). Thus the generalized distance matrix \(D(G,X_G)\) of \(G\) is the matrix with rows and columns indexed by the vertices of \(G\) defined as \(\operatorname{diag}(X_G)+D(G)\). Note that one can recover the distance matrix from the generalized distance matrix by evaluating \(X_G\) at the zero vector, that is, \(D(G) = D(G,0)\). Let \(R[X_G]\) be the polynomial ring over a commutative ring \(R\) in the variables \(X_G\). For all \(i \in \lfloor n\rfloor := \{1,2,\dots,n\}\), the \(i\)-th distance ideal \(I^{R}_{i}(G,X_G)\) of \(G\) is the ideal over \(R[X_G]\) given by \(\langle\mathrm{minors}_i(D(G,X_G))\rangle\), where \(n\) is the number of vertices of \(G\) and \(\mathrm{minors}_i(D(G,X_G))\) is the set of the determinants of the \(i \times i\) submatrices of \(D(G,X_G)\). Distance ideals were defined by \textit{C. A. Alfaro} and \textit{L. Taylor} [Linear Algebra Appl. 584, 127--144 (2020; Zbl 1426.05060)] as a generalization of the Smith normal form of distance matrix and the distance spectra of graphs. In this paper, the discussion is held in the case when \(R\) is the ring of integers of numbers. Smith normal forms have been useful in understanding algebraic properties of combinatorial objects. For instance, computing the Smith normal form of the adjacency or Laplacian matrix is a standard technique used to determine the Smith group and the critical group of a graph. Smith normal forms can be computed using rows and column operations. In fact, \textit{R. Kannan} and \textit{A. Bachem} [SIAM J. Comput. 8, 499--507 (1979; Zbl 0446.65015)] found polynomial algorithms for computing the Smith normal form of an integer matrix. An alternative way of obtaining the Smith normal form is as follows. Let \(\Delta_i(G)\) denote the greatest common divisor of the \(i\)-minors of the distance matrix \(D(G)\), then its \(i\)-th invariant factor \(f_i\) is equal to \(\Delta_i(G)/\Delta_{i-1}(G)\), where \(\Delta_0(G) = 1\). Thus the Smith normal form of \(D(G)\) is equal to \(\operatorname{diag}(f_1,f_2,\dots,f_r,0,\dots,0)\). It is known that the Smith normal form may not exist in ring \(\mathbb{Z}[X]\), for example consider the following matrix with entries in the ring \(\mathbb{Z}[x]\) \[ \begin{bmatrix} 2 & 0 \\ 0 & x \\ \end{bmatrix} \quad. \] Little is known about the Smith normal forms of distance matrices. In the paper by \textit{Y. Hou} and \textit{C. Woo} [Linear Multilinear Algebra 56, No. 6, 611--626 (2008; Zbl 1149.05033)], the Smith normal forms of the distance matrices were determined for trees, wheels, cycles, and complements of cycles and are partially determined for complete multipartite graphs. In the paper by \textit{R. B. Bapat} and \textit{M. Karimi} [ibid. 65, No. 6, 1117--1130 (2017; Zbl 1360.05094)], the Smith normal form of the distance matrices of unicyclic graphs and of the wheel graph with trees attached to each vertex were obtained. An ideal is said to be unit or trivial if it is equal to \(\left\langle 1\right\rangle\). Let \(\Phi(G)\) denote the maximum integer \(i\) for which \(I^{\mathbb{Z}}_{i}(G,X_G)\) is trivial. Let \(\Lambda_k\) denote the family of graphs with at most \(k\) trivial distance ideals over \(\mathbb{Z}\). Note that every graph with at least one non-loop edge has at least one trivial distance ideals. On the other hand, let \(\phi(G)\) denote the number of invariant factors of the distance matrix of \(G\) equal to 1. In this case, every graph with at least one non-loop edge has at least two invariant factors equal to one. This paper intends to explore the properties of the family \(\Lambda_2\) of graphs with at most two trivial distance ideals over \(\mathbb{Z}\). In particular, the author has found an infinite number of graphs that are forbidden for \(\Lambda_2\). It is defined that \(F\) is the set of 17 graphs with certain properties. In Section 2, the author has proved that graphs in \(\Lambda_2\) are \(\left\{F,\text{odd-holes}\right\}\)-free graphs, where odd-holes are cycles of odd length greater or equal than 7. One of the main application in finding a characterization of \(\Lambda_2\) is that it is an approach to obtain a characterization of the graphs with \(\phi_Z(G)=2\) since they are contained in \(\Lambda_2\). It has been proved that the distance matrix of trees has exactly 2 invariant factors equal to 1. Therefore, \[ \text{trees} \subseteq \Lambda_2\subseteq \{F, \text{odd-holes}\}-\text{free graphs}. \] Among the forbidden graphs for \(\Lambda_2\) there are several graphs studied in other contexts, like bull and odd-holes. Another related family is the family of 3-leaf powers that was characterized as \(\left\{\text{bull, dart, gem}\right\}\)-free chordal graphs. Distance-hereditary graphs are another related family defined by \textit{E. Howorka} [Q. J. Math., Oxf. II. Ser. 28, 417--420 (1977; Zbl 0376.05040)]. A graph \(G\) is distance-hereditary if for each connected induced subgraph \(H\) of \(G\) and every pair \(u\) and \(v\) of vertices in \(H\), \(d_H(u,v) = d_G(u,v)\). Distance-hereditary graphs are \(\left\{\text{house, gem, domino, holes}\right\}\)-free graphs, where holes are cycles of length greater than or equal 5 which intersects with \(\Lambda_2\). Also, if \(H\) is a connected induced subgraph of a distance-hereditary graph \(G\), then \(I^{R}_{i}(H, X_H) \subseteq I^{R}_{i}(G,X_G)\) for all \(i \leq \left|V(H)\right|\). Previously, an analogous notion to the distance ideals but for the adjacency and Laplacian matrices was explored. They are called critical ideal. It was found new connections in contexts different from the Smith group or sandpile group like the zero-forcing number and the minimum rank of a graph. In this setting, the set of forbidden graphs for the family with at most \(k\) trivial critical ideals is conjectured to be finite. It is interesting that for distance ideals this is not true. A graph \(G\) is forbidden for \(\Lambda_k\) if the \((k+1)\)-th distance ideal of \(G\) is trivial. In addition, a forbidden graph \(H\) for \(\Lambda_k\) is minimal if \(H\) does not contain a connected forbidden graph for \(\Lambda_k\) as induced subgraph, and any graph \(G\) containing \(H\) as induced subgraph, have that \(G\) is forbidden for \(\Lambda_k\). The set of minimal forbidden graphs for \(\Lambda_k\) is denoted by \(\mathrm{Forb}_k\). The author prove several results. The paper is well-written. The standard of the paper is good. Researchers will benefit a lot by reading this paper.