Hamiltonian cycles in Cayley graphs whose order has few prime factors

Kutnar, Klavdija (author), Marušič, Dragan (author), Morris, D. W. (author), Morris, Joy (author), Šparl, Primož (author)

We prove that if Cay$(G; S)$ is a connected Cayley graph with $n$ vertices, and the prime factorization of $n$ is very small, then Cay$(G; S)$ has a hamiltonian cycle. More precisely, if $p$, $q$, and $r$ are distinct primes, then $n$ can be of the form kp with $24 \ne k < 32$, or of the form $kpq$ with $k \le 5$, or of the form $pqr$, or of the form $kp^2$ with $k \le 4$, or of the form $kp^3$ with $k \le 2$.

• Language: English
• Keywords: graph theory, Cayley graphs, hamiltonian cycles
• Work type: Not categorized
• Typology: 1.01 - Original Scientific Article
• Organization: PEF - Faculty of Education
• Year: 2012
• Number of pages: Str. 27-71
• Numbering: Vol. 5, no. 1
• PID: 20.500.12556/RUL-84785
• UDC: 519.17
• ISSN on article: 1855-3966
• COBISS.SI-ID: 1024371028
• Publication date in RUL: 09.09.2016

KUTNAR, Klavdija, MARUŠIČ, Dragan, MORRIS, D. W., MORRIS, Joy and ŠPARL, Primož, 2012, Hamiltonian cycles in Cayley graphs whose order has few prime factors. Ars mathematica contemporanea [online]. 2012. Vol. 5, no. 1, p. 27–71. [Accessed 8 April 2025]. Retrieved from: http://amc.imfm.si/index.php/amc/article/view/177

Record is a part of a journal

• Title: Ars mathematica contemporanea
• Publisher: Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
• ISSN: 1855-3966
• COBISS.SI-ID: 239049984

Secondary language

• Language: Slovenian
• Keywords: teorija grafov, Cayleyjevi grafi, hamiltonski cikli, graph theory, Cayley graphs, hamiltonian cycles