On queens and tours
Pieter Jacobs, Andrés López Martínez, Frits C. R. Spieksma · Operations Research Letters · 2025
Given the complete graph on n vertices, where n ≥ 3 , we define two Hamiltonian cycles as cyclic disjoint if, for each pair of vertices, the distance between them in one Hamiltonian cycle differs from the distance between them in the other Hamiltonian cycle. We investigate the number of pairwise cyclic disjoint tours that exist in K n . Specifically, we identify when pairs of cyclic disjoint tours can occur and provide a procedure to generate m − 1 2 pairwise cyclic disjoint tours, where m is the smallest prime factor of n . Finally, we demonstrate that the number m − 1 2 of pairwise cyclic disjoint tours is maximized when n is prime.