Geodesic
Hamiltonicity of cubic Cayley graphs
Journal of the European Mathematical Society, Tome 9 (2007) no. 4, pp. 775-787

Voir la notice de l'article provenant de la source EMS Press

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=〈a,b∣a2=1,bs=1,(ab)3=1,...〉 generated by an involution a and an element b of order s≥3 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 adjacent vertices (and thus necessarily a Hamilton path) when ∣G∣ is congruent to 0 modulo 4.
DOI : 10.4171/jems/96
Classification : 05-XX, 20-XX, 00-XX
Keywords: Hamiltonian path and cycle, finite Cayley graph 
@article{JEMS_2007_9_4_a5,
     author = {Henry H. Glover and Dragan Marusic},
     title = {Hamiltonicity of cubic {Cayley} graphs},
     journal = {Journal of the European Mathematical Society},
     pages = {775--787},
     publisher = {mathdoc},
     volume = {9},
     number = {4},
     year = {2007},
     doi = {10.4171/jems/96},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/jems/96/}
}
TY  - JOUR
AU  - Henry H. Glover
AU  - Dragan Marusic
TI  - Hamiltonicity of cubic Cayley graphs
JO  - Journal of the European Mathematical Society
PY  - 2007
SP  - 775
EP  - 787
VL  - 9
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4171/jems/96/
DO  - 10.4171/jems/96
ID  - JEMS_2007_9_4_a5
ER  - 
%0 Journal Article
%A Henry H. Glover
%A Dragan Marusic
%T Hamiltonicity of cubic Cayley graphs
%J Journal of the European Mathematical Society
%D 2007
%P 775-787
%V 9
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4171/jems/96/
%R 10.4171/jems/96
%F JEMS_2007_9_4_a5
Henry H. Glover; Dragan Marusic. Hamiltonicity of cubic Cayley graphs. Journal of the European Mathematical Society, Tome 9 (2007) no. 4, pp. 775-787. doi: 10.4171/jems/96

Cité par Sources :