Speaker
Description
The distance ideals of connected graphs are algebraic invariants extending the Smith normal form (SNF) and the spectrum of graph distance matrices.
In general, distance ideals are not monotone under taking induced subgraphs.
However, it was proved in 2017 that the set of graphs with one trivial distance ideal over $\mathbb{Z}[X]$ and over $\mathbb{Q}[X]$ was characterized in terms of induced subgraphs, where $X$ is a set of variables indexed by the vertices.
Here, we give a characterization of the $\{\mathcal{F},\textsf{odd-holes}_{7}\}$-free graphs, where $\textsf{odd-holes}_{7}$ consists of the odd cycles of length at least seven and $\cal F$ is a set of sixteen graphs. Moreover, we show 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 bipartite graphs, the Graham-Pollak-Lovász celebrated formula $\det(D(T_{n+1}))=(-1)^nn2^{n-1}$, and Hou-Woo's result stating that $\text{SNF}(D(T_{n+1}))=\sf{I}_2\oplus 2\sf{I}_{n-2}\oplus (2n)$, for any tree $T_{n+1}$ with $n+1$ vertices.
Furthermore, we also determine the graphs with at most two trivial distance ideals over $\mathbb{Q}[X]$, and the graphs with at most two trivial distance univariate ideals. We conclude by showing that the SNF of the distance matrix of a graph has exactly two invariant factors equal to 1 if and only if it is bipartite or complete tripartite.