ϕ-symmetric Hamilton cycle decompositions of graphs

Document Type


Publication Date



The existence of symmetric Hamilton cycle decompositions for complete graphs and cocktail party graphs has been defined and explored in recent work by Akiyama et al., Brualdi and Schroeder, and others. In these works, the notion of symmetry in cocktail party graphs K2m−F was integrally tied to the missing 1-factor. In this paper, we generalize the notion of symmetric decompositions in two ways. First, we require only that F is symmetric and show that if F is not the invariant 1-factor under the symmetry action, then K2m−F has a symmetric Hamilton cycle decomposition for every m ≥ 2. Second, we consider other actions as symmetry, apply such definitions to appropriate complete graphs and complete multipartite graphs, and classify the existence of Hamilton cycle decompositions with such symmetry.


Copyright © 2015 Elsevier. All rights reserved.