pipette
ESEspañol

Edge-disjoint Hamilton cycles in the McKay--Miller--\v{S}ir\'{a}\v{n} graphs for every prime power

Xihe Li

Preprint

In the authors' words

Motivated by Hamilton cycle problems and applications to collective communication, we study edge-disjoint Hamilton cycles in the McKay--Miller--\v{S}ir\'{a}\v{n} (MMS) graphs. The MMS graph (indexed by a prime power ) is a highly symmetric graph arising from finite fields. For every prime power , we prove that the MMS graph contains edge-disjoint Hamilton cycles. This resolves a problem of Li, Wang and Zheng, who established the result for prime and for . Our construction uses graph lifts over finite fields and joins the components of lifted Hamilton cycles by adding edges within vertex fibres. The resulting cycles can be constructed using finite field operations, comparisons, and elementary list operations. As an application, these cycles provide edge-disjoint spanning rings for parallel ring-all-reduce algorithms on MMS networks.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 18 pages,4 figures