Detour Matrix

The detour matrix Delta, 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 infty if there is no such path (Harary 1994, p. 203). The most common convention (and that adopted here) is to take (Delta)_(ii)=0.

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 (Delta)_(ij)=max_(i,j)d_(ij), where the maximum is taken over all spanning trees.

For a graph with vertex count n, a detour matrix element of (Delta)_(ij)=n-1 corresponds to a Hamiltonian path between vertices i and j. A graph having a detour matrix whose off-diagonal elements are all equal to n-1 is therefore Hamilton-connected. Similarly, a bipartite graph whose elements (Delta)_(i,j) are maximal for all i and j 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"].

See also

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

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Detour Matrix

Cite this as:

Weisstein, Eric W. "Detour Matrix." From MathWorld--A Wolfram Web Resource.

Subject classifications