On the image of graph distance matrices

2023/07/10 by Dudarov, William, Feinberg, Noah, Guo, Raymond +5 · 2 citations
#05C12 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2307.04740

Abstract

Let G=(V,E) be a finite, simple, connected, combinatorial graph on n vertices and let D ∈ ℝ^{n × 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,…, 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≥ 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.

Cited by

• Distance Exceptional Graphs and the Curvature Index
• Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity

Related

• Spectra of variants of distance matrices of graphs and digraphs: a survey
• Inverse of the Squared Distance Matrix of a Complete Multipartite Graph
• On the rank of the distance matrix of graphs
• On distance matrices of distance-regular graphs
• On distance matrices of graphs