TOPICS
Search

Detour Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The detour index omega(G) of a graph G is a graph invariant defined as half the sum of all off-diagonal matrix elements of the detour matrix of G.

Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).

Precomputed detour indices for many named graphs are available in the Wolfram Language as GraphData[graph, "DetourIndex"].

Since a Hamilton-connected graph with vertex count n has all off-diagonal matrix elements equal to n-1, the detour index of such a graph is given by n(n-1)^2/2.

DetourIndex

The detour index is not particularly good at distinguishing graphs. The figures above illustrate a number of small nonisomorphic graphs sharing the same detour index omega (Amić and Trinajstić 1995; Nikolić et al. 2000, p. 292, corrected), where n is the number of graph vertices.

The following table gives values for various common classes of graphs.

graphOEISsequence
Andrásfai graphA3869061, 35, 196, 550, 1183, 2176, 3610, 5566, 8125, ...
antiprism graphA139757X, X, 75, 196, 405, 726, 1183, 1800, 2601, 3610, ...
Apollonian networkA29702718, 126, 1575, ...
barbell graphA226450X, X, 45, 124, 265, 486, 805, 1240, 1809, ...
black bishop graph BB_(n,n)A387645X, X, X, 194, 936, 2601, 7200, 15376, 32800, ...
book graph S_(n+1) square P_2A38765916, 67, 150, 251, 378, 531, 710, 915, ...
cocktail party graph K_(n×2)A139757X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ...
complete bipartite graph K_(n,n)1, 16, 69, 184, 385, 696, 1141, 1744, 2529, 3520, ...
complete graph K_nA0024110, 1, 6, 18, 40, 75, 126, 196, 288, 405, 550, ...
complete tripartite graph K_(n,n,n)6, 75, 288, 726, 1470, 2601, ...
2n-crossed prism graphX, X, X, 184, 696, 1744, 3520, 6216, 10024, ...
crown graphX, X, 63, 184, 385, 696, 1141, 1744, 2529, 3520, ...
cube-connected cycle graphA296777X, X, 6348, 126016, 2022480, ...
cycle graph C_nX, X, 6, 16, 35, 63, 105, 160, 234, 325, 440, 576, ...
Fibonacci cube graphA2919181, 4, 28, 174, 864, 4000, 18241, ...
folded cube graphA296778X, 1, 18, 184, 1800, 15136, ...
gear graphA033430X, X, 108, 256, 500, 864, 1372, 2048, 2916, 4000, ...
grid graph P_n×P_nA2967790, 16, 256, 1744, 6912, 21744, ...
grid graph P_n×P_n×P_nA2967800, 184, 8788, ...
halved cube graph1, 18, 196, 1800, 15376, ...
Hanoi graph6, 252, 8439, ...
helm graphA181617X, X, 72, 160, 300, 504, 784, 1152, 1620, 2200, ...
hypercube graph Q_nA2887201, 16, 184, 1744, 15136, ...
Keller graph G_nX, 1800, 127008, 8323200, ...
king graph Ki_(n,n)A288959X, 18, 288, 1800, 7200, 22050, ...
knight graph Kn_(n,n)A296781X, X, 1532, 6840, 21744, ...
ladder graph P_2 square P_n1, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ...
Menger sponge graph2864, ...
Möbius ladder M_nX, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ...
Mycielski graph M_n0, 1, 35, 550, 5566, 49726, 419710, 3447550, ...
odd graph O_n0, 6, 390, 20230, 984375, 49092351, 2523571050, ...
pan graphX, X, 13, 28, 54, 90, 142, 208, 295, 400, 531, 684, ...
path graph P_nA0002920, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, ...
permutation star graph Q_(n,n)A2967820, 1, 63, 6216, ...
prism graph Y_nX, X, 75, 184, 405, 696, 1183, 1744, 2601, 3520, 4851, ...
queen graphA288959X, 18, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
rook complement graph K_n square K_n^_A2889590, X, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
rook graph K_n square K_nA2889590, 16, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
Sierpiński carpet graph160, 123080, ...
Sierpiński gasket graphA2967836, 69, 1404, 34485, ...
Sierpiński tetrahedron graph...
star graph S_nA000290X, X, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, ...
sun graphX, X, 69, 180, 375, 678, 1113, 1704, 2475, 3450, ...
sunlet graph C_n circledot K_1X, X, 39, 92, 185, 318, 511, 760, 1089, 1490, 1991, ...
tetrahedral Johnson graphX, X, X, X, X, 18, 405, 3610, 20230, 84700, 289338, ...
torus grid graph C_n square C_nA296784X, X, 288, 1744, 7200, 21744, 56448, ...
transposition graph G_nA2967850, 1, 69, 6216, ...
triangular graphX, X, 6, 75, 405, 1470, 4200, 10206, 22050, ...
triangular grid graph T_nA2887196, 69, 399, 1467, 4197, 10203, 22047, ...
web graphX, X, 189, 452, 970, 1653, 2779, 4080, 6048, 8165, ...
wheel graph W_nA002411X, X, X, 18, 40, 75, 126, 196, 288, 405, 550, 726, ...
white bishop graph WB_(n,n)X, X, X, 194, 726, 2601, 6348, 15376, 30420, ...

Closed forms for some of these classes of graphs are summarized in the following table.

graphdetour index
Andrásfai graph{35 for n=2; 1/2(3n-1)(3n-2)^2 otherwise
antiprism graphn(2n-1)^2
barbell graphn(3n^2-5n+3)
black bishop graph BB_(n,n){28 for n=3; 194 for n=4; 1/(128)[2n^2-3-(-1)^n]^2[2n^2+1-(-1)^n] otherwise
book graph{16 for n=1; 67 for n=2; 13n^2+10n+3 otherwise
cocktail party graph K_(n×2){16 for n=2; n(2n-1)^2 otherwise
complete bipartite graph K_(n,n)n(4n^2-5n+2)
complete graph K_n1/2(n-1)^2n
complete tripartite graph K_(n,n,n)3/2n(3n-1)^2
2n-crossed prism graphn(4n^2-5n+2)
crown graph{63 for n=3; n(4n^2-5n+2) otherwise
cycle graph C_n1/(16)n[(-1)^(n+1)+6n^2-8n+1]
gear graph4n^3
grid graph P_n square P_n{1/4n^2(2n^4-5n^2+4) for n even; 1/2(n-1)^3(n+1)^3 for n odd
grid graph P_n square P_n square P_n{1/2n^3(n^6-5/2n^3+2) for n even; 1/2(n-1)^3(n^2+n+1)^3 for n odd
halved cube graph2^(n-4)(2^n-2)^2
helm graph2(n^3+7n^2+16n+11)
hypercube graph Q_n2^(n-2)(2^(2n+1)-5·2^n+4)
Keller graph G_n2^(2n-1)(4^n-1)^2
king graph Ki_(n,n)1/2(n-1)^2n^2(n+1)^2
ladder graph P_2 square P_n1/4[16n^3-26n^2+28n-15-(-1)^n]
Möbius ladder M_n1/2n[(-1)^n(n-1)+(8n^2-9n+3)]
Mycielski graph{0 for n=1; 35 for n=3; 1/2(3·2^(n-2)-2)^2(3·2^(n-2)-1) otherwise
odd graph{390 for n=3; 1/2[(2n-1; n-1)-1]^2(2n-1; n-1) otherwise
pan graph1/(16)[6n^3+4n^2+n+(-1)^(n+1)(n+2)+2]
path graph P_n1/6(n-1)n(n+1)
prism graph Y_n1/2n[(-1)^(n+1)(n-1)+(8n^2-9n+3)]
queen graph Q_(n,n)1/2(n-1)^2n^2(n+1)^2
rook complement graph K_n square K_n^_{undefined for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise
rook graph K_n square K_n{16 for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise
Sierpiński tetrahedron graph(2^(2n-1)+1)^2(4^(n-1)+1)
star graph S_n(n-1)^2
sun graphn(4n^2-6n+5)
sunlet graph C_n circledot K_11/4n[(-1)^(n-1)+3(2n^2-1)]
tetrahedral Johnson graph1/2(n; 3)[(n; 3)-1]^2
torus grid graph C_n square C_n{1/4n^2(2n^4-5n^2+4) for n even; 1/2n^2(n^2-1)^2 for n odd
transposition graph{1 for n=1; 1/4n![n!(2n!-5)+5] otherwise
triangular graph1/(16)(n-1)(n^2-n-2)^2
triangular grid graph{0 for n=0; 6 for n=1; 69 for n=2; 399 for n=3; 1/(16)n^2(n+1)(n+2)(n+3)^2-3 otherwise
web graph1/8n[72n^2-61n+22+(-1)^n(10-9n)]
wheel graph W_n1/2(n-1)^2n
white bishop graph WB_(n,n){16 for n=3; 194 for n=4; 1/(128)[2n^2+(-1)^n-5]^2[2n^2+(-1)^n-1] otherwise

See also

Detour Matrix, Detour Polynomial

Explore with Wolfram|Alpha

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, pp. 82-83, 2000.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.Sloane, N. J. A. Sequences A000290/M3556, A000292/M3382, A002411/M4116, A139757, A386906, A387645, and A387659 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Detour Index

Cite this as:

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

Subject classifications