Main Article Content

Abstract

Let G be an arbitrary non-trivial connected graph. An edge-colored graph G is called a rainbow connected if any two vertices are connected by a path whose edges have distinct colors, such path is called a rainbow path. The smallest number of colors required to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). A snowflake graph is a graph obtained by resembling one of the snowflake shapes into vertices and edges so that it forms a simple graph. Let  be a generalized snowflake graph, i.e., a graph with  paths of the stem,  pair of outer leaves,  middle circles, and  pairs of inner leaves. In this paper we determine the rainbow connection number for generalized snowflake graph .

Keywords

rainbow connection number snowflake graph bridges

Article Details

Author Biographies

Lyra Yulianti, Department of Mathematics and Data Science, Faculty of Mathematics and Natural Science (FMIPA), Universitas Andalas, Padang, Indonesia

lecturer in mathematical combinatorics at Andalas University

Des Welyyanti, Department of Mathematics and Data Science, Faculty of Mathematics and Natural Science (FMIPA), Universitas Andalas, Padang, Indonesia

lecturer in mathematical combinatorics at Andalas University

How to Cite
1.
Yulianti L, Fajri MR, Welyyanti D, Nurinsani A. On the Rainbow Connection Number for Snowflake Graph. EKSAKTA [Internet]. 2023Jan.3 [cited 2023Jan.26];24(01):19-2. Available from: https://eksakta.ppj.unp.ac.id/index.php/eksakta/article/view/374

References

  1. Chartrand, G., Johns, G. L., McKeon, K. A., & Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1), 85–98.
  2. Jiang, H., Li, W., Li, X., & Magnant, C. (2021). On proper (strong) rainbow connection of graphs. Discuss. Math. Graph Theory, 41(2), 469-479.
  3. Zhu, X., Wei, M., & Magnant, C. (2021). Generalized Rainbow Connection of Graphs. Bulletin of the Malaysian Mathematical Sciences Society, 44(6), 3991-4002.
  4. Yulianti, L., Nazra, A., Muhardiansyah, & Narwen. (2021). On the rainbow connection number of triangle-net graph. Journal of Physics: Conference Series, 012004.1836, 2021.
  5. Sy, S., Medika, G. H., & Yulianti, L. (2013). The Rainbow Connection of Fan and Sun. Applied Mathematical Sciences, 64th ed.7, HIKARI Ltd: Indonesia, 3155–3159.
  6. Sunil Chandran, L., Issac, D., Lauri, J., & van Leeuwen, E. J. (2022). Upper bounding rainbow connection number by forest number. Discrete Math, 345(7), 112829.
  7. Maulani, A., Pradini, S., Setyorini, D., & Sugeng, K. A. (2020). Rainbow connection number of Cm o Pn and Cm o Cn. Indonesian Journal of Combinatorics, 3(2), 95–108.
  8. Rocha, A., Almeida, S. M., & Zatesko, L. M. (2020). The Rainbow Connection Number of Triangular Snake Graphs. Anais do Encontro de Teoria da Computação (ETC), 65–68.
  9. Fitriani, D., Salman, A., & Awanis, Z. Y. (2022). Rainbow connection number of comb product of graphs. Electronic Journal of Graph Theory and Applications (EJGTA), 10(2), 461–474.
  10. Chen, L., & Al, E. T. (2018). On various (strong) rainbow connection numbers of graphs. Australasian Journal Of Combinatorics, 70(1), 137–156.
  11. Helda Mercy, M., & Annammal Arputhamary, I. (2020). A Study on Strong Rainbow Vertex-Connection in Some Classes of Generalized Petersen Graphs. Procedia Comput Sci, 172, 9–15.
  12. Li, W. jing, Jiang, H., & He, J. bei. (2022). Rainbow and Monochromatic Vertex-connection of Random Graphs. Acta Mathematicae Applicatae Sinica, English Series 2022 38:4, 38(4), 966–972.
  13. Fauziah, D. A., Dafik, Agustin, I. H., & Alfarisi, R. (2019). The rainbow vertex connection number of edge corona product graphs. IOP Conf Ser Earth Environ Sci, 243(1), 012020.
  14. Lima, P. T., van Leeuwen, E. J., & van der Wegen, M. (2021). Algorithms for the rainbow vertex coloring problem on graph classes. Theor Comput Sci, 887, 122–142.
  15. Bai, X. Q., Huang, Z., & Li, X. L. (2022). Bounds for the Rainbow Disconnection Numbers of Graphs. Acta Mathematica Sinica, English Series 2022 38:2, 38(2), 384–396.
  16. Li, X., & Weng, Y. (2021). Further results on the rainbow vertex-disconnection of graphs. Bull. Malays. Math. Sci. Soc., 44(5), 3445–3460.
  17. Chen, X. lin, Li, X. liang, & Lian, H. shu. (2020). Rainbow k-connectivity of Random Bipartite Graphs. Acta Mathematicae Applicatae Sinica, English Series 2020 36:4, 36(4), 879–890.
  18. Bača, M., Salman, A. N. M., Simanjuntak, R., & Susanti, B. H. (2020). Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph. Proceedings - Mathematical Sciences 2020 130:1, 130(1), 1–12.
  19. Hu, Y., & Wei, Y. (2020). Rainbow Antistrong Connection in Tournaments. Graphs and Combinatorics 2020 37:1, 37(1), 167–181.
  20. al Jabbar, Z. L., Dafik, Adawiyah, R., Albirri, E. R., & Agustin, I. H. (2020). On rainbow antimagic coloring of some special graph. J Phys Conf Ser, 1465(1), 012030.
  21. B, S., Dafik, S., H, A. I., & R, A. (2020). On Rainbow Antimagic Coloring of Some Graphs. Journal of Physics: Conference Series ICOPAMBS 2019, 1465, 1–8.
  22. I, K., I, K. A., Dafik, & R, A. (2019). On The Rainbow Antimagic Connection Number of Some Wheel Related Graphs. International Journal of Academic and Applied Research (IJAAR), 12(3), 60–64.
  23. Budi, H. S., Dafik, Tirta, I. M., Agustin, I. H., & Kristiana, A. I. (2021). On rainbow antimagic coloring of graphs. J Phys Conf Ser, 1832(1), 012016.
  24. Joedo, J. C., Dafik, Kristiana, A. I., Agustin, I. H., & Nisviasari, R. (2022). On the rainbow antimagic coloring of vertex amalgamation of graphs. J Phys Conf Ser, 2157(1).
  25. Sulistiyono, B., Slamin, Dafik, Agustin, I. H., & Alfarisi, R. (2020). On rainbow antimagic coloring of some graphs. J Phys Conf Ser, 1465(1).
  26. Septory, B. J., Utoyo, M. I., Dafik, Sulistiyono, B., & Agustin, I. H. (2021). On rainbow antimagic coloring of special graphs. J Phys Conf Ser, 1836(1), 012016.
  27. Rinaldi, G. (2021). Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees. Australasian Journal Of Combinatorics, 80(2), 178–196.
  28. Glock, S., Kühn, D., Montgomery, R., & Osthus, D. (2021). Decompositions into isomorphic rainbow spanning trees. Journal of Combinatorial Theory, Series B, 146, 439-484.
  29. Lu, L., Meier, A., & Wang, Z. (2021). Anti-Ramsey number of edge-disjoint rainbow spanning trees in all graphs. arXiv preprint arXiv:2104.12978.
  30. Li, S., Shi, Y., Tu, J., & Zhao, Y. (2019). On the complexity of k-rainbow cycle colouring problems. Discrete Appl Math (1979), 264, 125–133.
  31. Brause, C., Jendrol’, S., & Schiermeyer, I. (2021). From Colourful to Rainbow Paths in Graphs: Colouring the Vertices. Graphs and Combinatorics 2021 37:5, 37(5), 1823–1839
  32. Babiński, S., & Grzesik, A. (2022). Graphs without a rainbow path of length 3. arXiv preprint arXiv:2211.02308.
  33. Awanis, Z. Y., Salman, A., Saputro, S. W., Bača, M., & Semaničová-Feňovčíková, A. (2020). The strong 3-rainbow index of edge-amalgamation of some graphs. Turkish Journal of Mathematics, 44(2), 446–462.
  34. Awanis, Z. Y., & Salman, A. N. M. (2019). The 3-rainbow index of amalgamation of some graphs with diameter 2. J Phys Conf Ser, 1127(1), 012058.
  35. Hastuti, Y., Agustin, I. H., Prihandini, R. M., & Alfarisi, R. (2019). The total rainbow connection on comb product of cycle and path graphs. IOP Conference Series: Earth and Environmental Science, Vol. 243, No. 1, p. 012114.
  36. Bitterman, A. (2021). The Rainbow Connection: A Time-Series Study of Rainbow Flag Display Across Nine Toronto Neighborhoods. Urban Book Series, 117–137.
  37. Dafik, Sucianto, B., Irvan, M., & Rohim, M. A. (2019). The Analysis of Student Metacognition Skill in Solving Rainbow Connection Problem under the Implementation of Research-Based Learning Model. International Journal of Instruction, 12(4), 593–610.
  38. Eiben, E., Ganian, R., & Lauri, J. (2018). On the complexity of rainbow coloring problems. Discrete Appl Math (1979), 246, 38–48
  39. Fajri, M. R., Fajri, L. H., Ashari, J., Abdurrahman, A., & Arsyad, A. (2022). On the Metric Dimension for Snowflake Graph. EKSAKTA: Berkala Ilmiah Bidang MIPA, 23(04), 275–290.