1. Home
  2. Vol 7, No 4 (2023)
  3. Bustan

On the Locating Rainbow Connection Number of Trees and Regular Bipartite Graphs

Ariestha W. Bustan, A. N. M. Salman, Pritta E. Putri, Zata Y. Awanis

Abstract


Locating the rainbow connection number of graphs is a new mathematical concept that combines the concepts of the rainbow vertex coloring and the partition dimension. In this research, we determine the lower and upper bounds of the locating rainbow connection number of a graph and provide the characterization of graphs with the locating rainbow connection number equal to its upper and lower bounds to restrict the upper and lower bounds of the locating rainbow connection number of a graph. We also found the locating rainbow connection number of trees and regular bipartite graphs. The method used in this study is a deductive method that begins with a literature study related to relevant previous research concepts and results, making hypotheses, conducting proofs, and drawing conclusions. This research concludes that only path graphs with orders 2, 3, 4, and complete graphs have a locating rainbow connection number equal to 2 and the order of graph G, respectively. We also showed that the locating rainbow connection number of bipartite regular graphs is in the range of r-⌊n/4⌋+2 to n/2+1, and the locating rainbow connection number of a tree is determined based on the maximum number of pendants or the maximum number of internal vertices.

 

Doi: 10.28991/ESJ-2023-07-04-016

Full Text: PDF


Keywords


Bipartite Regular Graph; Locating Rainbow Connection Number; Rainbow Code; Rainbow Vertex Connection Number; Rainbow Vertex Path; Tree.

References


Mahmoudi, S., & Lotfi, S. (2015). Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem. Applied Soft Computing, 33, 48–64. doi:10.1016/j.asoc.2015.04.020.

Chartrand, G., Johns, G. L., McKeon, K. A., & Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1), 85–98. doi:10.21136/mb.2008.133947.

Ericksen, A. B. (2007). A matter of security. Graduating Engineer & Computer Careers, 24, 28.

Li, X., Shi, Y., & Sun, Y. (2013). Rainbow Connections of Graphs: A Survey. Graphs and Combinatorics, 29(1), 1–38. doi:10.1007/s00373-012-1243-2.

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. doi:10.1016/j.akcej.2016.03.004.

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

Susanti, B. H., Salman, A. N. M., & Simanjuntak, R. (2020). The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths. Electronic Journal of Graph Theory and Applications, 8(1), 145–156. doi:10.5614/EJGTA.2020.8.1.11.

Umbara, R. F., Salman, A. N. M., & Putri, P. E. (2023). On the inverse graph of a finite group and its rainbow connection number. Electronic Journal of Graph Theory and Applications, 11(1), 135–147. doi:10.5614/ejgta.2023.11.1.11.

Fitriani, D., Salman, A. N. M., & Awanis, Z. Y. (2022). Rainbow connection number of comb product of graphs. Electronic Journal of Graph Theory and Applications, 10(2), 461–473. doi:10.5614/ejgta.2022.10.2.9.

Hasan, M. A., Wulandari, R. Y., & Salman, A. N. M. (2022). Rainbow Connection Number of Shackle Graphs. Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021), Jember, Indonesia. doi:10.2991/acsr.k.220202.013.

Krivelevich, M., & Yuster, R. (2010). The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3), 185–191. doi:10.1002/jgt.20418.

Simamora, D. N. S., & Salman, A. N. M. (2015). The Rainbow (Vertex) Connection Number of Pencil Graphs. Procedia Computer Science, 74, 138–142. doi:10.1016/j.procs.2015.12.089.

Li, X., & Liu, S. (2014). Tight upper bound of the rainbow vertex-connection number for 2-connected graphs. Discrete Applied Mathematics, 173, 62–69. doi:10.1016/j.dam.2014.04.002.

Bustan, A. W., & Salman, A. N. M. (2018). The Rainbow Vertex-Connection Number of Star Fan Graphs. CAUCHY: Journal of Pure Mathematics and Applications, 5(3), 112–116. doi:10.18860/ca.v5i3.5516.

Ma, Y., Xue, Y., & Zhang, X. (2023). Proper (Strong) Rainbow Connection and Proper (Strong) Rainbow Vertex Connection of Some Special Graphs. Journal of Interconnection Networks, 2250006. doi:10.1142/s0219265922500062.

Chen, L., Li, X., & Shi, Y. (2011). The complexity of determining the rainbow vertex-connection of a graph. Theoretical Computer Science, 412(35), 4531–4535. doi:10.1016/j.tcs.2011.04.032.

Chen, L., Huo, B., & Ma, Y. (2016). Hardness results for total rainbow connection of graphs. Discussiones Mathematicae - Graph Theory, 36(2), 355–362. doi:10.7151/dmgt.1856.

Chartrand, G., Salehi, E., & Zhang, P. (2000). The partition dimension of a graph. Aequationes Mathematicae, 59(1–2), 45–54. doi:10.1007/PL00000127.

Bustan, A. W., Salman, A. N. M., & Putri, P. E. (2021). On the Locating Rainbow Connection Number of a Graph. Journal of Physics: Conference Series, 1764(1), 12057. doi:10.1088/1742-6596/1764/1/012057.


Full Text: PDF

DOI: 10.28991/ESJ-2023-07-04-016

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Ariestha Widyastuty Bustan, A.N.M. Salman, Pritta Etriana Putri, Zata Yumni Awanis