On the image of graph distance matrices

Abstract

Let $G=(V,E)$ be a finite, simple, connected, combinatorial graph on $n$ vertices and let $D\in {\mathbb{R}}^{n\times n}$ be its graph distance matrix $D_{ij}=d(v_i,v_j)$. Steinerberger (J. Graph Theory, 2023) empirically observed that the linear system of equations $Dx=1$, where $1=(1,1,\dots ,1{)}^T$, very frequently has a solution (even in cases where $D$ is not invertible). The smallest nontrivial example of a graph where the linear system is not solvable are two graphs on 7 vertices. We prove that, in fact, counterexamples exists for all $n\ge 7$. The construction is somewhat delicate and further suggests that such examples are perhaps rare. We also prove that for Erdős-Rényi random graphs the graph distance matrix $D$ is invertible with high probability. We conclude with some structural results on the Perron-Frobenius eigenvector for a distance matrix.

4 figures