On uniqueness of packing of three copies of 2-factors

• Autorzy: Grzelec Igor , Madaras Tomáš , Onderko Alfréd

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.79

• Języki publikacji: EN

Abstrakty

EN

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 C3,C4,C5,C6 and 2C3 have no packing of three copies, C7,C8,C3∪C4,C4∪C4,C3∪C5 and 3C3 have unique packing, and any other collection of cycles has at least two distinct packings.

Słowa kluczowe

EN

uniquely packable graph; 2-factor; 3-packing

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 79--101
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Grzelec Igor

• AGH University of Krakow, Faculty of Applied Mathematics, Department of Discrete Mathematics, al. A. Mickiewicza 30, 30–059 Kraków, Poland

• https://orcid.org/0000-0002-1011-535X

autor

Madaras Tomáš

• P.J. Šafárik University, Institute of Mathematics, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic

• https://orcid.org/0000-0003-4565-043X

autor

Onderko Alfréd

• P.J. Šafárik University, Institute of Mathematics, Faculty of Science, Jesenná 5, 041 54 Košice, Slovak Republic

• https://orcid.org/0000-0003-4811-3955

Bibliografia

• [1] P. Adams, D. Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen, Australas. J. Comb. 35 (2006), 113–118.
• [2] M. Aigner, S. Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc. (2) (1993), 39–51.
• [3] B. Bollobás, S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory Ser. B 25 (1978), 105–124.
• [4] D. Burns, S. Schuster, Every (p, p − 2) graph is contained in its complement, J. Graph Theory 1 (1977), 277–279.
• [5] D. Burns, S. Schuster, Embedding (n, n−1) graphs in their complements, Israel J. Math. 30 (1978), 313–320.
• [6] C.J. Colbourn, J.H. Dinitz (eds), The CRC Handbook of Combinatorial Designs, 2nd ed., CRC Press, Boca Raton, 2006.
• [7] M. Dean, On Hamilton cycle decomposition of 6-regular circulant graphs, Graphs Combin. 22 (2006), 331–340.
• [8] 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.
• [9] I. Grzelec, M. Pilśniak, M. Woźniak, A note on uniquely embeddable 2-factors, Appl. Math. Comput. 468 (2024), 128505.
• [10] 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).
• [11] C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003), 153–169.
• [12] A.J.W. Hilton, M. Johnson, Some results on the Oberwolfach problem, J. London Math. Soc. 64 (2001), 513–522.
• [13] M. Meszka, R. Nedela, A. Rosa, Circulants and the chromatic index of Steiner triple systems, Math. Slovaca 56 (2006) 371–378.
• [14] J. Otfinowska, M. Woźniak, A Note on Uniquely Embeddable Forests, Discuss. Math. Graph Th. 33 (2013), no. 1, 193–201.
• [15] N. Sauer, J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978), 295–302.
• [16] H. Wang, N. Sauer, Packing three copies of a tree into a complete graph, European J. Combin. 14 (1993), 137–142.
• [17] Wolfram Research, Inc., Mathematica, Version 14.1, Champaign, IL (2024).
• [18] M. Woźniak, Packing of graphs, Diss. Math. 362 (1997), pp. 78.
• [19] M. Woźniak, A note on uniquely embeddable graphs, Discuss. Math. Graph Theory 18 (1998), 15–21.
• [20] M. Woźniak, Packing of graphs and permutation – a survey, Discrete Math. 276 (2004), 379–391.
• [21] M. Woźniak, A.P. Wojda, Triple placement of graphs, Graphs Combin. 9 (1993), 85–91.
• [22] H.P. Yap, Packing of graphs – a survey, Discrete Math. 72 (1988), 395–404.