Detour Polynomial

The detour polynomial of a graph G is the characteristic polynomial of the detour matrix of G.

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 n has all off-diagonal matrix elements equal to n-1, the detour polynomial of such a graph is given by (x-(n-1)^2)(x+n-1)^(n-1).

The following table summarizes detour polynomials for some common classes of graphs. Here, T_n is a Chebyshev polynomial of the first kind and U_n is a Chebyshev polynomial of the second kind.

The following table summarizes the recurrence relations for detour polynomials for some simple classes of graphs.

path graph P_n5p_n(x)=x^5(-p_(n-5)(x))-(5x+4)x^3p_(n-4)(x)-2(5x^2+6x+2)xp_(n-3)(x)-2(5x^2+6x+2)p_(n-2)(x)-(5x+4)p_(n-1)(x)

See also

Characteristic Polynomial, Detour Index, Detour Matrix

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Detour Polynomial

Cite this as:

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

Subject classifications