maximal topological distances matrix | maximum path matrix

The detour matrix Δ, sometimes also called the maximum path matrix or maximal topological distances matrix, of a graph is a symmetric matrix whose (i, j) th entry is the length of the longest path from vertex i to vertex j, or ∞ if there is no such path. The most common convention (and that adopted here) is to take (Δ)_(i i) = 0. There is no efficient method for finding the entries of a detour matrix, but the detour matrix can be computed by finding the set of all spanning trees for a given graph, finding their distance matrices, and setting (Δ)_(i j) = max_(i, j) d_(i j), where the maximum is taken over all spanning trees.

detour index | detour polynomial | graph circumference | graph distance matrix | Hamilton-connected graph | Hamilton-laceable graph | longest path | spanning tree