Geodesic
C7-Decompositions of the Tensor Product of Complete Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 523-535.

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

In this paper we consider a decomposition of Km × Kn, where × denotes the tensor product of graphs, into cycles of length seven. We prove that for m, n ≥ 3, cycles of length seven decompose the graph Km × Kn if and only if (1) either m or n is odd and (2) 14 | m(m − 1)n(n − 1). The results of this paper together with the results of [Cp-Decompositions of some regular graphs, Discrete Math. 306 (2006) 429–451] and [C5-Decompositions of the tensor product of complete graphs, Australasian J. Combinatorics 37 (2007) 285–293], give necessary and sufficient conditions for the existence of a p-cycle decomposition, where p ≥ 5 is a prime number, of the graph Km × Kn.
Keywords: cycle decomposition, tensor product 
@article{DMGT_2017_37_3_a1,
     author = {Manikandan, R.S. and Paulraja, P.},
     title = {C\protect\textsubscript{7}-Decompositions of the {Tensor} {Product} of {Complete} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {523--535},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a1/}
}
TY  - JOUR
AU  - Manikandan, R.S.
AU  - Paulraja, P.
TI  - C7-Decompositions of the Tensor Product of Complete Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 523
EP  - 535
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a1/
LA  - en
ID  - DMGT_2017_37_3_a1
ER  - 
%0 Journal Article
%A Manikandan, R.S.
%A Paulraja, P.
%T C7-Decompositions of the Tensor Product of Complete Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 523-535
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a1/
%G en
%F DMGT_2017_37_3_a1
Manikandan, R.S.; Paulraja, P. C7-Decompositions of the Tensor Product of Complete Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 523-535. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a1/

[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] B. Alspach, P.J. Schellenberg, D.R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A 52 (1989) 20–43. doi:10.1016/0097-3165(89)90059-9

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

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

[5] N.J. Cavenagh and E.J. Billington, Decompositions of complete multipartite graphs into cycles of even length, Graphs Combin. 16 (2000) 49–65. doi:10.1007/s003730050003

[6] N.J. Cavenagh and E.J. Billington, On decomposing complete tripartite graphs into 5 -cycles, Australas. J. Combin. 22 (2000) 41–62.

[7] C.C. Lindner and C.A. Rodger, Design Theory (CRC Press New York, 1997).

[8] J. Liu, A Generalization of the Oberwolfach problem and Ct-factorizations of complete equipartite graphs, J. Combin. Designs 8 (2000) 42–49. doi:10.1002/(SICI)1520-6610(2000)8:1〈42::AID-JCD6〉3.0.CO;2-R

[9] E.S. Mahmoodian and M. Mirzakhani, Decomposition of complete tripartite graphs into 5 -cycles, in: Combinatorics and Advances, C.J. Colbourn and E.S. Mahmoodian (Ed(s)), (Kluwer Academic Publ., 1995) 235–241.

[10] 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

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

[12] A. Muthusamy and P. Paulraja, Factorizations of product graphs into cycles of uniform length, Graphs Combin. 11 (1995) 69–90. doi:10.1007/BF01787423

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

[14] B.R. Smith, Decomposing complete equipartite graphs into cycles of length 2 p, J. Combin. Designs 16 (2008) 244–252. doi:10.1002/jcd.20173

[15] B.R. Smith, Complete equipartite 3 p-cycle systems, Australas. J. Combin. 45 (2009) 125–138.

[16] B.R. Smith, Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd, J. Combin. Designs 18 (2010) 401–414. doi:10.1002/jcd.20268

[17] B.R. Smith, Cycle decompositions of λ-fold complete equipartite graphs, Australas. J. Combin. 47 (2010) 145–156.