Decomposing the complete graph and the complete graph minus a 1-factor into copies of a graph \(G\) where \(G\) is the union of two disjoint cycles. (English) Zbl 1373.05148
Summary: Let \(G\) of order \(n\) be the vertex-disjoint union of two cycles. It is known that there exists a \(G\)-decomposition of \(K_v\) for all \(v\equiv 1\pmod{2n}\). If \(G\) is bipartite and \(x\) is a positive integer, it is also known that there exists a \(G\)-decomposition of \(K_{nx}-I\), where \(I\) is a 1-factor. If \(G\) is not bipartite, there exists a \(G\)-decomposition of \(K_n\) if \(n\) is odd, and of \(K_n-I\), where \(I\) is a 1-factor, if \(n\) is even. We use novel extensions of the Bose construction for Steiner triple systems and some recent results on the Oberwolfach Problem to obtain a \(G\)-decomposition of \(K_v\) for all \(v\equiv m\pmod{2n}\) when \(n\) is odd, unless \(G=C_4\cup C_5\) and \(v=9\). If \(G\) consists of two odd cycles and \(n\equiv 0\pmod 4\), we also obtain a \(G\)-decomposition of \(K_v-I\), for all \(v\equiv 0\pmod n\), \(v\neq 4n\).
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
| 05B07 | Triple systems |
References:
| [1] | Abrham, J.; Kotzig, A., Graceful valuations of \(2\)-regular graphs with two components, Discrete Math., 150, 3-15 (1996) · Zbl 0856.05086 |
| [2] | Adams, P.; Bryant, D.; Buchanan, M., A survey on the existence of \(G\)-designs, J. Combin. Des., 16, 373-410 (2008) · Zbl 1168.05303 |
| [3] | Adams, P.; Bryant, D.; Gavlas, H., Decompositions of the complete graph into small 2-regular graphs, J. Combin. Math. Combin. Comput., 43, 135-146 (2002) · Zbl 1028.05082 |
| [4] | Alspach, B.; Gavlas, H., Cycle decompositions of \(K_n\) and of \(K_n - I\), J. Combin. Theory Ser. B, 81, 77-99 (2001) · Zbl 1023.05112 |
| [5] | Blinco, A.; El-Zanati, I., A note on the cyclic decomposition of complete graphs into bipartite graphs, Bull. Inst. Combin. Appl., 40, 77-82 (2004) · Zbl 1045.05078 |
| [6] | Blinco, A.; El-Zanati, S.; Vanden Eynden, C., On the decomposition of complete graphs into almost-bipartite graphs, Discrete Math., 284, 71-81 (2004) · Zbl 1044.05057 |
| [7] | Bose, R. C., On the construction of balanced incomplete block designs, Ann. Eugenics, 9, 353-399 (1939) · JFM 65.1110.04 |
| [8] | Bryant, D.; Danziger, P., On bipartite 2-factorizations of \(K_n - I\) and the Oberwolfach problem, J. Graph Theory, 68, 22-37 (2011) · Zbl 1230.05231 |
| [9] | Bryant, D.; El-Zanati, S., (Colbourn, C. J.; Dinitz, J. H., Graph Decompositions. Graph Decompositions, Handbook of Combinatorial Designs (2007), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton), 477-485 · Zbl 1101.05001 |
| [10] | Bunge, R. C.; Chantasartrassmee, A.; El-Zanati, S.; Vanden Eynden, C., On cyclic decompositions of complete graphs into tripartite graphs, J. Graph Theory, 72, 90-111 (2013) · Zbl 1259.05136 |
| [11] | Buratti, M.; Gionfriddo, L., Strong difference families over arbitrary graphs, J. Combin. Des., 16, 443-461 (2008) · Zbl 1182.05016 |
| [12] | El-Zanati, S.; Jongthawonwuth, U.; Jordon, H.; Vanden Eynden, C., On decomposing the complete graph into the union of two disjoint cycles, Lecture Notes in Comput. Sci., 8986, 153-163 (2015) · Zbl 1401.05233 |
| [13] | El-Zanati, S.; Vanden Eynden, C.; Punnim, N., On the cyclic decomposition of complete graphs into bipartite graphs, Australas. J. Combin., 24, 209-219 (2001) · Zbl 0983.05063 |
| [14] | Gannon, D. I.; El-Zanati, S., All 2-regular graphs with uniform odd components admit \(\rho \)-labelings, Australas. J. Combin., 53, 207-219 (2012) · Zbl 1256.05212 |
| [15] | Häggkvist, R., A lemma on cycle decompositions, Ann. Discrete Math., 27, 227-232 (1985) · Zbl 0577.05045 |
| [16] | Hoffman, D. G.; Lindner, C. C.; Rodger, C. A., On the construction of odd cycle systems, J. Graph Theory, 13, 417-426 (1989) · Zbl 0704.05031 |
| [17] | Jongthawonwuth, U.; El-Zanati, S.; Uiyyasathian, C., On extending the bose construction for triple systems to decompositions of complete multipartite graphs into 2-regular graphs of odd order, Australas. J. Combin., 59, 378-390 (2014) · Zbl 1296.05026 |
| [18] | Lindner, C. C.; Rodger, C. A., (Design Theory. Design Theory, Discrete Mathematics and its Applications (2009), CRC Press: CRC Press Boca Raton, FL) · Zbl 1157.68403 |
| [19] | Lindner, C. C.; Rodger, C. A.; Stinson, C. R., Nesting of cycle systems of odd length, Discrete Math., 77, 191-203 (1989) · Zbl 0714.05014 |
| [20] | Rosa, A., On certain valuations of the vertices of a graph, (Théorie des graphes, journées internationales d’études (1967), Dunod: Dunod Paris), 349-355 · Zbl 0193.53204 |
| [21] | Šajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des., 10, 27-78 (2002) · Zbl 1033.05078 |
| [22] | Traetta, A., Complete solution to the two-table oberwolfach problems, J. Combin. Theory Ser. A, 120, 984-997 (2013) · Zbl 1277.05143 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
