Decompositions of line graphs of complete graphs into paths and cycles. (English) Zbl 1502.05202
Summary: Let \(L( K_n)\) denote the line graph of the complete graph \(K_n\). Let \(\alpha\) and \(\beta\), \(\beta \neq 1\), be non-negative integers. B. A. Cox and C. A. Rodger [J. Graph Theory 21, No. 2, 173–182 (1996; Zbl 0840.05068)] raised the following question: for what values of \(m\) and \(n\) does there exist an \(m\)-cycle decomposition of \(L( K_n)\)? In this paper, the above question is answered for \(m = p\), where \(p\) is an odd prime. In fact, much more than this has been proved. Particularly, for any prime \(p \geq 7\), \(L( K_n)\) can be decomposed into \(\alpha\) cycles of length \(p\) and \(\beta\) paths of length \(p\) if and only if \(p(\alpha + \beta) = n \binom{n - 1}{2} \), the number of edges of \(L( K_n)\). Consequently, when \(\beta = 0\), this completely characterizes the existence of a \(p\)-cycle decomposition of \(L( K_n)\), where \(p\) is an odd prime. Further, a complete characterization for the existence of a \(P_{k + 1} \)-decomposition of \(L( K_n)\), where for \(k = p^\ell\), \(\ell \geq 1\) and \(p\) is an odd prime, is obtained.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
| 05C76 | Graph operations (line graphs, products, etc.) |
Citations:
Zbl 0840.05068References:
| [1] | Abueida, A.; Clark, S.; Leach, D., Multidecomposition of the complete graph into graph pairs of order 4 with various leaves, Ars Comb., 93, 403-407 (2009) · Zbl 1224.05335 |
| [2] | Abueida, A.; Daven, M., Multidesigns for graph-pairs of order 4 and 5, Graphs Comb., 19, 433-447 (2003) · Zbl 1032.05105 |
| [3] | Abueida, A.; Daven, M., Multidecompositions of the complete graph, Ars Comb., 72, 17-22 (2004) · Zbl 1071.05059 |
| [4] | Abueida, A.; Daven, M., Multidecompositions of several graph products, Graphs Comb., 29, 315-326 (2013) · Zbl 1267.05223 |
| [5] | Abueida, A. A.; Lian, C., On the decompositions of complete graphs into cycles and stars on the same number of edges, Discuss. Math., Graph Theory, 34, 113-125 (2014) · Zbl 1292.05211 |
| [6] | Abueida, A. A.; O’Neil, T., Multidecomposition of \(\lambda K_m\) into small cycles and claws, Bull. Inst. Comb. Appl., 49, 32-40 (2007) · Zbl 1112.05084 |
| [7] | Akiyama, J.; Kobayashi, M.; Nakamura, G., Uniform coverings of 2-paths with 6-paths in the complete graph, (Akiyama, J.; etal., Combinatorial Geometry and Graph Theory, IJCCGGT 2003. Combinatorial Geometry and Graph Theory, IJCCGGT 2003, Lecture Notes in Computer Science, vol. 3330 (2005), Springer-Verlag), 25-33 · Zbl 1117.05085 |
| [8] | Bryant, D., Packing paths in complete graphs, J. Comb. Theory, Ser. B, 100, 206-215 (2010) · Zbl 1216.05111 |
| [9] | Bryant, D.; Horsley, D.; Pettersson, W., Cycle decompositions V: complete graphs into cycles of arbitrary lengths, Proc. Lond. Math. Soc., 108, 3, 1153-1192 (2014) · Zbl 1296.05044 |
| [10] | Beggas, F.; Haddad, M.; Kheddouci, H., Decomposition of complete multigraphs into stars and cycles, Discuss. Math., Graph Theory, 35, 629-639 (2015) · Zbl 1327.05268 |
| [11] | Colby, M.; Rodger, C. A., Cycle decompositions of the line graph of \(K_n\), J. Comb. Theory, Ser. A, 62, 158-161 (1993) · Zbl 0777.05076 |
| [12] | Cox, B. A., The complete spectrum of 6-cycle systems of \(L( K_n)\), J. Comb. Des., 3, 353-362 (1995) · Zbl 0886.05097 |
| [13] | Cox, B. A.; Rodger, C. A., Cycle systems of the line graph of the complete graph, J. Graph Theory, 21, 173-182 (1996) · Zbl 0840.05068 |
| [14] | Ezhilarasi, A. P.; Muthusamy, A., Decomposition of Cartesian product of complete graphs into paths and stars with four edges, Comment. Math. Univ. Carol., 63, 273-289 (2021) · Zbl 1524.05199 |
| [15] | Fu, C. M.; Lin, Y. L.; Lo, S. W.; Hsu, Y. F., Decomposition of complete graphs into triangles and claws, Taiwan. J. Math., 18, 1563-1581 (2014) · Zbl 1357.05099 |
| [16] | Ganesamurthy, S.; Paulraja, P., A \(C_5\)-decomposition of the λ-fold line graph of the complete graph, Discrete Math., 342, 2197-2210 (2019) |
| [17] | Ganesamurthy, S.; Paulraja, P.; Srimathi, R., Multidecompositions of line graphs of complete graphs, Discrete Math. Algorithms Appl., 11, Article 1950035 pp. (2019) · Zbl 1418.05094 |
| [18] | Heinrich, K.; Kobayashi, M.; Nakamura, G., Dudeney’s round table problem, Discrete Math., 92, 107-125 (1991) · Zbl 0762.05056 |
| [19] | Heinrich, K.; Nonay, G., Exact coverings of 2-paths by 4-cycles, J. Comb. Theory, Ser. A, 45, 50-61 (1987) · Zbl 0675.05044 |
| [20] | Heinrich, K.; Verrall, H., A construction of a perfect set of Euler tours of \(K_{2 k + 1}\), J. Comb. Des., 5, 215-230 (1997) · Zbl 0914.05047 |
| [21] | Ilayaraja, M.; Muthusamy, A., Decomposition of complete bipartite graphs into cycles and stars with four edges, AKCE Int. J. Graphs Comb., 17, 697-702 (2020) · Zbl 1468.05025 |
| [22] | Ilayaraja, M.; Sowndhariya, K.; Muthusamy, A., Decomposition of product graphs into paths and stars on five vertices, AKCE Int. J. Graphs Comb., 17, 777-783 (2020) · Zbl 1468.05026 |
| [23] | Jeevadoss, S.; Muthusamy, A., Decomposition of complete bipartite graphs into paths and cycles, Discrete Math., 331, 98-108 (2014) · Zbl 1297.05190 |
| [24] | Jeevadoss, S.; Muthusamy, A., Decomposition of product graphs into paths and cycles of length four, Graphs Comb., 32, 199-223 (2016) · Zbl 1331.05182 |
| [25] | Lee, H.-C., Multidecompositions of complete bipartite graphs into cycles and stars, Ars Comb., 108, 355-364 (2013) · Zbl 1289.05375 |
| [26] | Lee, H.-C., Decomposition of the complete bipartite multigraph into cycles and stars, Discrete Math., 338, 1362-1369 (2015) · Zbl 1310.05173 |
| [27] | Lee, H.-C.; Chen, Z.-C., Maximum packings and minimum coverings of multigraphs with paths and stars, Taiwan. J. Math., 19, 1341-1357 (2015) · Zbl 1357.05124 |
| [28] | Lindner, C. C.; Rodger, C. A., Design Theory (2009), CRC Press: CRC Press Boca Raton · Zbl 1157.68403 |
| [29] | McCauley, L.; Rodger, C. A., Hamilton cycle rich 2-factorizations of complete multipartite graphs, Graphs Comb., 24, 47-52 (2008) · Zbl 1158.05053 |
| [30] | N. Mutoh, Some results on symmetry Dudeney sets, 2016, pp. 1-5, (in Japanese), Manuscript. |
| [31] | Priyadharsini, H. M.; Muthusamy, A., \(( G_m, H_m)\)-multidecomposition of \(K_{m , m}(\lambda)\), Bull. Inst. Comb. Appl., 66, 42-48 (2012) · Zbl 1271.05080 |
| [32] | Shyu, T.-W., Decomposition of complete graphs into paths and stars, Discrete Math., 310, 2164-2169 (2010) · Zbl 1219.05146 |
| [33] | Shyu, T. W., Decomposition of complete graphs into paths and cycles, Ars Comb., 97, 257-270 (2010) · Zbl 1249.05313 |
| [34] | Shyu, T. W., Decomposition of complete graphs into paths of length three and triangles, Ars Comb., 107, 209-224 (2012) · Zbl 1289.05381 |
| [35] | Shyu, T.-W., Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math., 313, 865-871 (2013) · Zbl 1260.05096 |
| [36] | Shyu, T. W., Decomposition of complete graphs into cycles and stars, Graphs Comb., 29, 301-313 (2013) · Zbl 1263.05079 |
| [37] | Verrall, H., A construction of a perfect set of Euler tours of \(K_{2 m} + I\), J. Comb. Des., 6, 183-212 (1998) · Zbl 0911.05047 |
| [38] | Wallis, W. D., One-Factorizations (1997), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht · Zbl 0863.05064 |
| [39] | West, D. B., Introduction to Graph Theory (2001), Prentice-Hall |
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.
