SymmetryTechReportDefinit.pdf (123.28 kB)
Symmetry and optimality of disjoint Hamilton cycles in star graphs
reportposted on 2015-11-05, 13:55 authored by Parisa Derakhshan, Walter HussakWalter Hussak
Multiple edge-disjoint Hamilton cycles have been obtained in labelled star graphs Stn of degree n-1, using number-theoretic means, as images of a known base 2-labelled Hamilton cycle under label-mapping auto- morphisms of Stn. However, no optimum bounds for producing such edge-disjoint Hamilton cycles have been given, and no positive or nega- tive results exist on whether Hamilton decompositions can be produced by such constructions other than a positive result for St5. We show that for all even n there exist such collections, here called symmetric collec- tions, of φ(n)/2 edge-disjoint Hamilton cycles, where φ is Euler's totient function, and that this bound cannot be improved for any even or odd n. Thus, Stn is not symmetrically Hamilton decomposable if n is not prime. Our method improves on the known bounds for numbers of any kind of edge-disjoint Hamilton cycles in star graphs.
Department Computer Science, Loughborough University
- Computer Science
Published inSymmetry and optimality of disjoint Hamilton cycles in star graphs
CitationDERAKHSHAN, P. and HUSSAK, W., 2014. Symmetry and optimality of disjoint Hamilton cycles in star graphs. Technical Report 1111. Department Computer Science, Loughborough University.
PublisherDepartment of Computer Science, Loughborough University.
- VoR (Version of Record)
Publisher statementThis work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/
NotesThis is a report.