1041. On Queens and Tours
Invited abstract in session WD-17: Diversity in Solutions to CO problems, stream Combinatorial Optimization.
Wednesday, 14:30-16:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Frits Spieksma
|
| Mathematics and Computer Science, Eindhoven University of Technology | |
| 2. | Pieter Jacobs
|
| Eindhoven University of Technology | |
| 3. | Andres Lopez Martinez
|
| Mathematics and Computer Science, Eindhoven University of Technology |
Abstract
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 Kn. 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.
Keywords
- Combinatorial Optimization
- Graphs and Networks
Status: accepted
Back to the list of papers