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.

اخر الاخبار

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

قسم الشؤون الفكرية يشارك في تجهيز الهدايا للمشاركات في حفل تخرج بنات الكفيل

جمعية العميد تشارك في تقديم ندوة علمية في جامعة كربلاء حول المرجعية الدينية وصناعة الوعي

جامعة الكفيل تنظّم ورشة عن الإعجاز العلمي في القرآن الكريم

قسم الشؤون الطبية يجهز فرقًا صحية متخصصة استعدادًا لحفل تخرج طالبات الجامعات

المزيد

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

العين تتحدث قبل القلب.. اكتشاف مذهل في الطب الوقائي

دراسة تكشف فوائد صحية لمشاهدة الأعمال الفنية الأصلية

لن ترمِ قشور البصل بعد اليوم.. تعرف على فوائدها الخفية !

مكملات المغنيسيوم والنوم.. كم المدة التي تحتاج لتلاحظ الفرق؟

المزيد

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

"أزمة صامتة" تقتل على الطرق.. تعادل القيادة تحت تأثير الخمر

لغز عمره ربع قرن.. اكتشاف يغير فهم العلماء لتضاريس المريخ

الشيخوخة المبكرة للدماغ.. دراسة تكشف الرابط

حين تختفي أشعة الشمس.. سر الحفاظ على فيتامين "د"

المزيد

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

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