Research Article
BibTex RIS Cite

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

Year 2022, , 29 - 46, 15.01.2022
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.

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.
Year 2022, , 29 - 46, 15.01.2022
https://doi.org/10.13069/jacodesmath.1056547

Abstract

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.
There are 25 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Kaliappan Sowndhariya This is me

Appu Muthusamy This is me 0000-0001-9014-6916

Publication Date January 15, 2022
Published in Issue Year 2022

Cite

APA Sowndhariya, K., & Muthusamy, A. (n.d.). Decomposition of cartesian product of complete graphs into sunlet graphs of order eight. Journal of Algebra Combinatorics Discrete Structures and Applications, 9(1), 29-46. https://doi.org/10.13069/jacodesmath.1056547
AMA Sowndhariya K, Muthusamy A. Decomposition of cartesian product of complete graphs into sunlet graphs of order eight. Journal of Algebra Combinatorics Discrete Structures and Applications. 9(1):29-46. doi:10.13069/jacodesmath.1056547
Chicago Sowndhariya, Kaliappan, and Appu Muthusamy. “Decomposition of Cartesian Product of Complete Graphs into Sunlet Graphs of Order Eight”. Journal of Algebra Combinatorics Discrete Structures and Applications 9, no. 1 n.d.: 29-46. https://doi.org/10.13069/jacodesmath.1056547.
EndNote Sowndhariya K, Muthusamy A Decomposition of cartesian product of complete graphs into sunlet graphs of order eight. Journal of Algebra Combinatorics Discrete Structures and Applications 9 1 29–46.
IEEE K. Sowndhariya and A. Muthusamy, “Decomposition of cartesian product of complete graphs into sunlet graphs of order eight”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 1, pp. 29–46, doi: 10.13069/jacodesmath.1056547.
ISNAD Sowndhariya, Kaliappan - Muthusamy, Appu. “Decomposition of Cartesian Product of Complete Graphs into Sunlet Graphs of Order Eight”. Journal of Algebra Combinatorics Discrete Structures and Applications 9/1 (n.d.), 29-46. https://doi.org/10.13069/jacodesmath.1056547.
JAMA Sowndhariya K, Muthusamy A. Decomposition of cartesian product of complete graphs into sunlet graphs of order eight. Journal of Algebra Combinatorics Discrete Structures and Applications.;9:29–46.
MLA Sowndhariya, Kaliappan and Appu Muthusamy. “Decomposition of Cartesian Product of Complete Graphs into Sunlet Graphs of Order Eight”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 1, pp. 29-46, doi:10.13069/jacodesmath.1056547.
Vancouver Sowndhariya K, Muthusamy A. Decomposition of cartesian product of complete graphs into sunlet graphs of order eight. Journal of Algebra Combinatorics Discrete Structures and Applications. 9(1):29-46.