Cyclic bundle Hamiltonicity

Abstract

Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C _n □^α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G.

Keywords:

• graphs
• cycle
• Cartesian product
• Cartesian graph bundle
• Hamiltonian graph

2010 AMS Subject Classifications :

• 05C45
• 05C76

Acknowledgements

This work was supported in part by the Slovenian research agency ARRS. The authors would like to thank the referee for a careful reading of the manuscript and for many useful remarks that helped us to improve the presentation considerably.