Decomposition of cartesian product of complete graphs into sunlet graphs of order eight

Year 2022, Volume: 9 Issue: 1, 29 - 46, 15.01.2022

Kaliappan Sowndhariya Appu Muthusamy

https://doi.org/10.13069/jacodesmath.1056547

Abstract

For any integer $k\geq 3$, we define the sunlet graph of order $2k$, denoted by $L_{2k}$, as the graph consisting of a cycle of length $k$ together with $k$ pendant vertices such that, each pendant vertex adjacent to exactly one vertex of the cycle so that the degree of each vertex in the cycle is $3$. In this paper, we establish necessary and sufficient conditions for the existence of decomposition of the Cartesian product of complete graphs into sunlet graphs of order eight.

Keywords

Graph decomposition, Cartesian product, Corona graph, Sunlet graph

References

• [1] A. D. Akwu, D. O. A. Ajayi, Decomposing certain equipartite graphs into sunlet graphs of length 2p, AKCE Int. J. Graphs Combin. 13(3) (2016) 267–271.
• [2] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20.
• [3] B. Alspach, J. C. Bermond, D. Sotteau, Decomposition into cycles I: Hamilton decompositions, In: Cycles and rays (Montreal, PQ, 1987), Kluwer Academic Publishers, Dordrecht, 301 (1990) 9–18.
• [4] B. Alspach, H. Gavlas, Cycle decompositions of $K_n$ and $K_{n-1}$, J. Combin. Theory Ser. B 81(1) (2001) 77–99.
• [5] R. Anitha, R. S. Lekshmi, N-sun decomposition of complete graphs and complete bipartite graphs, World Acad. Sci. Eng. Tech. 27 (2007) 181–185.
• [6] R. Anitha, R. S. Lekshmi, N-sun decomposition of complete, complete bipartite and some Harary graphs, Int. J. Comput. Math. Sci. 2(7) (2008) 452–457.
• [7] D. Bryant, Cycle decompositions of complete graphs, Surveys in Combinatorics (2007) 67-97, A. Hilton, J. Talbot (Editors), London Math. Soc. Lecture Note Ser., 346, Cambridge Univ. Press, Cambridge (2007).
• [8] D. Bryant, C. A. Rodger, Cycle decompositions, C. J. Colbourn, J. H. Dinitz (Editors), The CRC Handbook of Combinatorial Designs (2nd Edition), CRC Press (2007) 373–382.
• [9] C. M. Fu, M. H. Huang, Y. L. Lin, On the existence of 5-sun systems, Discrete Math. 313(24) (2013) 2942–2950.
• [10] C. M. Fu, N. H. Jhuang, Y. L. Lin, H. M. Sung, From steiner triple systems to 3-sun systems, Taiwanese J. Math. 16(2) (2012) 531–543.
• [11] C. M. Fu, N. H. Jhuang, Y. L. Lin, H. M. Sung, On the existence of k-sun systems, Discrete Math. 312(12-13) (2012) 1931–1939.
• [12] M. Gionfriddo, G. Lo Faro, S. Milici, A. Tripodi, On the existence of uniformly resolvable decompositions of K_v into 1-factors and h-suns, 99 (2016) 331–339.
• [13] A. J. W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin.Theory B, 36(2) (1984) 125–134.
• [14] A. J. W. Hilton, C. A. Rodger, Hamiltonian decompositions of complete regular n-partite graphs, Discrete Math. 58(1) (1986) 63–78.
• [15] Z. Liang, J. Guo, Decomposition of complete multigraphs into crown graphs, J. Appl. Math. Comput. 32 (2009) 507–517.
• [16] Z. Liang, J. Guo, J. Wang, On the crown graph decompositions containing odd cycle, Int. J. Comb. Graph Theory Appl. 2 (2008) 125–160.
• [17] C. Lin, T. W. Shyu, A necessary and sufficient condition for the star decomposition of complete graphs , J. Graph Theory, 23(4) (1996) 361–364.
• [18] M. Sajna, Cycle decompositions III; complete graphs and fixed length cycles, J. Combin. Des. 10(1) (2002) 27–78.
• [19] D. Sotteau, Decomposition of $K_{m,n}(K^{*}_{m,n})$ into cycles (circuits) of length 2k, J. Combin. Theory Ser. B 30(1) (1981) 75–81.
• [20] K. Sowndhariya, A. Muthusamy, Decomposition of product graphs into sunlet graphs of order eight, J. Algebra Comb. Discrete Appl. 8(1) (2021) 43–53.
• [21] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26(3) (1979) 273–278.
• [22] M. Tarsi, Decomposition of complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A, 34(1) (1983) 60–70.
• [23] M. Truszczyński, Note on the decomposition of $\lambda K_{m,n}(\lambda K_{m,n}^{*})$ into paths, Discrete Math. 55(1) (1985) 89-96.
• [24] K. Ushio, S. Tazawa, S. Yamamoto, On claw-decomposition of complete multipartite graphs, Hiroshima Math. J. 8(1) (1978) 207–210.
• [25] S. Yamamoto, H. Ikeda, S. Shige-Eda, K. Ushio, N. Hamada, On claw decomposition of complete graphs and complete bipartite graphs, Hiroshima Math. J. 5(1) (1975) 33-42.