Determining the locating rainbow connection numbers of vertex-transitive graphs

Articles in Press

Document Type : Original paper

Authors

1 Mathematics Department, Faculty of Mathematics and Natural Sciences, Universitas Pasifik Morotai, Kabupaten Pulau Morotai, Indonesia

2 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

Abstract

The locating rainbow connection number of a graph is defined as the minimum number of colors required to color vertices such that for every two vertices there exists a rainbow vertex path and every vertex has a distinct rainbow code. This rainbow code signifies a distance between vertices within a given set of colors in a graph. This paper aims to determine the locating rainbow connection number for vertex-transitive graphs. Three main theorems are derived, focusing on the locating rainbow connection number for cycles, $(n-2)$-regular graphs, and complement of cycles $\overline{C_n}$.

Keywords

Main Subjects

References

[1] A.W. Bustan and A.N.M. Salman, The rainbow vertex-connection number of star fan graphs, CAUCHY: Jurnal Matematika Murni dan Aplikasi 5 (2018), no. 3, 112–116.  https://doi.org/10.18860/ca.v5i3.5516
[2] A.W. Bustan, A.N.M. Salman, and P.E. Putri, On the locating rainbow connection number of a graph, J. Phys. Conf. Ser. 1764 (2021), no. 1, Article ID: 012057.  https://doi.org/10.1088/1742-6596/1764/1/012057
[3] A.W. Bustan, A.N.M. Salman, and P.E. Putri, On the locating rainbow connection number of amalgamation of complete
graphs, J. Phys. Conf. Ser. 2543 (2023), no. 1, Article ID: 012004.  https://doi.org/10.1088/1742-6596/2543/1/012004
[4] A.W. Bustan, A.N.M. Salman, P.E. Putri, and Z.Y. Awanis, On the locating rainbow connection number of trees and regular bipartite graphs, Emerg. Sci. J. 7 (2023), no. 4, 1260–1273. https://doi.org/10.28991/ESJ-2023-07-04-016
[5] G. Chartrand, D. Erwin, M.A. Henning, P. J. Slater, and P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl 36 (2002), 89 –101.
[6] W.K. Chiang and R.J. Chen, The $(n, k)$-star graph-a generalized star graph, Inform. Process. Lett. 56 (1995), no. 5, 259–264.  https://doi.org/10.1016/0020-0190(95)00162-1
[7] A.B. Ericksen, A matter of security, Graduating Engineer & Computer Careers 24 (2007), 28.
[8] D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2022), no. 2, p461  https://doi.org/10.5614/ejgta.2022.10.2.9
[9] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010), no. 3, 185–191. https://doi.org/10.1002/jgt.20418
[10] I.S. Kumala and A.N.M. Salman, The rainbow connection number of a flower $(C_m, K_n)$ graph and a flower $(C_3, F_n)$ graph, Procedia Comput. Sci. 74 (2015), 168–172. https://doi.org/10.1016/j.procs.2015.12.094
[11] X. Li and S. Liu, Tight upper bound of the rainbow vertex-connection number for 2-connected graphs, Discrete Appl. Math. 173 (2014), 62–69.  https://doi.org/10.1016/j.dam.2014.04.002
[12] S. Nabila and A.N.M. Salman, The rainbow connection number of origami graphs and pizza graphs, Procedia Comput. Sci. 74 (2015), 162–167.  https://doi.org/10.1016/j.procs.2015.12.093
[13] D.N.S. Simamora and A.N.M. Salman, The rainbow (vertex) connection number of pencil graphs, Procedia Comput. Sci. 74 (2015), 138–142.  https://doi.org/10.1016/j.procs.2015.12.089
[14] B.H. Susanti, A.N.M. Salman, and R. Simanjuntak, The rainbow 2-connectivity of cartesian pro-ducts of 2-connected graphs and paths, Electron. J. Graph Theory Appl. (EJGTA) 8 (2020), no. 1, 145–156. https://dx.doi.org/10.5614/ejgta.2020.8.1.11
[15] R.F. Umbara, A.N.M. Salman, and P.E. Putri, On the inverse graph of a finite group and its rainbow connection number, Electron. J. Graph Theory Appl. 11 (2023), no. 1, 135–147. https://doi.org/10.5614/ejgta.2023.11.1.11
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 15 February 2025

Files

Share

How to cite

Statistics