Edge-disjoint Hamilton cycles in the McKay--Miller--\v{S}ir\'{a}\v{n} graphs for every prime power
En palabras de los autores
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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 18 pages,4 figures