Hamiltonicity of Cubic Cayley Graphs

Details Hamiltonicity of Cubic Cayley Graphs Hamiltonicity of Cubic Cayley Graphs

2005-08-31

arxiv.org/abs/math/0508647v1

Mathematics

Combinatorics

13 pages, 6 figures

Scientific paper

Following a problem posed by Lov\'asz in 1969, it is believed that every connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from groups having a $(2,s,3)$-presentation, that is, for groups $G=\la a,b| a^2=1, b^s=1, (ab)^3=1, etc. \ra$ generated by an involution $a$ and an element $b$ of order $s\geq3$ such that their product $ab$ has order 3. More precisely, it is shown that the Cayley graph $X=Cay(G,\{a,b,b^{-1}\})$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.

Affiliated with

Also associated with

No associations

Rating

Hamiltonicity of Cubic Cayley Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hamiltonicity of Cubic Cayley Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamiltonicity of Cubic Cayley Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-116873