Graph Distance Matrix

The graph distance matrix, sometimes also called the all-pairs shortest path matrix, is the square matrix consisting of all graph distances from vertex to vertex . The distance matrix for graphs was introduced by Graham and Pollak (1971).

The mean of all distances in a (connected) graph is known as the graph's mean distance. The maximum value of all distance matrix elements is known as the graph diameter.

The characteristic polynomial of the graph distance matrix is known as the distance polynomial.

The graph distance matrix can be computed in the Wolfram Language using the built-in function GraphDistanceMatrix[g], and precomputed distance matrices for many named graphs can be obtained using GraphData[graph, "DistanceMatrix"].

For a connected graph on vertices, the linear system of equations

(1)

where is the distance matrix and is the vector consisting of 1's, tends to have a real solution for "most" graphs (Steinerberger 2022). Exceptions include the complete -partite graphs and , the "double pac-man graph," the knight graph, and the 14-node cubic graph #52 and 11-node quartic graph #18 (in the numbering of GraphData). The numbers of connected graphs with no solution to the above equation on , 2, ... nodes are 1, 0, 0, 0, 0, 0, 2, 14, 398, 23923, ... (OEIS A354465). Dudarov et al. (2023) proved that such graphs exist for all .

The first few "ones vector not in distance matrix image graphs" that are also k-trees (which occurs for , 7, and 8 nodes) are illustrated above. The 8-node graphs #1 and 2 are 2-trees, while the 8-node graph #13 is a 4-tree (E. Weisstein, Jan. 18, 2024).

The real eigenvector with nonnegative entries associated with the largest eigenvalue (as guaranteed to exist by the Perron-Frobenius theorem) is nearly constant in the sense that the inner product satisfies

(2)

where is the -norm (Steinerberger 2022). However, the Perron-Frobenius eigenvectors for the distance matrices of the thousands of connected graphs in GraphData give an average value for that is close to as opposed to . The conditions under which this may be true is apparently an open problem, as noted by Steinerberger (2023). However, exact values for limiting cases of certain families are known, e.g.,

(3)

for the path graph , where is the positive root of (Ruzieh and Powers 1990, Steinerberger 2023), and

(4)

for the sun graph (Steinerberger 2023). These considerations are related to the definition of graph curvatures.