Detour Matrix

 

The detour matrix , sometimes also called the maximum path matrix or maximal topological distances matrix, of a graph is a symmetric matrix whose th entry is the length of the longest path from vertex  to vertex , or  if there is no such path (Harary 1994, p. 203). The most common convention (and that adopted here) is to take .

There is no efficient method for finding the entries of a detour matrix (Harary 1994, p. 203), but the detour matrix can be computed by finding the set of all spanning trees for a given graph, finding their distance matrices, and setting , where the maximum is taken over all spanning trees.

For a graph with vertex count , a detour matrix element of  corresponds to a Hamiltonian path between vertices  and . A graph having a detour matrix whose off-diagonal elements are all equal to  is therefore Hamilton-connected. Similarly, a bipartite graph whose elements  are maximal for all  and  corresponding to different elements of the vertex bipartition is Hamilton-laceable.

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

---

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, p. 44, 1999.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 203, 1994.

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.

Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

اخر الاخبار

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

ملتقى الكوثر الثالث يشهد عرض مشهد حواري بعنوان شريك العمر أم شريك الفكر؟

إقامة مسابقة (مرفأ النور) العلمية للمشاركات في فعاليات ملتقى الكوثر بنسخته الثالثة

ضمن ملتقى الكوثر الثالث.. ورشة تسلط الضوء على بناء الوعي القرآني لدى النساء

شعبة فاطمة بنت أسد (عليها السلام): ملتقى الكوثر منصةً لتحقيق وعي أسري مستند للقرآن الكريم

المزيد

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

نظام غذائي شائع قد يؤدي إلى ارتفاع الكوليسترول الضار

تحذيرات هامة من عواقب تناول "أيبوبروفين" مع أدوية شائعة

علامات مبكرة للإيبولا يمكن الخلط بينها وبين الإنفلونزا

خبراء: الفيروسات مثل هانتا وإيبولا أصبحت أكثر شيوعا وفتكاً

المزيد

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

الليلة.. هلال القمر يلتقي كوكبي الزهرة والمشتري

إيلون ماسك يخسر دعواه القضائية أمام أوبن إيه.آي

مهمة فضائية "أوروبية صينية" لكشف أسرار الرياح الشمسية

انتهاء رحلة "السفينة الموبوءة".. وهذا مصير من بقي على متنها

المزيد

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

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