The detour matrix ,
sometimes also called the maximum path matrix or maximal topological distances matrix,
of a graph is a symmetric matrix whose th entry is the length of the longest path from vertex
to vertex , or if there is no such path (Harary 1994, p. 203). The
most common convention (and that adopted here) is to take .
There is no efficient method for finding the entries of a detour matrix (Harary 1994, p. 203), 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 ,
where the maximum is taken over all spanning trees.
For a graph with vertex count, a detour matrix element of corresponds to a Hamiltonian
path between vertices and . A graph having a detour matrix whose off-diagonal elements
are all equal to
is therefore Hamilton-connected. Similarly,
a bipartite graph whose elements are maximal for all and corresponding to different elements of the vertex bipartition
is Hamilton-laceable.
Precomputed detour matrices for many named graphs are available in the Wolfram Language as GraphData[graph,
"DetourMatrix"].
Amić, D. and Trinajstić, N. "On the Detour Matrix." Croat. Chem. Acta68, 53-62, 1995.Devillers,
J. and Balaban, A. T. (Eds.). Topological
Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands:
Gordon and Breach, p. 44, 1999.Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, p. 203, 1994.Nikolić,
S.; Trinajstić, N.; and Mihalić, A. "The Detour Matrix and the Detour
Index." Ch. 6 in Topological
Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers A. T.
and Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 279-306, 2000.Randić,
M.; DeAlba, L. M.; Harris, F. E. "Graphs with the Same Detour Matrix."
Croat. Chem. Acta71, 53-68, 1998.Zamfirescu, T. "On
Longest Paths and Circuits in Graphs." Math. Scand.38, 211-239,
1976.
,
sometimes also called the maximum path matrix or maximal topological distances matrix,
of a graph is a symmetric matrix whose 
th entry is the length of the longest path from vertex
to vertex 
, or 
if there is no such path (Harary 1994, p. 203). The
most common convention (and that adopted here) is to take 
.
,
where the maximum is taken over all spanning trees.
, a detour matrix element of 
corresponds to a Hamiltonian
path between vertices 
and 
. A graph having a detour matrix whose off-diagonal elements
are all equal to 
is therefore Hamilton-connected. Similarly,
a bipartite graph whose elements 
are maximal for all 
and 
corresponding to different elements of the vertex bipartition
is Hamilton-laceable.
