Journal of the Iranian Mathematical Society

Journal of the Iranian Mathematical Society

Decomposition of complete tripartite graphs into triangles and claws

Document Type : Research Article

Authors
S. Priyadarsini 1
A. Muthusamy 2
1 Department of Mathematics, Periyar University, Salem, Tamilnadu, India.
2 Department of Mathematics, Periyar University, Salem, TamilNadu, India.
10.30504/jims.2024.417929.1148
Abstract
Let $K_{{r},{s},{t}}$ be a complete tripartite graph with $r\leq s \leq t$‎. ‎Let $C_{k}$ and $S_{k}$ respectively denote a cycle and a star with $k$ edges‎. ‎In this paper‎, ‎we show that the necessary and sufficient conditions for the existence of $\left\{pC_{3},qS_{3}\right\}$‎ -‎decomposition of $K_{{r},{s},{t}}$ for all possible values of $p,q\geq0$‎.
Keywords
Cycle
Claw
Complete Tripartite graph
Decomposition of graphs
Subjects
[1] S. Alipour, E. S. Mahmoodian and E. Mollaahmadi, On decomposing complete tripartite graphs into 5-cycles, Australas. J. Combin. 54 (2012) 289–301.
[2] E. J. Billington, Decomposing complete tripartite graphs into cycles of length 3 and 4, Discrete Math. 197/198 (1999) 123–135.
[3] E. J. Billington and N. J. Cavenagh, Decomposing complete tripartite graphs into 5-cycles when the partite sets have similar size, Aequationes Math. 82 (2011), no. 3, 277–289.
[4] E. J. Billington, N. J. Cavenagh and B. R. Smith, Path and Cycle decompositions of complete equipartite graphs: 3 and 5 parts, Discrete Math. 310 (2010), no. 2, 241–254.
[5] N.J. Cavenagh, Decompositions of complete tripartite graphs into k cycles, Australas. J. Combin. 18 (1998) 193–200.
[6] N. J. Cavenagh, Further decompositions of complete tripartite graphs into 5-cycles, Discrete Math. 256 (2002), no. 1-2, 55–81.
[7] N. J. Cavenagh and E .J. Billington, On decomposing complete tripartite graphs into 5-cycles, Australas. J. Combin. 22 (2000) 41–62.
[8] C.-M. Fu, Y.-L. Lin, S.-W. Lo and Y.-F. Hsu, Decomposition of complete graphs into triangles and claws, Taiwanese J. Math. 5 (2014), no. 5, 1563–1581.
[9] S. Ganeshamurthy and P. Paulraja, Decompositions of complete tripartite graphs into cycles of lengths 3 and 6, Australas. J. Combin. 73 (2019) 220–241.
[10] S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math. 331 (2014) 98–108.
[11] C. C. Lindner and C. A. Rodger, Design Theory, 2nd Ed., CRC Press, Boca Raton, 2009.
[12] Mahmoodian and M. Mirzakhani, Decomposition of complete tripartite graphs into 5-cycles, in: Combin. Advances, (Eds.: C.J. Colbourn and E.S. Mahmoodian), Kluwer Academic Publishers, Dordrecht, (1995) 235–241.
[13] S. Priyadarsini and A. Muthusamy, Decomposition of complete tripartite graphs into cycles and paths of length three, Contrib. Discrete Math. 15 (2020), no. 3, 117–129.
[14] T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math. 313 (2013), no. 7, 865–871.
[15] T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Combin. 29 (2013), no. 2, 301–313.
[16] B. R. Smith, Decomposing complete equipartite graphs into cycles of length 2p, J. Combin. Des. 16 (2008), no. 3, 244–252.
[17] D. Sotteau, Decomposition of Km,n (K∗m,n ) into cycles(circuits) of length 2k, J. Combin. Theory Ser. B 30 (1981), 1, 75–81.
Journal of the Iranian Mathematical Society
Volume 5, Issue 2
March 2024
Pages 113-126