# Hamiltonicity of cubic Cayley graphs

• Volume: 009, Issue: 4, page 775-787
• ISSN: 1435-9855

top

## Abstract

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

## How to cite

top

Glover, Henry, and Marušič, Dragan. "Hamiltonicity of cubic Cayley graphs." Journal of the European Mathematical Society 009.4 (2007): 775-787. <http://eudml.org/doc/277281>.

@article{Glover2007,
abstract = {Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a $(2,s,3)$-presentation, that is, for groups $G=\langle a,b\mid a^2=1, b^s=1, (ab)^3=1,\dots \rangle$ generated by an involution $a$ and an element $b$ of order $s\ge 3$ such that their product $ab$ has order $3$. More precisely, it is shown that the Cayley graph $X=\operatorname\{Cay\}(G,\lbrace a,b,b^\{-1\}\rbrace )$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.},
author = {Glover, Henry, Marušič, Dragan},
journal = {Journal of the European Mathematical Society},
keywords = {Hamiltonian path and cycle; finite Cayley graph; Hamiltonian path and cycle; finite Cayley graph},
language = {eng},
number = {4},
pages = {775-787},
publisher = {European Mathematical Society Publishing House},
title = {Hamiltonicity of cubic Cayley graphs},
url = {http://eudml.org/doc/277281},
volume = {009},
year = {2007},
}

TY - JOUR
AU - Glover, Henry
AU - Marušič, Dragan
TI - Hamiltonicity of cubic Cayley graphs
JO - Journal of the European Mathematical Society
PY - 2007
PB - European Mathematical Society Publishing House
VL - 009
IS - 4
SP - 775
EP - 787
AB - Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a $(2,s,3)$-presentation, that is, for groups $G=\langle a,b\mid a^2=1, b^s=1, (ab)^3=1,\dots \rangle$ generated by an involution $a$ and an element $b$ of order $s\ge 3$ such that their product $ab$ has order $3$. More precisely, it is shown that the Cayley graph $X=\operatorname{Cay}(G,\lbrace a,b,b^{-1}\rbrace )$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.
LA - eng
KW - Hamiltonian path and cycle; finite Cayley graph; Hamiltonian path and cycle; finite Cayley graph
UR - http://eudml.org/doc/277281
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.