Abstract
Let \(K_{n,n}\) be the complete bipartite graph with two parts of equal size n. In this paper, it is shown that depending on whether n is even or odd, \(K_{n,n}\) or \(K_{n,n}-I\), where I is a 1-factor of \(K_{n,n}\), can be decomposed into cycles of distinct even lengths for any integer \(n \ge 2\) with the exception of \(n = 4\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alspach, B.: Research problems. Discrete Math. 36, 333–334 (1981)
Archdeacon, D., Debowsky, M., Dinitz, J., Gavlas, H.: Cycle systems in the complete bipartite graph minus a one-factor. Discrete Math. 284, 37–43 (2004)
Bryant, D.: Cycle decompositions of complete graphs. In: Hilton, A., Talbot. J.: (eds.) Surveys in Combinatorics 2007, London Mathematical Society Lecture Note Series, vol. 346, Proceedings of the 21st British Combinatorial Conference, Cambridge University Press, pp. 67–97 (2007)
Bryant, D., Adams, P.: Decomposing the complete graph into cycles of many lengths. Graphs Combin. 11, 97–102 (1995)
Bryant, D., Horsley, D., Pettersson, W.: Cycle decompositions V: complete graphs into cycles of arbitrary lengths. Proc. Lond. Math. Soc. 108, 1153–1192 (2014)
Bryant, D., Rodger, C.A.: Cycle decompositions. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 373–382. CRC Press, Boca Raton (2007)
Chou, C.-C., Fu, C.-M.: Decomposition of \(K_{m, n}\) into \(4\)-cycles and \(2t\)-cycles. J. Combin. Optim. 14(205–218), 205–218 (2007)
Chou, C.-C., Fu, C.-M., Huang, W.-C.: Decomposition of \(K_{m, n}\) into short cycles. Discrete Math. 197(198), 195–203 (1999)
Horsley, D.: Decomposing various graphs into short even-length cycles. Ann. Combin. 16, 571–589 (2012)
Ma, J., Pu, L., Shen, H.: Cycle decompositions of \(K_{n, n}-I\). SIAM J. Discrete Math. 20, 603–609 (2006)
Sotteau, D.: Decomposition of \(K_{m, n}\) (\(K_{m, n}^*\)) into cycles (circuits) of length \(2k\). J. Combin. Theory B 30, 75–81 (1981)
West, D.: Introduction to Graph Theory, 3rd edn. Prentice Hall, Saddle River (2007)
Acknowledgments
The authors wish to thank the referees for their helpful advice, especially suggesting the better terms and sentences in order to improve the readability of the manuscript. The work of C.-M. Fu was supported in part by MOST 103-2115-M-032-002. The work of M. Mishima was supported in part by JSPS under Grant-in-Aid for Scientific Research (C)25400200 and (B)15H03636.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fu, CM., Huang, KC. & Mishima, M. Decomposition of Complete Bipartite Graphs into Cycles of Distinct Even Lengths. Graphs and Combinatorics 32, 1397–1413 (2016). https://doi.org/10.1007/s00373-015-1664-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-015-1664-9