Geodesic
Decomposition of the Tensor Product of Complete Graphs into Cycles of Lengths 3 and 6
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 249-266.

Voir la notice de l'article provenant de la source Library of Science

By a {C_3^α, C_3^β}-decomposition of a graph G, we mean a partition of the edge set of G into α cycles of length 3 and β cycles of length 6. In this paper, necessary and sufficient conditions for the existence of a {C_3^α, C_3^β}-decomposition of (K_m × K_n)(λ), where × denotes the tensor product of graphs and λ is the multiplicity of the edges, is obtained. In fact, we prove that for λ ≥ 1, m, n ≥ 3 and (m, n) ≠ (3, 3), a {C_3^α, C_3^β}-decomposition of (Km × Kn)(λ) exists if and only if λ(m − 1)(n − 1) ≡ 0 (mod 2) and 3α+6β=λ m(m-1)n(n-1)/2.
Keywords: cycle decomposition, tensor product 
@article{DMGT_2021_41_1_a15,
     author = {Paulraja, P. and Srimathi, R.},
     title = {Decomposition of the {Tensor} {Product} of {Complete} {Graphs} into {Cycles} of {Lengths} 3 and 6},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {249--266},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a15/}
}
TY  - JOUR
AU  - Paulraja, P.
AU  - Srimathi, R.
TI  - Decomposition of the Tensor Product of Complete Graphs into Cycles of Lengths 3 and 6
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 249
EP  - 266
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a15/
LA  - en
ID  - DMGT_2021_41_1_a15
ER  - 
%0 Journal Article
%A Paulraja, P.
%A Srimathi, R.
%T Decomposition of the Tensor Product of Complete Graphs into Cycles of Lengths 3 and 6
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 249-266
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a15/
%G en
%F DMGT_2021_41_1_a15
Paulraja, P.; Srimathi, R. Decomposition of the Tensor Product of Complete Graphs into Cycles of Lengths 3 and 6. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 249-266. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a15/

[1] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn − I, J. Combin. Theory Ser. B 81 (2001) 77–99. doi: 10.1006/jctb.2000.1996

[2] J. Asplund, J. Chaffee and J.M. Hammer, Decomposition of a complete bipartite multigraph into arbitrary cycle sizes, Graphs Combin. 33 (2017) 715–728. doi: 10.1007/s00373-017-1817-0

[3] A.M. Assaf, Modified group divisible designs, Ars Combin. 29 (1990) 13–20.

[4] A.M. Assaf, An application of modified group divisible designs, J. Combin. Theory Ser. A 68 (1994) 152–168. doi: 10.1016/0097-3165(94)90095-7

[5] A.M. Assaf, Modified group divisible designs with block size 4 and λ > 1, Australas. J. Combin. 16 (1997) 229–238.

[6] A.M. Assaf and R. Wei, Modified group divisible designs with block size 4 and λ = 1, Discrete Math. 195 (1999) 15–25. doi: 10.1016/S0012-365X(98)00161-7

[7] M.A. Bahmanian and M. Šajna, Decomposing complete equipartite multigraphs into cycles of variable lengths: The Amalgamation-detachment approach, J. Combin. Des. 24 (2016) 165–183. doi: 10.1002/jcd.21419

[8] R. Balakrishnan, J.-C. Bermond, P. Paulraja and M.-L. Yu, On Hamilton cycle decompositions of the tensor product of complete graphs, Discrete Math. 268 (2003) 49–58. doi: 10.1016/S0012-365X(02)00680-5

[9] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, 2nd Ed. (Springer, New York, 2012). doi: 10.1007/978-1-4614-4529-6

[10] E.J. Billington, Decomposing complete tripartite graphs into cycles of lengths 3 and 4, Discrete Math. 197/198 (1999) 123–135. doi: 10.1016/S0012-365X(99)90049-3

[11] E.J. Billington and N.J. Cavenagh, Sparse graphs which decompose into closed trails of arbitrary lengths, Graphs Combin. 24 (2008) 129–147. doi: 10.1007/s00373-008-0783-y

[12] E.J. Billington, D.G. Hoffman and B.M. Maenhaut, Group divisible pentagon systems, Util. Math. 55 (1999) 211–219.

[13] D. Bryant, D. Horsley and W. Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, Proc. Lond. Math. Soc. (3) 108 (2014) 1153–1192. doi: 10.1112/plms/pdt051

[14] D. Bryant, D. Horsley, B. Maenhaut and B.R. Smith, Decompositions of complete multigraphs into cycles of varying lengths, J. Combin. Theory Ser. B 129 (2018) 79–106. doi: 10.1016/j.jctb.2017.09.005

[15] M. Buratti, H. Cao, D. Dai and T. Traetta, A complete solution to the existence of (k, λ)-cycle frames of type gu, J. Combin. Des. 25 (2017) 197–230. doi: 10.1002/jcd.21523

[16] C.C. Chou, C.M. Fu and W.C. Huang, Decomposition of Km,n into short cycles, Discrete Math. 197/198 (1999) 195–203. doi: 10.1016/S0012-365X(99)90063-8

[17] C.C. Chou and C.M. Fu, Decomposition of Km,n into 4-cycles and 2t-cycles, J. Comb. Optim. 14 (2007) 205–218. doi: 10.1007/s10878-007-9060-x

[18] C.M. Fu, K.C. Huang and M. Mishima, Decomposition of complete bipartite graphs into cycles of distinct even lengths, Graphs Combin. 32 (2016) 1397–1413. doi: 10.1007/s00373-015-1664-9

[19] S. Ganesamurthy and P. Paulraja, Decompositions of complete tripartite graphs into cycles of lengths 3 and 6, Australas. J. Combin. 73 Part 1, to appear.

[20] H. Hanani, Balanced incomplete block designs and related designs, Discrete Math. 11 (1975) 255–369. doi: 10.1016/0012-365X(75)90040-0

[21] D.G. Hoffman, C.C. Lindner and C.A. Rodger, On the construction of odd cycle systems, J. Graph Theory 13 (1989) 417–426. doi: 10.1002/jgt.3190130405

[22] M.H. Huang and H.L. Fu, (4, 5)-cycle systems of complete multipartite graphs, Taiwanese J. Math. 16 (2012) 999–1006. doi: 10.11650/twjm/1500406672

[23] C.C. Lindner and C.A. Rodger, Design Theory, 2nd Ed. (CRC Press, Boca Raton, 2009).

[24] A.C.H. Ling and C.J. Colbourn, Modified group divisible designs with block size four, Discrete Math. 219 (2000) 207–221. doi: 10.1016/S0012-365X(99)00342-8

[25] R.S. Manikandan and P. Paulraja, Cp-decompositions of some regular graphs, Discrete Math. 306 (2006) 429–451. doi: 10.1016/j.disc.2005.08.006

[26] R.S. Manikandan and P. Paulraja, C5-decompositions of the tensor product of complete graphs, Australas. J. Combin. 37 (2007) 285–293.

[27] R.S. Manikandan and P. Paulraja, C7-decompositions of the tensor product of complete graphs, Discuss. Math. Graph Theory 37 (2017) 523–535. doi: 10.7151/dmgt.1936

[28] R.S. Manikandan and P. Paulraja, Hamiltonian decompositions of the tensor product of a complete graph and a complete bipartite graphs, Ars Combin. 80 (2006) 33–44.

[29] R.S. Manikandan and P. Paulraja, Hamilton cycle decompositions of the tensor product of complete multipartite graphs, Discrete Math. 308 (2008) 3586–3606. doi: 10.1016/j.disc.2007.07.020

[30] R.S. Manikandan and P. Paulraja, Hamilton cycle decompositions of the tensor products of complete bipartite graphs and complete multipartite graphs, Discrete Math. 310 (2010) 2776–2789. doi: 10.1016/j.disc.2010.05.034

[31] R.S. Manikandan, P. Paulraja and S. Sivasankar, Directed Hamilton cycle decompositions of the tensor product of symmetric digraphs, Ars Combin. 98 (2011) 379–386.

[32] A. Muthusamy and A. Shanmuga Vadivu, Cycle frames of complete multipartite multigraphs -III, J. Combin. Des. 22 (2014) 473–487. doi: 10.1002/jcd.21373

[33] P. Paulraja and S. Sampath Kumar, Resolvable even cycle decompositions of the tensor product of complete graphs, Discrete Math. 311 (2011) 1841–1850. doi: 10.1016/j.disc.2011.04.028

[34] P. Paulraja and S. Sampath Kumar, Closed trail decompositions of some classes of regular graphs, Discrete Math. 312 (2012) 1353–1366. doi: 10.1016/j.disc.2011.12.015

[35] P. Paulraja and S. Sivasankar, Directed Hamilton cycle decompositions of the tensor products of symmetric digraphs, Graphs Combin. 25 (2009) 571–581. doi: 10.1007/s00373-009-0866-4

[36] M. Šajna, Cycle decompositions III : Complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27–78. doi: 10.1002/jcd.1027