Nonhamiltonian Vertex-Transitive Graph

Lovász (1970) conjectured that every connected vertex-transitive graph is traceable (Gould, p. 33). This conjecture was subsequently verified for several special orders and classes. Furthermore, with a few notable exceptions, such graphs were also shown to be Hamiltonian. Babai proved the conjecture for graphs with prime order  (Bondy and Murty 1976, Lipman 1985, Gould).

Alspach (1979) showed that every connected vertex-transitive graph of order  except the Petersen graph is Hamiltonian. Marušič (1982) showed that every connected vertex-transitive graph of order , , , and  is Hamiltonian, while Marušič and Parsons (1983) showed that connected vertex-transitive graphs of order  and  are traceable (Gould, p. 33).

Thomassen (1991) conjectured that there are only a finite number of connected nonhamiltonian vertex-transitive graphs, while Babai (1979, 1996) conjectured that there are infinitely many.

There are currently only five known connected nonhamiltonian vertex-transitive graphs, namely the path graph , the Petersen graph , the Coxeter graph , and the triangle-replaced Petersen and Coxeter graphs (the first of these being the cubic vertex-transitive graph Ct66). It is conjectured that all other connected vertex-transitive graphs are Hamiltonian (Godsil and Royle 2001, p. 45).

A slightly weaker conjecture is that all Cayley graphs are Hamiltonian (Royle). Conversely, all Cayley graphs are vertex-transitive.

---

REFERENCES

Babai, L. Problem 17 in "Unsolved Problems." In Summer Research Workshop in Algebraic Combinatorics. Simon Fraser University, Jul. 1979.

Babai, L. "Automorphism Groups, Isomorphism, Reconstruction." Ch. 27 in Handbook of Combinatorics, 2 vols. (Ed. R. L. Graham, M. Grötschel, M.; and L. Lovász). Cambridge, MA: MIT Press, pp. 1447-1540, 1996.

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, 1976.

Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.

Godsil, C. and Royle, G. "Hamilton Paths and Cycles." C§3.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.

Gould, R. J. "Updating the Hamiltonian Problem--A Survey." n.d. http://www.mathcs.emory.edu/~rg/updating.pdf.Kutnar, K. and Marušič, D. "Hamilton Cycles and Paths in Vertex-Transitive Graphs-Current Directions." Disc. Math. 309, 5491-5500, 2009.

Lipman, M. "Hamiltonian Cycles and Paths in Vertex-Transitive Graphs with Abelian and Nilpotent Groups." Disc. Math. 54, 15-21, 1985.

Lovász, L. Problem 11 in "Combinatorial Structures and Their Applications." In Proc. Calgary Internat. Conf. Calgary, Alberta, 1969. 

London: Gordon and Breach, pp. 243-246, 1970.

Marušič, D. "Hamiltonian Paths in Vertex-Symmetric Graphs of Order ." Disc. Math. 42, 227-242, 1982.

Marušič, D. and Parsons, T. D. "Hamiltonian Paths in Vertex-Symmetric Graphs of Order ." Disc. Math. 43, 91-96, 1983.

Royle, G. "Transitive Graphs." http://school.maths.uwa.edu.au/~gordon/trans/.Thomassen, C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface." Trans. Amer. Math. Soc. 323 605-635, 1991.

اخر الاخبار

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

جولة تفقدية لمتابعة خطة تنظيم مداخل المعزّين المشاركين في عزاء ركضة طويريج

لتعزيز التعاون الأكاديمي والبحثي.. جامعة الكفيل توقع اتفاقيتي توأمة مع جامعتين عراقيتين

المجمَع العلميّ يواصل إقامة مجلسه العزائي بذكرى شهادة الإمام الحسين (عليه السلام) في النجف الأشرف

قسم حفظ النظام يواصل تنفيذ خطته لتنظيم سير المواكب والزائرين في شهر المحرم

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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