Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649212 | Discrete Mathematics | 2009 | 8 Pages |
Abstract
The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group GG has a generating set of size at most log2|G|log2|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Igor Pak, Radoš Radoičić,