The rotator graph has vertices labeled by the permutations of n in one line notation, and there is an arc from u to v if a prefix of u's label can be rotated to obtain v's label. In other words, it is the directed Cayley graph whose generators are σ_k := (1 2 … k) for 2 ≤ k ≤ n and these rotations are applied to the indices of a permutation. In a restricted rotator graph the allowable rotations are restricted from k ∈ {2,3,..., n} to k ∈ G for some smaller (finite) set G is contained in {2,3,..., n}. We construct Hamilton cycles for G = {n- 1,n} and G = {2,3,n}, and provide efficient iterative algorithms for generating them. Our results start with a Hamilton cycle in the rotator graph due to Corbett (IEEE Transactions on Parallel and Distributed Systems 3 (1992) 622-626) and are constructed entirely from two sequence operations we name 'reusing' and 'recycling'.
展开▼
机译：旋转图具有以n个排列标记的顶点，并在一行中标记，并且如果u的标签的前缀可以旋转以获得v的标签，则从u到v会有一个弧线。换句话说，它是有向Cayley图，其生成器对于2≤k≤n为σ_k：=（1 2…k），并将这些旋转应用于置换的索引。在受限转子图中，对于一些较小（有限）的集合G，G包含在{2,3，...，n}中，允许的旋转从k∈{2,3，...，n}限制到k∈G。 。我们为G = {n-1，n}和G = {2,3，n}构造汉密尔顿循环，并提供有效的迭代算法来生成它们。由于Corbett（IEEE Transactions on Parallel and Distributed Systems 3（1992）622-626），我们的结果从旋转图中的汉密尔顿循环开始，并且完全由两个名为“重用”和“循环”的序列操作构成。
展开▼
