On invariants for 1-factorizations of K2n: Description and computation

Articles in Press

Document Type : Original paper

Authors

1 Graduate Program in Computer Science, Federal University of Sergipe, Säo Cristóväo, Brazil

2 Institute of Computing, Universidade Federal da Bahia, Salvador, Brazil

3 Computer Science Department, Boston University, Boston, MA 02215, USA

4 Faculty of Logistics, Molde University College, Norway

5 Institut de Mathématiques, EPFL, Lausanne CH-1015, Switzerland

Abstract

A 1-factorization is a partition of the edge set of a graph into perfect matchings. The concept of 1-factorization is of great interest due to its applications in modeling sports tournaments. An invariant of a 1-factorization is a property that depends only on its structure such that isomorphic 1-factorizations are guaranteed to have equal invariant values. As such, non-isomorphic 1-factorizations may or may not have different invariant values. An invariant is complete when any two non-isomorphic 1-factorizations have distinct invariant values. We review seven invariants available in the literature to distinguish non-isomorphic 1-factorizations of $K_{2n}$ (complete graphs with an even number of vertices). Additionally, considering that the invariants available in the literature are not complete, we propose two new ones, denoted lantern profiles and even-size bichromatic chains. We analyze the invariants concerning their sizes and calculation time complexity. Furthermore, we conduct computational experiments to assess their ability to distinguish non-isomorphic 1-factorizations. To accomplish that we use the sets of non-isomorphic 1-factorizations of $K_{10}$ and $K_{12}$. We also consider the sets of non-isomorphic perfect 1-factorizations of $K_{12}$, $K_{14}$, and $K_{16}$, as well as randomly generated 1-factorizations of $K_{16}$ and $K_{20}$. Moreover, the experiments evaluate how the combination of invariants can increase the distinguishing ability.  

Keywords

Main Subjects

References

[1] L. Babai, Graph isomorphism in quasipolynomial time, L. Babai, Graph isomorphism in quasipolynomial time, 2015, pp. arXiv e–prints https://doi:10.48550/ARXIV.1512.03547
[2] L. Babai, Graph isomorphism in quasipolynomial time [extended abstract], Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (New York, NY, USA), Association for Computing Machinery, 2016, pp. 684–697.
[3] R.C. Brigham and R.D. Dutton, A compilation of relations between graph invariants, Networks 15 (1985), no. 1, 73–107.
[4] L. E. Dickson and F. H. Safford, 8, The American Mathematical Monthly 13 (1906), no. 6/7, 150–151.
[5] J.H. Dinitz and D.K. Garnick, There are 23 nonisomorphic perfect onefactorizations of K14, J. Comb. Des. 4 (1996), no. 1, 1–4.
[6] J.H. Dinitz, D.K. Garnick, and B.D. McKay, There are 526,915,620 nonisomorphic one-factorizations of K12, J. Comb. Des. 2 (1994), no. 4, 273–285. https://doi.org/10.1002/jcd.3180020406
[7] J.H. Dinitz and W.D. Wallis, Trains: An invariant for one-factorizations, Ars Combin. 32 (1991), 161–180.
[8] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman & Co., San Francisco, 1979.
[9] E.N. Gelling, On 1-factorizations of the complete graph and the relationship to round robin schedules, Ph.D. thesis, 1973.
[10] E.N. Gelling and R.E. Odeh, On 1-factorizations of the complete graph and the relationship to round-robin schedules, Congr. Numer. 9 (1974), 213–221.
[11] M.J. Gill and I.A.N.M. Wanless, Perfect 1-factorisations of K16, Bull. Aust. Math. Soc. 101 (2020), no. 2, 177–185.
https://doi.org/10.1017/S0004972719000856
[12] T.S. Griggs and A. Rosa, An invariant for one-factorizations of the complete graph, Ars Combin. 42 (1996), 77–88.
[13] M. Grohe and P. Schweitzer, The graph isomorphism problem, Commun. ACM 63 (2020), no. 11, 128–134.
https://doi.org/10.1145/3372123
[14] H.A. Helfgott, J. Bajpai, and D. Dona, Graph isomorphisms in quasi-polynomial time, arXiv preprint arXiv:1710.04574 (2017), https://doi.org/10.48550/arXiv.1710.04574
[15] T. Januario, S. Urrutia, C.C. Ribeiro, and D. de Werra, Edge coloring: A natural model for sports scheduling, Eur. J. Oper. Res. 254 (2016), no. 1, 1–8. https://doi.org/10.1016/j.ejor.2016.03.038
[16] P. Kaski, A. de Souza Medeiros, P.R.J. Östergård, and I.M. Wanless, Switching in one-factorisations of complete graphs, 21 (2014), 1–24. https://doi.org/10.37236/3606
[17] P. Kaski and P.R.J. Östergård, There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of K14, J. Comb. Des. 17 (2009), no. 2, 147–159. https://doi.org/10.1002/jcd.20188.
[18] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symb. Comput. 60 (2014), 94–112. https://doi.org/10.1016/j.jsc.2013.09.003
[19] E. Mendelsohn and A. Rosa, One-factorizations of the complete graph–A survey, J. Graph Theory 9 (1985), no. 1, 43–65. https://doi.org/10.1002/jgt.3190090104
[20] M. Meszka, There are 3155 nonisomorphic perfect one-factorizations of v16, J. Comb. Des. 28 (2020), no. 1, 85–94.
https://doi.org/10.1002/jcd.21683
[21] J. Misra and D. Gries, A constructive proof of Vizing’s theorem, Inf. Process. Lett. 41 (1992), no. 3, 131–133. https://doi.org/10.1016/0020-0190(92)90041-S
[22] A.P. Petrenyuk and A.Y. Petrenyuk, Intersection of perfect 1-factorizations of complete graphs, Cybernetics 16 (1980), no. 1, 6–9. https://doi.org/10.1007/BF01099353
[23] A. Rosa, Perfect 1-factorizations, Math. Slovaca 69 (2019), no. 3, 479–496. https://doi.org/10.1515/ms-2017-0241
[24] S. Urrutia, D. de Werra, and T. Januario, Recoloring subgraphs of K2n for sports scheduling, Theor. Comput. Sci. 877 (2021), 36–45. https://doi.org/10.1016/j.tcs.2021.03.029
[25] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Discrete Analiz 3 (1964), 25 – 30. https://doi.org/10022205410
[26] W.D. Wallis, On one-factorizations of complete graphs, J. Aust. Math. Soc. 16 (1973), no. 2, 167–171. https://doi.org/10.1017/S1446788700014178
[27] W.D. Wallis, One-factorizations, Mathematics and Its Applications, Springer, 1997.
[28] W.D. Wallis, Introduction to Combinatorial Designs, Second Edition (Discrete Mathematics and Applications), Chapman & Hall/CRC, 2007.
[29] I.M. Wanless, Cycle switches in Latin squares, Graphs Combin. 20 (2004), no. 4, 545–570. https://doi.org/10.1007/s00373-004-0567-7
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 14 November 2025

Files

Share

How to cite

Statistics