Abstract
For any two 2-regular spanning subgraphs G and H of the complete multipartite graph K, necessary and sufficient conditions are found for the existence of a 2-factorization of K in which
-
1.
the first and second 2-factors are isomorphic to G and H respectively, and
-
2.
each other 2-factor is a hamilton cycle
in the case where K has an odd number of vertices.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adams, P., Bryant, D.: Two-factorisations of complete graphs of orders fifteen and seventeen. Australas. J. Combin. 35, 113–118 (2006)
Alspach, B., Schellenberg, P., Stinson, D., Wagner, D.: The Oberwolfach problem and factors of uniform odd length cycles. J. Combin. Theory, Ser A 52, 20–43 (1989)
Bermond, J., Favaron, O., Maheo, M.: Hamilton decomposition of Cayley graphs of degree 4. J. Combin. Theory, Ser. B 46, 142–153 (1989)
Bryant, D.: Hamilton cycle rich 2-factorizations of complete graphs. J. Combin. Des. 12, 147–155 (2004)
Bryant, D., Rodger, C.A.: Cycle decompositions, CRC Handbook of Combinatorial Designs. In: Colbourn, C.J., Dinitz, J.H., (eds.) 2nd edition, CRC Press, 2007
Buchanan, H. III: Ph.D. Dissertation, University of West Virginia, 1996
Franek, F., Rosa, A.: Two-factorizations of small complete graphs. J. Statist. Plann. Inference 86, 435–442 (2000)
Hoffman, D.G., Schellenberg, P.: The existence of a C k -factorization of K2n − F, Discrete Math. 97, 243–250 (1991)
Plantholt, M.: The chromatic index of graphs with a spanning star. J. Graph Theory 5, 45–53 (1981)
Rodger, C.A.: Hamilton decomposable graphs with specified leaves. Graphs Combin. 20, 541–543 (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
McCauley, L., Rodger, C.A. Hamilton Cycle Rich 2-factorizations of Complete Multipartite Graphs. Graphs and Combinatorics 24, 47–52 (2008). https://doi.org/10.1007/s00373-008-0763-2
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-008-0763-2