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.

اخر الاخبار

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

قسم الشؤون الفكرية يقيم أمسيات قرآنية في غانا ونيجيريا ضمن برنامج سفرة الكفيل الرمضانية

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

المجمع العلمي يختتم مسابقة رحيق الولاء ضمن فعاليات ملتقى النورين الخامس في بابل

الحلقة 27 من جائزة العميد القرآنية تشهد مشاركة 5 قرّاء من فئة الكبار ضمن المرحلة النهائية

المزيد

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

كوب قبل النوم.. مشروب طبيعي يحارب الأرق

دون أدوية.. طريقة طبيعية لخفض ضغط الدم بفعالية مذهلة

المعكرونة ليست عدوك.. كيف تصبح جزءا من وجبة صحية متوازنة؟

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

المزيد

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

علماء روس يخططون لبناء منشأة للكشف عن المادة المظلمة

ثاني أكسيد الكربون ليس تهديدا للمناخ فقط.. بل لصحة الإنسان أيضا!

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

المزيد

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

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