# Hamiltonicity of cubic Cayley graphs

Journal of the European Mathematical Society (2007)

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

## Access Full Article

top## Abstract

top## How to cite

topGlover, 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 ?

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