Decomposition of product graphs into sunlet graphs of order eight

Abstract

For any integer $k\geq 3$ , we define sunlet graph of order $2k$, denoted by $L_{2k}$, as the graph consisting of a cycle of length $k$ together with $k$ pendant vertices, each adjacent to exactly one vertex of the cycle. In this paper, we give necessary and sufficient conditions for the existence of $L_{8}$-decomposition of tensor product and wreath product of complete graphs.

Keywords

• Graph decomposition
• Product graphs
• Corona graph
• Sunlet graph

References

1. [1] A. D. Akwu, D. D. A. Ajayi, Decomposing certain equipartite graphs into Sunlet graphs of length 2p, AKCE Int. J. Graphs Combin. 13 (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, (1990) 9–18.
4. [4] B. Alspach, H. Gavlas, Cycle decompositions of Kn and Kn1, 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) 262-266.
6. [6] R. Anitha, R.S. Lekshmi, N-sun decomposition of complete, complete bipartite and some Harary graphs, Int. J. Comput. Math. Sci. 2 (2008).
7. [7] J. A. Bondy, U. R. S. Murty, Graph theory with applications, The Macmillan Press Ltd, New York (1976).
8. [8] D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics 2007, A. Hilton and J. Talbot (Editors), London Mathematical Society Lecture Note Series 346, Proceedings of the 21st British Combinatorial Conference, Cambridge University Press (2007) 67–97.

9. [9] D. Bryant, C. A. Rodger, Cycle decompositions, C.J. Colbourn, J.H. Dinitz (Eds.), The CRC Handbook of Combinatorial Designs (2nd edition), CRC Press, Boca Raton (2007) 373–382.
10. [10] D. Froncek, Decomposition of complete graphs into small graphs, Opuscula Math. 30(3) (2010) 277–280.
11. [11] C. M. Fu, M. H. Huang, Y. L. Lin, On the existence of 5-sun systems, Discrete Math. 313(24) (2013) 2942–2950.
12. [12] 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.
13. [13] C. M. Fu, N. H. Jhuang, Y. L. Lin, H. M. Sung, On the existence of k-sun systems, Discrete Math. 312 (2012) 1931–1939.
14. [14] M. Gionfriddo, G. Lo Faro, S. Milici, A. Tripodi, On the existence of uniformly resolvable decompositions of K into 1-factors and h-suns, Utilitas Mathematica 99 (2016) 331–339.
15. [15] A. J. W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin.Theory B 36(2) (1984) 125–134.
16. [16] A. J. W. Hilton, C. A. Rodger, Hamiltonian decompositions of complete regular s-partite graphs, Discrete Math. 58 (1986) 63–78.
17. [17] Z. Liang, J. Guo, Decomposition of complete multigraphs into Crown graphs, J. Appl. Math. Comput. 32 (2010) 507–517.
18. [18] Z. Liang, J. Guo, J. Wang, On the Crown graph decompositions containing odd cycle, Int. J. Comb. Graph Theory Appl. 4 (2019) 1–23.
19. [19] C. Lin, T-W Shyu, A necessary and sufficient condition for the star decomposition of complete graphs, J. Graph Theory, 23 (1996) 361–364.
20. [20] R. Frucht, Graceful numbering of wheels and related graphs, Ann. New York Acad. Sci 319 (1979) 219–229.
21. [21] M. Sajna, Cycle decompositions III: Complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27–78.
22. [22] D. Sotteau, Decomposition of Km;n(Km;n) into cycles (circuits) of length 2k, J. Combin. Theory Ser. B 30(1) (1981) 75–81.
23. [23] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Mathematics 26(3) (1979) 273–278.
24. [24] M. Tarsi, Decomposition of complete multigraph into simple paths: Nonbalanced Handcuffed designs, J. Combin. Theory Ser. A 34 (1983) 60–70.
25. [25] M. Truszczynski, Note on the decomposition of Km;n(K m;n) into paths, Discrete Math. 55 (1985)89–96.
26. [26] K. Ushio, S. Tazawa, S. Yamamoto, On claw-decomposition of complete multipartite graphs, Hiroshima Math. J. 8(1) (1978) 207–210.
27. [27] 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.