The detour polynomial of a graph is the characteristic polynomial of the detour matrix of .
Precomputed detour polynomials for many named graphs are available in the Wolfram Language as GraphData[graph, "DetourPolynomial"].
Since a Hamilton-connected graph with vertex count has all off-diagonal matrix elements equal to , the detour polynomial of such a graph is given by .
The following table summarizes detour polynomials for some common classes of graphs. Here, is a Chebyshev polynomial of the first kind and is a Chebyshev polynomial of the second kind.
The following table summarizes the recurrence relations for detour polynomials for some simple classes of graphs.
graph | order | recurrence |
path graph | 5 |