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

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. [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. [2] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20.
3. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [13] A. J. W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin.Theory B, 36(2) (1984) 125–134.
14. [14] A. J. W. Hilton, C. A. Rodger, Hamiltonian decompositions of complete regular n-partite graphs, Discrete Math. 58(1) (1986) 63–78.
15. [15] Z. Liang, J. Guo, Decomposition of complete multigraphs into crown graphs, J. Appl. Math. Comput. 32 (2009) 507–517.
16. [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. [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. [18] M. Sajna, Cycle decompositions III; complete graphs and fixed length cycles, J. Combin. Des. 10(1) (2002) 27–78.
19. [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. [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. [21] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26(3) (1979) 273–278.
22. [22] M. Tarsi, Decomposition of complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A, 34(1) (1983) 60–70.
23. [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. [24] K. Ushio, S. Tazawa, S. Yamamoto, On claw-decomposition of complete multipartite graphs, Hiroshima Math. J. 8(1) (1978) 207–210.
25. [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.