Hamilton cycles for involutions of classical types

Abstract

Let ${\mathcal{W}}_n$ denote any of the three families of classical Weyl groups: the symmetric groups ${\mathcal{S}}_n$, the hyperoctahedral groups (signed permutation groups) ${\mathcal{S}}_n^B$, or the even-signed permutation groups ${\mathcal{S}}_n^D$. In this paper we give an uniform construction of a Hamilton cycle for the restriction to involutions on these three families of groups with respect to a inverse-closed connecting set of involutions. This Hamilton cycle is optimal with respect to the Hamming distance only for the symmetric group ${\mathcal{S}}_n$. We also recall an optimal algorithm for a Gray code for type $B$ involutions. A modification of this algorithm would provide a Gray Code for type $D$ involutions with Hamming distance two, which would be optimal. We give such a construction for ${\mathcal{S}}_4^D$ and ${\mathcal{S}}_5^D$.