TOPICS
Search

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.

graphdetour polynomial
Andrásfai graph{-(-14+x)(11+7x+x^2)^2 for n=2; (-1)^(n-1)(-(3n-2)^2+x)(3n-2+x)^(3n-2) otherwise
antiprism graph(2n-1+x)^(2n-1)(x-(2n-1)^2)
barbell graph(n-1+x)^(2(n-2))(-(n-1)(4-7n+4n^2)-(4-6n+3n^2)x+x^2)((n-1)n+n^2x+x^2)
book graph S_(n+1) square P_2(4+x)^(n-1)(8+x)^(n-1)(-6(4+7n)-(-5+13n)x+x^2)(2(n+6)+(n+7)x+x^2)
cocktail party graph K_(n×2)(-(2n-1)^2+x)(2n-1+x)^(2n-1)
complete bipartite graph K_(n,n)(2n-2+x)^(2n-2)(3n-2+x)[x-(2-5n+4n^2)]
complete graph K_n((n-1)^2-x)(1-x-n)^(n-1))
complete tripartite graph K_(n,n)(3n+x-1)^(3n-1)[x-(3n-1)^2]
crossed prism graph(-2+5n-4n^2+x)(2n-2+x)^(2n-2)(3n-2+x)
crown graph for n>3(x-(2-5n+4n^2))(2(n-1)+x)^(2(n-1))(3n-2+x)
gear graph-(2(n-1)+x)^(n-1)(2n+x)^n(-n(1-7n+8n^2)-2(1-2n+2n^2)x+x^2)
halved cube graph 1/2Q_n(-(-1+2^(n-1))^2+x)(x-1+2^(n-1))^((-1+2^(n-1)))
helm graph-(2n+2(n+1)x+x^2)^(n-1)(-n^2(1+3n)-n(-1+5n+2n^2)x-2(n-1)(1+n)x^2+x^3)
hypercube graph Q_n[x-(4^n+2-5·2^(n-1))][x+2(2^(n-1)-1)]^(2(2^(n-1)-1))[x+3·2^(n-1)-2]
Keller graph K_n(x-(4^n-1)^2)(4^n-1+x)^(4^n-1)
king graph Ki_(n,n)(x-(n^2-1)^2)(x+n^2-1)^(n^2-1)
Möbius ladder M_n{(2n-2+x)^(2n-2)(3n-2+x)(-(2-5n+4n^2)+x) for n odd; (-(2n-1)^2+x)(2n-1+x)^(2n-1) for n even
Mycielski graph M_n{x for n=1; (x-14)(x^2+7x+11)^2 for n=3; (x+3·2^(n-2)-2)^(3·2^(n-2))[x-(3·2^(n-2)-2)^2] otherwise
odd graph O_n{(x-78)(x+7)^4(x+10)^5 for n=3; [x-((2n-1; n)-1)^2][x+(2n-1; n)-1]^((2n-1; n)-1) otherwise
path graph P_n(x^(n-1))/2[x+xT_(2n)(sqrt(1+1/(2x)))-nU_(n-1)(1+1/x)]
prism graph Y_n{(x-(2n-1)^2)(2n-1+x)^(2n-1) for n odd; (x-(2-5n+4n^2))(2n-2+x)^(2n-2)(3n-2+x) for n even
Sierpiński tetrahedron graph1/(16)(4^n+2)^2(4^n+4)
star graph S_n(2+x)^(n-2)(1-n-(2n-4)x+x^2)
wheel graph W_n(x-(n-1)^2)(n-1+x)^(n-1)

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

graphorderrecurrence
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

References

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. https://mathworld.wolfram.com/DetourPolynomial.html

Subject classifications