Detour Index

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

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  has all off-diagonal matrix elements equal to , the detour index of such a graph is given by .

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  (Amić and Trinajstić 1995; Nikolić et al. 2000, p. 292, corrected), where  is the number of graph vertices.

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

graph	OEIS	sequence
Andrásfai graph	A000000	1, 35, 196, 550, 1183, 2176, 3610, 5566, 8125, ...
antiprism graph	A139757	X, X, 75, 196, 405, 726, 1183, 1800, 2601, 3610, ...
Apollonian network	A297027	18, 126, 1575, ...
barbell graph	A226450	X, X, 45, 124, 265, 486, 805, 1240, 1809, ...
black bishop graph	A000000	X, X, X, 194, 936, 2601, 7200, 15376, 32800, ...
book graph	A000000	16, 67, 150, 251, 378, 531, 710, 915, ...
cocktail party graph	A139757	X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ...
complete bipartite graph	A000000	1, 16, 69, 184, 385, 696, 1141, 1744, 2529, 3520, ...
complete graph	A002411	0, 1, 6, 18, 40, 75, 126, 196, 288, 405, 550, ...
complete tripartite graph	A000000	6, 75, 288, 726, 1470, 2601, ...
-crossed prism graph	A000000	X, X, X, 184, 696, 1744, 3520, 6216, 10024, ...
crown graph	A000000	X, X, 63, 184, 385, 696, 1141, 1744, 2529, 3520, ...
cube-connected cycle graph	A296777	X, X, 6348, 126016, 2022480, ...
cycle graph	A000000	X, X, 6, 16, 35, 63, 105, 160, 234, 325, 440, 576, ...
Fibonacci cube graph	A291918	1, 4, 28, 174, 864, 4000, 18241, ...
folded cube graph	A296778	X, 1, 18, 184, 1800, 15136, ...
gear graph	A033430	X, X, 108, 256, 500, 864, 1372, 2048, 2916, 4000, ...
grid graph	A296779	0, 16, 256, 1744, 6912, 21744, ...
grid graph	A296780	0, 184, 8788, ...
halved cube graph	A000000	1, 18, 196, 1800, 15376, ...
Hanoi graph	A000000	6, 252, 8439, ...
helm graph	A181617	X, X, 72, 160, 300, 504, 784, 1152, 1620, 2200, ...
hypercube graph	A288720	1, 16, 184, 1744, 15136, ...
Keller graph	A000000	X, 1800, 127008, 8323200, ...
king graph	A288959	X, 18, 288, 1800, 7200, 22050, ...
knight graph	A296781	X, X, 1532, 6840, 21744, ...
ladder graph	A000000	1, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ...
Menger sponge graph	A000000	2864, ...
Möbius ladder	A000000	X, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ...
Mycielski graph	A000000	0, 1, 35, 550, 5566, 49726, 419710, 3447550, ...
odd graph	A000000	0, 6, 390, 20230, 984375, 49092351, 2523571050, ...
pan graph	A000000	X, X, 13, 28, 54, 90, 142, 208, 295, 400, 531, 684, ...
path graph	A000292	0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, ...
permutation star graph	A296782	0, 1, 63, 6216, ...
prism graph	A000000	X, X, 75, 184, 405, 696, 1183, 1744, 2601, 3520, 4851, ...
queen graph	A288959	X, 18, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
rook complement graph	A288959	0, X, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
rook graph	A288959	0, 16, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
Sierpiński carpet graph	A000000	160, 123080, ...
Sierpiński sieve graph	A296783	6, 69, 1404, 34485, ...
Sierpiński tetrahedron graph	A000000	...
star graph	A000290	X, X, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, ...
sun graph	A000000	X, X, 69, 180, 375, 678, 1113, 1704, 2475, 3450, ...
sunlet graph	A000000	X, X, 39, 92, 185, 318, 511, 760, 1089, 1490, 1991, ...
tetrahedral graph	A000000	X, X, X, X, X, 18, 405, 3610, 20230, 84700, 289338, ...
torus grid graph	A296784	X, X, 288, 1744, 7200, 21744, 56448, ...
transposition graph	A296785	0, 1, 69, 6216, ...
triangular graph	A000000	X, X, 6, 75, 405, 1470, 4200, 10206, 22050, ...
triangular grid graph	A288719	6, 69, 399, 1467, 4197, 10203, 22047, ...
web graph	A000000	X, X, 189, 452, 970, 1653, 2779, 4080, 6048, 8165, ...
wheel graph	A002411	X, X, X, 18, 40, 75, 126, 196, 288, 405, 550, 726, ...
white bishop graph	A000000	X, X, X, 194, 726, 2601, 6348, 15376, 30420, ...

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

graph	detour index
Andrásfai graph	{35 for n=2; 1/2(3n-1)(3n-2)^2 otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline39.svg" style="height:72px; width:344px" />
antiprism graph
barbell graph
black bishop graph	{28 for n=3; 194 for n=4; 1/(128)[2n^2-3-(-1)^n]^2[2n^2+1-(-1)^n] otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline43.svg" style="height:110px; width:554px" />
book graph	{16 for n=1; 67 for n=2; 13n^2+10n+3 otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline44.svg" style="height:104px; width:274px" />
cocktail party graph	{16 for n=2; n(2n-1)^2 otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline46.svg" style="height:68px; width:240px" />
complete bipartite graph
complete graph
complete tripartite graph
-crossed prism graph
crown graph	{63 for n=3; n(4n^2-5n+2) otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline55.svg" style="height:72px; width:295px" />
cycle graph
gear graph
grid graph	{1/4n^2(2n^4-5n^2+4) for n even; 1/2(n-1)^3(n+1)^3 for n odd" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline60.svg" style="height:76px; width:337px" />
grid graph	{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" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline62.svg" style="height:78px; width:361px" />
halved cube graph
helm graph
hypercube graph
Keller graph
king graph
ladder graph
Möbius ladder
Mycielski graph	{0 for n=1; 35 for n=3; 1/2(3·2^(n-2)-2)^2(3·2^(n-2)-1) otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline75.svg" style="height:110px; width:430px" />
odd graph	{390 for n=3; 1/2[(2n-1; n-1)-1]^2(2n-1; n-1) otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline76.svg" style="height:94px; width:426px" />
pan graph
path graph
prism graph
queen graph
rook complement graph	{undefined for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline85.svg" style="height:72px; width:345px" />
rook graph	{16 for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline87.svg" style="height:72px; width:345px" />
Sierpiński tetrahedron graph
star graph
sun graph
sunlet graph
tetrahedral graph
torus grid graph	{1/4n^2(2n^4-5n^2+4) for n even; 1/2n^2(n^2-1)^2 for n odd" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline96.svg" style="height:78px; width:337px" />
transposition graph	{1 for n=1; 1/4n![n!(2n!-5)+5] otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline97.svg" style="height:72px; width:382px" />
triangular graph
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" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline99.svg" style="height:180px; width:461px" />
web graph
wheel graph
white bishop graph	{16 for n=3; 194 for n=4; 1/(128)[2n^2+(-1)^n-5]^2[2n^2+(-1)^n-1] otherwise" src="https://mathworld.wolfram.com/images/equations/DetourIndex/Inline104.svg" style="height:110px; width:554px" />

---

REFERENCES

Amić, D. and Trinajstić, N. "On the Detour Matrix." Croat. Chem. Acta 68, 53-62, 1995.

Devillers, J. and A. T. Balaban (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, and A139757 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الفكرية يطلق باقة من النشاطات الرقمية الخاصة بشهر المحرم

العتبة العباسية المقدسة تختتم السلسلة الأولى لمشروع المحاضرات القرآنية العاشورائية في بابل

العتبة العباسية المقدسة تسلّم راية العزاء إلى تجمّع مواكب محافظة الديوانية

قسم الشؤون الفكرية يواصل إقامة المجالس الحسينية ضمن سلسلة (بيوت النعيم)

المزيد

الآخبار الصحية

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

الآخبار التكنلوجية

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength