Hamiltonian cycles in neighbor-swap graphsSmerdu, Ana (Avtor) Verhoeff, Tom (Mentor) Žitnik, Arjana (Komentor) neighbor-swap graphsmultisetspermutationstranspositionsHamiltonian pathsLehmer pathsposetsIn 1965 Derrick Henry Lehmer conjectured that every neighbor-swap graph admits an imperfect Hamiltonian path. This path, also known as Lehmer path, is a walk visiting all the vertices of a graph where some of them might be visited twice in a row. For most of the neighbor-swap graphs the conjecture is already proved, it remains open only for two families of graphs. We will present known results with their proofs in the thesis. It turns out most of these graphs even contain a Lehmer cycle and we will show how to construct them. For the missing part of the proof we will present a possible approach, that might finally confirm D. H. Lehmer's conjecture. First we find a Hamiltonian path in a related binary neighbor-swap graph and then step by step add the missing symbols, connecting the paths together into a Lehmer path.20192019-07-25 08:30:39Magistrsko delo/naloga108786sl