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).

For a complete multipartite graph with positive part sizes s_1,...,s_r, r>=2, let d_(ij) be the detour distance between distinct vertices in parts i and j. Define the r×r matrix Q by Q_(ii)=(s_i-1)d_(ii) and Q_(ij)=s_jd_(ij) for i!=j. The subspace of vectors supported in part i with coordinate sum zero has eigenvalue -d_(ii) and dimension s_i-1. The remaining invariant subspace consists of vectors constant on each part, so

p_G(x)=product_(i=1)^r(x+d_(ii))^(s_i-1)det(xI-Q).
(1)

The formal value d_(ii) is immaterial for a singleton part.

For the complete bipartite graph K_(m,n), put a=2min(n,m-1), b=2min(m,n-1), and c=2min(m,n)-1. This specializes to

p_(K_(m,n))(x)=(x+a)^(m-1)(x+b)^(n-1)[(x-a(m-1))(x-b(n-1))-mnc^2].
(2)

These formulas and the tables use the monic polynomial convention p_G(x)=det(xI-Delta).

For a strongly Hamiltonian-laceable graph with two equal bipartition classes and even vertex count N>=2, write its detour polynomial as

b_N(x)=[x-(2N^2-5N+4)/2](x+(3N)/2-2)(x+N-2)^(N-2).
(3)

The constant vector, the vector taking opposite signs on the two bipartition classes, and the vectors whose coordinates sum to zero within each class give the three factors. The Bruhat graph and permutation star graph use N=n! for n>=4 (Hsieh et al. 2000, Araki and Kikuchi 2007). The transposition graph contains the permutation star graph as a spanning subgraph, so the same longest path bounds apply for n>=4. For n=2 and n=3, the transposition graphs are K_2 and K_(3,3), respectively, and also use b_(n!)(x). For the folded cube graph, put v=2^(n-1) with n>=2. It is a Hamilton-connected graph for odd n and a strongly Hamiltonian-laceable graph for even n (Hsieh and Kuo 2007).

For the cycle graph and sunlet graph rows with n>=3, put lambda_j=sum_(k=1)^(n-1)max(k,n-k)cos(2pijk/n) for j=0,...,n-1. These are the eigenvalues of the circulant matrix Delta(C_n).

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; (-(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, n>=3(4+x)^(n-1)(8+x)^(n-1)(-6(4+7n)-(-5+13n)x+x^2)(2(n+6)+(n+7)x+x^2)
Bruhat graph B_n{x for n=1; x^2-1 for n=2; (x-21)(x+2)^2(x+5)(x+6)^2 for n=3; b_(n!)(x) for n>=4
cocktail party graph K_(n×2), n>=3(-(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(x-(n-1)^2)(x+n-1)^(n-1)
complete tripartite graph K_(n,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)
cycle graph C_n, n>=3product_(j=0)^(n-1)(x-lambda_j)
folded cube graph{[x-(v-1)^2](x+v-1)^(v-1) for n odd; b_v(x) for n even
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, n>=1[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, n>=2(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)-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)]
permutation star graph PS_n{x for n=1; x^2-1 for n=2; (x-21)(x+2)^2(x+5)(x+6)^2 for n=3; b_(n!)(x) for n>=4
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
star graph S_n(2+x)^(n-2)(1-n-(2n-4)x+x^2)
sunlet graph C_n circledot K_1, n>=3[x^2-(2lambda_0+2n-2)x-2lambda_0-n^2]product_(j=1)^(n-1)[x^2+(2-2lambda_j)x-2lambda_j]
transposition graph G_n{x for n=1; b_(n!)(x) for n>=2
wheel graph W_n(x-(n-1)^2)(n-1+x)^(n-1)

For the zero-dimensional hypercube graph and the singleton star graph, p_G(x)=x. The 2-cocktail party graph is C_4 and has polynomial (x-8)(x+2)^2(x+4).

The following table identifies -p_G(0), the negative of the constant coefficient.

graphdomainOEIS for -p_G(0)
antiprism graphn>=3A008788
cocktail party graphn>=3A008788
complete graphn>=1A008788
complete tripartite graph K_(n,n,n)n>=1A008788
path graphn>=1A001787
star graphn>=1A001787
wheel graphn>=4A008788

The following table summarizes the recurrence relations for detour polynomials for some simple classes of graphs. The path recurrence applies for n>=6.

graphorderrecurrence
path graph P_n5p_n(x)=x^5p_(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

Araki, T. and Kikuchi, Y. "Hamiltonian Laceability of Bubble-Sort Graphs with Edge Faults." Inform. Sci. 177, 2679-2691, 2007. https://doi.org/10.1016/j.ins.2007.01.017.Hsieh, S.-Y.; Chen, G.-H.; and Ho, C.-W. "Hamiltonian-Laceability of Star Graphs." Networks 36, 225-232, 2000. https://doi.org/10.1002/1097-0037(200012)36:4%3C225::AID-NET3%3E3.0.CO;2-G.Hsieh, S.-Y. and Kuo, C.-N. "Hamiltonian-Connectivity and Strongly Hamiltonian-Laceability of Folded Hypercubes." Comput. Math. Appl. 53, 1040-1044, 2007. https://doi.org/10.1016/j.camwa.2006.10.033.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.Sloane, N. J. A. Sequences A001787 and A008788 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Detour Polynomial

Cite this as:

Weisstein, Eric W. "Detour Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DetourPolynomial.html

Subject classifications