TOPICS

# Detour Matrix

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"].

Detour Index, Detour Polynomial, Graph Distance Matrix, Graph Circumference, Hamilton-Connected Graph, Hamilton-Laceable Graph, Longest Path, Spanning Tree

## Explore with Wolfram|Alpha

More things to try:

## References

Amić, D. and Trinajstić, N. "On the Detour Matrix." Croat. Chem. Acta 68, 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. Acta 71, 53-68, 1998.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

Detour Matrix

## Cite this as:

Weisstein, Eric W. "Detour Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DetourMatrix.html