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.

اخر الاخبار

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

المجمَع العلمي يقيم مسابقة الكوثر الخاصة بترتيل القرآن الكريم في كربلاء

قسم الشؤون الفكرية والثقافية يُصدر العدد الثالث والعشرين من مجلّة (أوراق معرفية)

قسم التربية والتعليم يُطلق الموسم التدريبيّ الصيفيّ لملاكات مجموعة العميد التربوية

المجمَع العلمي يُطلق المرحلة الثالثة من مشروع أمير القرّاء الوطني

المزيد

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

اختراق علمي.. دواء يؤخر ظهور السكري من النوع الأول لسنوات

هذا ما يحدث لجسمك إن أهملت نظافة فراشك

لماذا تعتبر النساء أكثر عرضة للإصابة بألزهايمر من الرجال؟

لماذا يحذر الخبراء من الإفراط في تناول الفراولة؟

المزيد

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

السيارات الكهربائية أنظف بنسبة 73% من سيارات الوقود

سيارة لوسِد الكهربائية تدخل "غينيس" بأطول مدى في العالم

نظرية جديدة تنسف كل ما نعرفه عن تشكل أول قارة في الأرض

منذ 37 ألف عام.. دراسة تكشف "أقدم أمراض" أصابت البشر

المزيد

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

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