Hamiltonicity of generalised Petersen graphs
Katja Kodrič · PeFprints (University of Ljubljana) · 2012
In 1969 Lászlo Lovász posed a question whether every connected vertex-transitive graph has a Hamiltonian path, i.e. path which visits every vertex of a given graph. Answer to his question is still not known. Moreover, only five connected vertex-transitive graphs, which do not have a Hamiltonian cycle, are known. In chase of finding an answer to this question, special family of cubic graphs known as generalised Petersen graphs have an important role, too. This is why we prove the following result: every cubic Generalised Petersen graph (with an exception of graphs , and ) contains a Hamiltonian cycle.