TY - JOUR

T1 - The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations

AU - Verhoeff, T.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - Consider the graph with all permutations of a symbol sequence as vertices, where two permutations are connected by an edge when they differ by an interchange of two distinct adjacent symbols. In 1965, D. H. Lehmer conjectured that all vertices in this graph can be visited by a Hamiltonian path that is possibly imperfect, in the sense of having spurs. Such a spur visits a vertex twice, with a single vertex in-between. We prove Lehmer’s conjecture for binary permutations that involve only two distinct symbols. For general symbol sequences, we identify the stutter permutations as candidate spur tips, and prove that the non-stutter permutations admit a disjoint cycle cover. We also provide new (simpler) proofs for some known results.

AB - Consider the graph with all permutations of a symbol sequence as vertices, where two permutations are connected by an edge when they differ by an interchange of two distinct adjacent symbols. In 1965, D. H. Lehmer conjectured that all vertices in this graph can be visited by a Hamiltonian path that is possibly imperfect, in the sense of having spurs. Such a spur visits a vertex twice, with a single vertex in-between. We prove Lehmer’s conjecture for binary permutations that involve only two distinct symbols. For general symbol sequences, we identify the stutter permutations as candidate spur tips, and prove that the non-stutter permutations admit a disjoint cycle cover. We also provide new (simpler) proofs for some known results.

KW - Hamiltonian path

KW - Minimal-change generation

KW - Permutation

UR - http://www.scopus.com/inward/record.url?scp=84995394509&partnerID=8YFLogxK

U2 - 10.1007/s10623-016-0301-9

DO - 10.1007/s10623-016-0301-9

M3 - Article

AN - SCOPUS:84995394509

VL - 84

SP - 295

EP - 310

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 1-2

ER -