Hamiltonian cycles in Cayley graphs whose order has few prime factors

Klavdija Kutnar, Dragan Marušič, Dave Witte Morris, Joy Morris, Primož Šparl

Abstract


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 ≠ k < 32, or of the form kpq with k ≤ 5, or of the form pqr, or of the form kp2 with k ≤ 4, or of the form kp3 with k ≤ 2.

Keywords


Cayley graphs, hamiltonian cycles

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.177.341

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications