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 was studied by Hakimi and Yau (1965) and Graham and Pollak (1971).

The mean of all entries of this matrix in a (connected) graph is one convention for the graph's mean distance. For graphs on at least two vertices, another common convention omits the diagonal zero entries and averages over unordered vertex pairs. 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 2023, Chen and Tsui 2025). 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).

For a connected graph , let be the real eigenvector with nonnegative entries associated with the largest eigenvalue, normalized by . Such a vector is guaranteed to exist by the Perron-Frobenius theorem. It is nearly constant in the sense that the inner product satisfies

(2)

where is the -norm (Steinerberger 2023). In the study of 7642 connected graphs on vertices from the Mathematica 12 database, Steinerberger (2023) reported an average value of close to 0.996, compared with . Steinerberger (2023) asked whether this behavior could be made precise or quantified. 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 on vertices (Steinerberger 2023). These considerations are related to the definition of graph curvatures.