×
Ezhilarasi, A. Pauline; Muthusamy, A.

Decomposition of complete equipartite graphs into paths and cycles of length \(2p\). (English) Zbl 1502.05201

Discrete Math. 346, No. 1, Article ID 113160, 11 p. (2023).
Summary: Let \(P_k\) and \(C_k\) respectively denote a path and a cycle on \(k\) vertices. In this paper, we give necessary and sufficient conditions for the existence of a complete \(\{ P_{2 p + 1}, C_{2 p} \}\)-decomposition of even regular complete equipartite graphs for all prime \(p\).

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.)

Keywords:

graph decomposition; equipartite graph; path; cycle; product graph
Cite Review PDF
Full Text: DOI

References:

[1] Abueida, A. A.; Daven, M., Multidesigns for graph-pairs of order 4 and 5, Graphs Comb., 19, 433-447 (2003) · Zbl 1032.05105
[2] Abueida, A. A.; Daven, M.; Roblee, K. J., Multidesigns of the λ-fold complete graph-pairs of orders 4 and 5, Australas. J. Comb., 32, 125-136 (2005) · Zbl 1067.05054
[3] Alspach, B.; Gavlas, H., Cycle decompositions of \(K_n\) and \(K_n - I\), J. Comb. Theory, Ser. B, 81, 77-99 (2001) · Zbl 1023.05112
[4] Bahmanian, M. A.; Sajna, M., Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach, J. Comb. Des., 24, 165-183 (2016) · Zbl 1338.05208
[5] Billington, E. J.; Cavenagh, N. J.; Smith, B. R., Path and cycle decompositions of complete equipartite graphs: four parts, Discrete Math., 309, 3061-3073 (2009) · Zbl 1202.05070
[6] Billington, E. J.; Cavenagh, N. J.; Smith, B. R., Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts, Discrete Math., 310, 241-254 (2010) · Zbl 1200.05135
[7] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), The MacMillan Press Ltd.: The MacMillan Press Ltd. London · Zbl 1226.05083
[8] Fu, C. M.; Lin, Y. L.; Lo, S. W.; Hsu, Y. F., Decomposition of complete graphs into triangles and claws, Taiwan. J. Math., 18, 5, 1563-1581 (2014) · Zbl 1357.05099
[9] Horsley, D., Decomposing various graphs into short even-length cycles, Ann. Comb., 16, 571-589 (2012) · Zbl 1256.05189
[10] Jeevadoss, S.; Muthusamy, A., Decomposition of complete bipartite graphs into paths and cycles, Discrete Math., 331, 98-108 (2014) · Zbl 1297.05190
[11] Jeevadoss, S.; Muthusamy, A., Decomposition of product graphs into paths and cycles of length four, Graphs Comb., 32, 199-223 (2016) · Zbl 1331.05182
[12] Lindner, C. C.; Rodger, C. A., Design Theory (2009), CRC Press: CRC Press Boca Raton · Zbl 1157.68403
[13] Pauline Ezhilarasi, A.; Muthusamy, A., Decomposition of product graphs into paths and stars with three edges, Bull. Inst. Comb. Appl., 87, 47-74 (2019) · Zbl 1427.05173
[14] 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
[15] Shyu, T. W., Decompositions of complete graphs into paths and cycles, Ars Comb., 97, 257-270 (2010) · Zbl 1249.05313
[16] Sajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Comb. Des., 10, 27-78 (2002) · Zbl 1033.05078
[17] Smith, B. R., Decomposing complete equipartite graphs into cycle of length 2p, J. Comb. Des., 16, 244-252 (2008) · Zbl 1149.05026
[18] Smith, B. R., Complete equipartite 3p-cycle systems, Australas. J. Comb., 45, 125-138 (2009) · Zbl 1207.05108
[19] Smith, B. R., Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd, J. Comb. Des., 6, 401-414 (2010) · Zbl 1208.05118
[20] Tarsi, M., Decomposition of complete multigraph into simple paths: nonbalanced handcuffed designs, J. Comb. Theory, Ser. A, 34, 60-70 (1983) · Zbl 0511.05024
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.