0
EN
1
المرجع الالكتروني للمعلوماتية

الرياضيات

تاريخ الرياضيات

الاعداد و نظريتها

تاريخ التحليل

تار يخ الجبر

الهندسة و التبلوجي

الرياضيات في الحضارات المختلفة

العربية

اليونانية

البابلية

الصينية

المايا

المصرية

الهندية

الرياضيات المتقطعة

المنطق

اسس الرياضيات

فلسفة الرياضيات

مواضيع عامة في المنطق

الجبر

الجبر الخطي

الجبر المجرد

الجبر البولياني

مواضيع عامة في الجبر

الضبابية

نظرية المجموعات

نظرية الزمر

نظرية الحلقات والحقول

نظرية الاعداد

نظرية الفئات

حساب المتجهات

المتتاليات-المتسلسلات

المصفوفات و نظريتها

المثلثات

الهندسة

الهندسة المستوية

الهندسة غير المستوية

مواضيع عامة في الهندسة

التفاضل و التكامل

المعادلات التفاضلية و التكاملية

معادلات تفاضلية

معادلات تكاملية

مواضيع عامة في المعادلات

التحليل

التحليل العددي

التحليل العقدي

التحليل الدالي

مواضيع عامة في التحليل

التحليل الحقيقي

التبلوجيا

نظرية الالعاب

الاحتمالات و الاحصاء

نظرية التحكم

بحوث العمليات

نظرية الكم

الشفرات

الرياضيات التطبيقية

نظريات ومبرهنات

علماء الرياضيات

500AD

500-1499

1000to1499

1500to1599

1600to1649

1650to1699

1700to1749

1750to1779

1780to1799

1800to1819

1820to1829

1830to1839

1840to1849

1850to1859

1860to1864

1865to1869

1870to1874

1875to1879

1880to1884

1885to1889

1890to1894

1895to1899

1900to1904

1905to1909

1910to1914

1915to1919

1920to1924

1925to1929

1930to1939

1940to the present

علماء الرياضيات

الرياضيات في العلوم الاخرى

بحوث و اطاريح جامعية

هل تعلم

طرائق التدريس

الرياضيات العامة

نظرية البيان

قم بتسجيل الدخول اولاً لكي يتسنى لك الاعجاب والتعليق.

Detour Index

المؤلف:  Amić, D. and Trinajstić, N

المصدر:  "On the Detour Matrix." Croat. Chem. Acta 68

الجزء والصفحة:  ...

7-4-2022

4388

+

-

20

Detour Index

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.

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 BB_(n,n) A000000 X, X, X, 194, 936, 2601, 7200, 15376, 32800, ...
book graph S_(n+1) square P_2 A000000 16, 67, 150, 251, 378, 531, 710, 915, ...
cocktail party graph K_(n×2) A139757 X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ...
complete bipartite graph K_(n,n) A000000 1, 16, 69, 184, 385, 696, 1141, 1744, 2529, 3520, ...
complete graph K_n A002411 0, 1, 6, 18, 40, 75, 126, 196, 288, 405, 550, ...
complete tripartite graph K_(n,n,n) A000000 6, 75, 288, 726, 1470, 2601, ...
2n-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 C_n 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 P_n×P_n A296779 0, 16, 256, 1744, 6912, 21744, ...
grid graph P_n×P_n×P_n 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 Q_n A288720 1, 16, 184, 1744, 15136, ...
Keller graph G_n A000000 X, 1800, 127008, 8323200, ...
king graph Ki_(n,n) A288959 X, 18, 288, 1800, 7200, 22050, ...
knight graph Kn_(n,n) A296781 X, X, 1532, 6840, 21744, ...
ladder graph P_2 square P_n A000000 1, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ...
Menger sponge graph A000000 2864, ...
Möbius ladder M_n A000000 X, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ...
Mycielski graph M_n A000000 0, 1, 35, 550, 5566, 49726, 419710, 3447550, ...
odd graph O_n 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 P_n A000292 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, ...
permutation star graph Q_(n,n) A296782 0, 1, 63, 6216, ...
prism graph Y_n 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 K_n square K_n^_ A288959 0, X, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
rook graph K_n square K_n 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 S_n 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 C_n circledot K_1 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 C_n square C_n A296784 X, X, 288, 1744, 7200, 21744, 56448, ...
transposition graph G_n A296785 0, 1, 69, 6216, ...
triangular graph A000000 X, X, 6, 75, 405, 1470, 4200, 10206, 22050, ...
triangular grid graph T_n A288719 6, 69, 399, 1467, 4197, 10203, 22047, ...
web graph A000000 X, X, 189, 452, 970, 1653, 2779, 4080, 6048, 8165, ...
wheel graph W_n A002411 X, X, X, 18, 40, 75, 126, 196, 288, 405, 550, 726, ...
white bishop graph WB_(n,n) 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 <span style={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 n(2n-1)^2
barbell graph n(3n^2-5n+3)
black bishop graph BB_(n,n) <span style={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 <span style={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 K_(n×2) <span style={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 K_(n,n) n(4n^2-5n+2)
complete graph K_n 1/2(n-1)^2n
complete tripartite graph K_(n,n,n) 3/2n(3n-1)^2
2n-crossed prism graph n(4n^2-5n+2)
crown graph <span style={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 C_n 1/(16)n[(-1)^(n+1)+6n^2-8n+1]
gear graph 4n^3
grid graph P_n square P_n <span style={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 P_n square P_n square P_n <span style={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 2^(n-4)(2^n-2)^2
helm graph 2(n^3+7n^2+16n+11)
hypercube graph Q_n 2^(n-2)(2^(2n+1)-5·2^n+4)
Keller graph G_n 2^(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_n 1/4[16n^3-26n^2+28n-15-(-1)^n]
Möbius ladder M_n 1/2n[(-1)^n(n-1)+(8n^2-9n+3)]
Mycielski graph <span style={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 <span style={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 1/(16)[6n^3+4n^2+n+(-1)^(n+1)(n+2)+2]
path graph P_n 1/6(n-1)n(n+1)
prism graph Y_n 1/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^_ <span style={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 K_n square K_n <span style={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 (2^(2n-1)+1)^2(4^(n-1)+1)
star graph S_n (n-1)^2
sun graph n(4n^2-6n+5)
sunlet graph C_n circledot K_1 1/4n[(-1)^(n-1)+3(2n^2-1)]
tetrahedral graph 1/2(n; 3)[(n; 3)-1]^2
torus grid graph C_n square C_n <span style={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 <span style={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 1/(16)(n-1)(n^2-n-2)^2
triangular grid graph <span style={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 1/8n[72n^2-61n+22+(-1)^n(10-9n)]
wheel graph W_n 1/2(n-1)^2n
white bishop graph WB_(n,n) <span style={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."

الاكثر قراءة في نظرية البيان

اخر الاخبار

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

مضيف العتبة العباسية المقدسة يقيم مجلس عزائه السنوي لإحياء ذكرى عاشوراء

قسم الشؤون الفكرية ينجز المراحل النهائية لمشروع الأرشفة الرقمية في كلية العلوم بجامعة البصرة

بعد إدامتها.. قسم صناعة الشبابيك ينهي تركيب الأعمدة الوسطية لأبواب حرم مرقد أبي الفضل العباس (عليه السلام)

في اليوم السابع من المحرم.. العتبة العباسية المقدسة تستذكر سيرة أبي الفضل العباس (عليه السلام)

المزيد
الآخبار الصحية

كيف يختبئ فيروس "إيبولا" داخل الجسم؟..دراسة تكشف السر الخطير

أسرار البطيخ الأحمر.. فوائد صحية تتجاوز مجرد الترطيب

ليس عدد الساعات فقط.. توقيت النوم يحمي قلبك ومزاجك

القهوة قبل الإفطار أم بعده.. أيهما أفضل لصحتك؟

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

الإمارات تطلق "زايد".. متحدث رقمي مدعوم بالذكاء الاصطناعي

لحفظ أسرار البشرية.. بدء بناء "الصندوق الأسود" للأرض

نماذج الذكاء الاصطناعي تفشل في تجاوز خبراء الرياضيات في اختبار بحثي معقد

ابتكار أول كاشف كمي للمادة المظلمة

المزيد

اشترك بقناتنا على التلجرام ليصلك كل ما هو جديد

EN