Detour Polynomial

The detour polynomial of a graph  is the characteristic polynomial of the detour matrix of .

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

Since a Hamilton-connected graph with vertex count  has all off-diagonal matrix elements equal to , the detour polynomial of such a graph is given by .

The following table summarizes detour polynomials for some common classes of graphs. Here,  is a Chebyshev polynomial of the first kind and  is a Chebyshev polynomial of the second kind.

graph	detour polynomial
Andrásfai graph	{-(-14+x)(11+7x+x^2)^2 for n=2; (-1)^(n-1)(-(3n-2)^2+x)(3n-2+x)^(3n-2) otherwise" src="https://mathworld.wolfram.com/images/equations/DetourPolynomial/Inline8.svg" style="height:78px; width:561px" />
antiprism graph
barbell graph
book graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
crossed prism graph
crown graph for
gear graph
halved cube graph
helm graph
hypercube graph
Keller graph
king graph
Möbius ladder	{(2n-2+x)^(2n-2)(3n-2+x)(-(2-5n+4n^2)+x) for n odd; (-(2n-1)^2+x)(2n-1+x)^(2n-1) for n even" src="https://mathworld.wolfram.com/images/equations/DetourPolynomial/Inline35.svg" style="height:76px; width:664px" />
Mycielski graph	{x for n=1; (x-14)(x^2+7x+11)^2 for n=3; (x+3·2^(n-2)-2)^(3·2^(n-2))[x-(3·2^(n-2)-2)^2] otherwise" src="https://mathworld.wolfram.com/images/equations/DetourPolynomial/Inline37.svg" style="height:122px; width:552px" />
odd graph	{(x-78)(x+7)^4(x+10)^5 for n=3; [x-((2n-1; n)-1)^2][x+(2n-1; n)-1]^((2n-1; n)-1) otherwise" src="https://mathworld.wolfram.com/images/equations/DetourPolynomial/Inline39.svg" style="height:104px; width:640px" />
path graph
prism graph	{(x-(2n-1)^2)(2n-1+x)^(2n-1) for n odd; (x-(2-5n+4n^2))(2n-2+x)^(2n-2)(3n-2+x) for n even" src="https://mathworld.wolfram.com/images/equations/DetourPolynomial/Inline43.svg" style="height:76px; width:650px" />
Sierpiński tetrahedron graph
star graph
wheel graph

The following table summarizes the recurrence relations for detour polynomials for some simple classes of graphs.

graph	order	recurrence
path graph	5

---

REFERENCES

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.

اخر الاخبار

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

قسم شؤون المعارف يطلق دورة (صفات الشيعة) لعدد من ملاكات العتبة العباسية المقدسة

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

جامعة الكفيل تكرِّم طلبتها المتميزين من ذوي الاحتياجات الخاصة

فريق طبي في مستشفى الكفيل يجري عملية ناجحة لطفل يعاني من تشوّه ولاديّ بالنخاع الشوكي

المزيد

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

خصوصا مع تقدم السن.. 6 سلوكيات يومية قد تدمّر صحتك

فاكهة خضراء.. علاج طبيعي فعّال للإمساك واضطرابات الهضم

روسيا تبدأ أولى التجارب السريرية للقاح واعد ضد السرطان

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

المزيد

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

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

روسيا تخطط لإقامة محطة نووية في القمر خلال العقد المقبل

كيف قاد إيلون ماسك حملة "غروك" لاختراق عرش الذكاء الاصطناعي

ألتمان: الذكاء الاصطناعي سيتجاوز البشر في 2026 !

المزيد

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

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