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

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.