Opuscula Math. 45, no. 1 (2025), 79-101
https://doi.org/10.7494/OpMath.2025.45.1.79
Opuscula Mathematica
On uniqueness of packing of three copies of 2-factors
Igor Grzelec
Tomáš Madaras
Alfréd Onderko
Abstract. The packing of three copies of a graph \(G\) is the union of three edge-disjoint copies (with the same vertex set) of \(G\). In this paper, we completely solve the problem of the uniqueness of packing of three copies of 2-regular graphs. In particular, we show that \(C_3,C_4,C_5,C_6\) and \(2C_3\) have no packing of three copies, \(C_7,C_8,C_3 \cup C_4, C_4 \cup C_4, C_3 \cup C_5\) and \(3C_3\) have unique packing, and any other collection of cycles has at least two distinct packings.
Keywords: uniquely packable graph, 2-factor, 3-packing.
Mathematics Subject Classification: 05C70.
- P. Adams, D. Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen, Australas. J. Comb. 35 (2006), 113-118.
- M. Aigner, S. Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc. (2) (1993), 39-51. https://doi.org/10.1112/jlms/s2-48.1.39
- B. Bollobás, S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory Ser. B 25 (1978), 105-124. https://doi.org/10.1016/0095-8956(78)90030-8
- D. Burns, S. Schuster, Every \((p,p-2)\) graph is contained in its complement, J. Graph Theory 1 (1977), 277-279. https://doi.org/10.1002/jgt.3190010308
- D. Burns, S. Schuster, Embedding \((n,n-1)\) graphs in their complements, Israel J. Math. 30 (1978), 313-320. https://doi.org/10.1007/bf02761996
- C.J. Colbourn, J.H. Dinitz (eds), The CRC Handbook of Combinatorial Designs, 2nd ed., CRC Press, Boca Raton, 2006. https://doi.org/10.1201/9781420010541
- M. Dean, On Hamilton cycle decomposition of 6-regular circulant graphs, Graphs Combin. 22 (2006), 331-340. https://doi.org/10.1007/s00373-006-0657-0
- A. Deza, F. Franek, W. Hua, M. Meszka, A. Rosa, Solutions to the Oberwolfach problem for orders 18 to 40, J. Comb. Math. Comb. Comput. 74 (2010), 95-102.
- I. Grzelec, M. Pilśniak, M. Woźniak, A note on uniquely embeddable \(2\)-factors, Appl. Math. Comput. 468 (2024), 128505. https://doi.org/10.1016/j.amc.2023.128505
- A. Hagberg, P. Swart, D. Schult, Exploring network structure, dynamics, and function using NetworkX (No. LA-UR-08-05495; LA-UR-08-5495). Los Alamos National Lab. (LANL), 2008, Los Alamos, NM (United States).
- C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003), 153-169. https://doi.org/10.1016/s0012-365x(02)00685-4
- A.J.W. Hilton, M. Johnson, Some results on the Oberwolfach problem, J. London Math. Soc. 64 (2001), 513-522. https://doi.org/10.1112/s0024610701002666
- M. Meszka, R. Nedela, A. Rosa, Circulants and the chromatic index of Steiner triple systems, Math. Slovaca 56 (2006) 371-378.
- J. Otfinowska, M. Woźniak, A Note on Uniquely Embeddable Forests, Discuss. Math. Graph Th. 33 (2013), no. 1, 193-201. https://doi.org/10.7151/dmgt.1651
- N. Sauer, J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978), 295-302. https://doi.org/10.1016/0095-8956(78)90005-9
- H. Wang, N. Sauer, Packing three copies of a tree into a complete graph, European J. Combin. 14 (1993), 137-142. https://doi.org/10.1006/eujc.1993.1018
- Wolfram Research, Inc., Mathematica, Version 14.1, Champaign, IL (2024).
- M. Woźniak, Packing of graphs, Diss. Math. 362 (1997), pp. 78.
- M. Woźniak, A note on uniquely embeddable graphs, Discuss. Math. Graph Theory 18 (1998), 15-21. https://doi.org/10.7151/dmgt.1060
- M. Woźniak, Packing of graphs and permutation - a survey, Discrete Math. 276 (2004), 379-391. https://doi.org/10.1016/s0012-365x(03)00296-6
- M. Woźniak, A.P. Wojda, Triple placement of graphs, Graphs Combin. 9 (1993), 85-91. https://doi.org/10.1007/bf01195330
- H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988), 395-404. https://doi.org/10.1016/0012-365x(88)90232-4
- Igor Grzelec (corresponding author)
https://orcid.org/0000-0002-1011-535X- AGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30-059 Kraków, Poland
- Tomáš Madaras
- https://orcid.org/0000-0003-4565-043X
- P.J. Šafárik University, Institute of Mathematics, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic
- Alfréd Onderko
- https://orcid.org/0000-0003-4811-3955
- P.J. Šafárik University, Institute of Mathematics, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic
- Communicated by Andrzej Żak.
- Received: 2024-03-18.
- Revised: 2024-09-21.
- Accepted: 2024-10-07.
- Published online: 2024-12-20.
