The (Strong) Rainbow Connection Number of Join Of Ladder and Trivial Graph

Authors

  • Dinda Kartika Department of Mathematics, Universitas Negeri Medan
  • Didi Febrian Department of Mathematics, Universitas Negeri Medan
  • Nurul Maulida Surbakti Department of Mathematics, Universitas Negeri Medan

DOI:

https://doi.org/10.31764/jtam.v7i1.11704

Keywords:

Rainbow path, Ladder graph, Join, Rainbow connection number,

Abstract

Let G = (V,E) be a nontrivial, finite, and connected graph. A function c from E to {1,2,...,k},k ∈ N, can be considered as a rainbow k-coloring if every two vertices x and y in G has an x- y path. Therefore, no two path's edges receive the same color; this condition is called a “rainbow pathâ€. The smallest positive integer k, designated by rc(G), is the G rainbow connection number. Thus, G has a rainbow k-coloring. Meanwhile, the c function is considered as a strong rainbow k-coloring within the condition for every two vertices x and y in G have an x - y rainbow path whose length is the distance between x and y. The smallest positive integer k, such as G, has a strong rainbow k-coloring; such a condition is called a strong rainbow connection number of G, denoted by src(G). In this research, the rainbow connection number and strong rainbow connection number are determined from the graph resulting from the join operation between the ladder graph and the trivial graph, denoted by rc(L_n∨K_1) and src(L_n∨K_1) respectively. So, rc (L_n∨K_1 )= src (L_n∨K_1 )=2,"for" 3≤n≤4 and rc (L_n∨K_1 )=3, while src(L_n∨K_1 )=⌈n/2⌉,"for" n≥5.

 

References

Basavaraju, M., Chandran, L. S., Rajendraprasad, D., & Ramaswamy, A. (2014). Rainbow Connection Number of Graph Power and Graph Products. Graphs and Combinatorics, 30(6), 1363–1382. https://doi.org/10.1007/s00373-013-1355-3

Chartrand, G., Johns, G. L., Mckeon, K. A., & Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 127(1), 85–98. https://doi.org/10.21136/MB.2008.133947

Chen, L., Li, X., Liu, H., & Liu, J. (2018). On various (strong) rainbow connection numbers of graphs. Australasian Journal of Combinatorics, 70(1), 137–156. https://doi.org/10.48550/arXiv.1601.01063

Chen, X., Li, X., Wang, J., & Fan, N. (2019). The rainbow connectivity of cartesian product graphs. Journal of Discrete Mathematical Sciences and Cryptography, 22(6), 901–914. https://doi.org/10.1080/09720529.2019.1614337

Dafik, D., Agustin, I. H., Wardanai, D. A. R., Kurniawati, E. Y., & Alfarisi, R. (2018). On the Rainbow and Strong Rainbow Coloring of Comb Product Graphs. Acta Mechanica Slovaca, 22(3), 20–26. https://doi.org/10.21496/ams.2018.022

Diestel, R. (2005). Graph Theory. Springer.

Doan, T. D., Ha, P. H., & Schiermeyer, I. (2022). The Conflict-Free Vertex-Connection Number and Degree Conditions of Graphs. Graphs and Combinatorics, 38(5). DOI: 10.1007/s00373-022-02567-y

Fitrianda, S., Yulianti, L., & Narwen. (2018). Rainbow Connection Number dan Strong Rainbow Connection Number pada Graf Tangga Segitiga yang Diperumum. Jurnal Matematika UNAND, VII(1), 136–142. https://doi.org/10.25077/jmu.7.1.125-135.2018

Fitriani, D., & Salman, A. N. M. (2016). Rainbow connection number of amalgamation of some graphs. AKCE International Journal of Graphs and Combinatorics, 13(1), 90–99. https://doi.org/10.1016/j.akcej.2016.03.004

Gembong, A. W., & Agustin, I. H. (2017). The Rainbow ( 1 , 2 ) -Connection Number of Edge Comb Product Graph and It ’ s Lower Bound. 2, 5–6. ISBN: 978-602-60569-5-5

Gologranc, T., Mekiš, G., & Peterin, I. (2014). Rainbow Connection and Graph Products. Graphs and Combinatorics, 30(591–607). https://doi.org/10.1007/s00373-013-1295-y

Kartika, D. (2020). Indeks Pelangi-3 Kuat Graf Hasil Operasi Kali Sisir Titik Graf Tangga Dengan Graf Bintang (L_n ⊳∘ K_(1,r)). Karismatika, 6(3), 1–9. https://doi.org/10.24114/jmk.v6i3.22181

Li, H., Li, X., & Liu, S. (2011). The ( strong ) rainbow connection numbers of Cayley graphs on. Computers and Mathematics with Applications, 62(11), 4082–4088. https://doi.org/10.1016/j.camwa.2011.09.056

Li, H., & Ma, Y. (2017). Rainbow connection number and graph operations. Discrete Applied Mathematics, 230, 91–99. https://doi.org/10.1016/j.dam.2017.06.004

Li, X., & Sun, Y. (2012). Rainbow Connections of Graphs: A Survey. In Graphs and Combinatorics (Vol. 29, Issue 1). SpringerBriefs in Math.Springer. https://doi.org/10.1007/s00373-012-1243-2

Liu, Y. (2014). The Rainbow Connection of Windmill and Corona Graph. 8(128), 6367–6372. http://dx.doi.org/10.12988/ams.2014.48632

Maulani, A., Pradini, S. F. Y. O., Setyorini, D., Sugeng, K. A., Indonesia, F. U., & Ui, K. (2019). Rainbow connection number of C_m⊙P_n and C_m⊙C_n. 3(2), 95–108. https://doi.org/10.19184/ijc.2019.3.2.3

Morris, R., & Thompson, K. (1979). Password Security: A Case History. Communications of the ACM, 22(11): 594-597. https://doi.org/10.1145/359168.359172

Resty, D., & Salman, A. N. M. (2015). The Rainbow Connection Number of an n-Crossed Prism Graph and its Corona Product with a Trivial Graph. Procedia Computer Science, 74, 143–150. https://doi.org/10.1016/j.procs.2015.12.090

Schiermeyer, I. (2011). Bounds For The Rainbow Connection. Discussiones Mathematicae, 31, 387–395. https://doi.org/10.7151/dmgt.1553

Septyanto, F., & Sugeng, K. A. (2017). Rainbow connections of graph joins. Australasian Journal of Combinatorics, 69(3), 375–381. ISSN: 2202-3518

Shulhany, M. A., & Salman, A. N. M. (2016). The (strong) rainbow connection number of stellar graphs. AIP Conference Proceedings, 1708(February 2016). https://doi.org/10.1063/1.4941170

Zhang, L., Tan, C., & Yu, F. (2013). An Improved Rainbow Table Attack for Long Passwords. Procedia Computer Science, 107(2017), 47-52.

https://doi.org/10.1016/j.procs.2017.03.054

Downloads

Published

2023-01-12

Issue

Vol. 7 No. 1 (2023): January

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).