SymmetryTechReportDefinit.pdf (123.28 kB)

Symmetry and optimality of disjoint Hamilton cycles in star graphs

Download (123.28 kB)
report
posted on 05.11.2015, 13:55 by Parisa Derakhshan, Walter 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.

Funding

Department Computer Science, Loughborough University

History

School

  • Science

Department

  • Computer Science

Published in

Symmetry and optimality of disjoint Hamilton cycles in star graphs

Citation

DERAKHSHAN, P. and HUSSAK, W., 2014. Symmetry and optimality of disjoint Hamilton cycles in star graphs. Technical Report 1111. Department Computer Science, Loughborough University.

Publisher

Department of Computer Science, Loughborough University.

Version

VoR (Version of Record)

Publisher statement

This 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/

Publication date

2014

Notes

This is a report.

Language

en

Exports

Logo branding

Exports