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.

اخر الاخبار

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

تكريم الجامعات الفائزة ولجنة التحكيم المشاركة في مسابقة النور القرآنية الدولية الجامعية

اختتام فعاليات مسابقة النور القرآنية الدولية الجامعية في جامعة العميد

قسم الصيانة يُنهي تنصيب منظومة الإنذار المبكّر للحرائق في ثانوية نور العباس (عليه السلام) للبنين

في يومها الثاني.. مسابقة النور القرآنية تواصل فعالياتها في جامعة العميد

المزيد

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

أول إرشادات غذائية قائمة على الأدلة لمعالجة الإمساك المزمن

صباح بلا إفطار؟.. صحتك في خطر!

هل يمكن للجلد أن يكشف عن صحتك العقلية؟.. دراسة حديثة تجيب

السر في مطبخك.. 6 أطعمة تمنح عظامك قوة الشباب

المزيد

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

ناسا تكشف: كوكب الأرض أصبح أقل لمعانا خلال العقود الماضية

دراسة: الوقت الذي تستخدم فيه هاتفك قد يفضح حالتك النفسية

الهنغاري لاسلو كراسناهوركاي يفوز بجائزة نوبل للآداب 2025

رسميا.. إعلان الفائز بجائزة نوبل للسلام لعام 2025

المزيد

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

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