The distance ideals of graphs are algebraic invariants that generalize the Smith normal form (SNF) and the spectrum of several distance matrices associated with a graph. In general, distance ideals are not monotone under taking induced subgraphs. However, in [7] the characterizations of connected graphs with one trivial distance ideal over $\mathbb{ Z}[X]$ and over $\mathbb{ Q}[X]$ were obtained in terms of induced subgraphs, where $X$ is a set of variables indexed by the vertices. Later, in [3], the first attempt was made to characterize the family of connected graphs with at most two trivial distance ideals over $\mathbb{ Z}[X]$. There, it was proven that these graphs are $\{ \mathcal { F},\textsf{ odd-holes}_{ 7}\}$-free, where $\textsf{ odd-holes}_{ 7}$ consists of the odd cycles of length at least seven and $\mathcal{ F}$ is a set of sixteen graphs. Here, we give a characterization of the $\{ \mathcal{ F},\textsf{ odd-holes}_{ 7}\}$-free graphs and prove that the $\{ \mathcal{ F},\textsf{ odd-holes}_{ 7}\}$-free graphs are precisely the graphs with at most two trivial distance ideals over $\mathbb{ Z}[X]$. As byproduct, we also find that the determinant of the distance matrix of a connected bipartite graph is even, this suggests that it is possible to extend, to connected bipartite graphs, the Graham-Pollak-Lov\'asz celebrated formula $\det(D(T_{ n+1}))=(-1)^nn2^{ n-1}$, and the Hou-Woo result stating that $\text{ SNF}(D(T_{ n+1}))=\textsf{ I}_2\oplus 2\textsf{ I}_{ n-2}\oplus (2n)$, for any tree $T_{ n+1}$ with $n+1$ vertices. Finally, we also give the characterizations of graphs with at most two trivial distance ideals over $\mathbb{ Q}[X]$, and the graphs with at most two trivial distance univariate ideals.
Categories: math.CO