Graphs with Large Locating Rainbow Vertex Connection Number
Main Article Content
Abstract
The locating rainbow vertex connection number of G, denoted by rvcl(G), is the least positive integer k such that there exists a k-coloring of G that ensures G is rainbow vertex-connected and each vertex has a distinct rainbow code. To learn how this parameter behave in graphs, it is natural to consider the extremal case. In this paper, we investigate several graphs with the difference of its order and its locating rainbow vertex connection number is not larger than three, i.e. rvcl(G) ∈ {n, n − 1, n − 2, n − 3} for graphs of order n.
Furthermore, we demonstrate the existence of a graph with arbitrary large difference of its partition dimension and its locating rainbow vertex connection number. The study provides an overview of some structures that distinguishability under chromatic constraints becomes most costly, as in large number of colors needed.
Article Details
References
[1] F. Anggalia, L. Yulianti, and D. Welyyanti, Batas atas rainbow connection number pada graf Buckminsterfullerene [The upper bound of rainbow connection number of Buckminsterfullerene graph], J. Mat. UNAND, 11(1) (2022), 1–11. DOI: https://doi.org/10.25077/jmu.11.1.111.2022
[2] E. T. Baskoro and D. O. Haryeni, All graphs of order n ≥ 11 and diameter 2 with partition dimension n−3, Heliyon, 6(4) (2020), e03694.
[3] A. W. Bustan, A. N. M. Salman, and P. E. Putri, On the locating rainbow connection number of a graph, In J. Phys.: Conf. Ser. 1764 (2021), 012057.
[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(4) (2023), 1260–1273.
[5] A. W. Bustan, A. N. M. Salman, and P. E. Putri, Determining the locating rainbow connection numbers of vertex transitive graphs, Commun. Comb. Optim., in press. DOI: https://doi.org/10.22049/cco.2025.29742.2137
[6] G. Chartrand, E. Salehi, and P. Zhang, The partition dimension of a graph, Aequationes Math., 59 (2000), 45–54.
[7] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133(1) (2008), 85–98.
[8] C. Darayon and W. Tangjai, Rainbow vertex-connection number on a small-world Farey graph, AKCE Int. J. Graphs Combin., 19(1) (2022), 54–60. DOI: http://dx.doi.org/10.1080/09728600.2022.2057827
[9] D. Fitriani, A. N. M. Salman, and Z. Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory 10(2) (2022), 461–474. DOI: https://dx.doi.org/10.5614/ejgta.2022.10.2.9
[10] F. Harary and R. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
[11] D. O. Haryeni, E. T. Baskoro, and S. W. Saputro, Family of graphs with partition dimension three, Indones. J. Combin., 8(2) (2024), 64–75. DOI: http://dx.doi.org/10.19184/ijc.2024.8.2.1
[12] D. O. Haryeni, M. Ridwan, and E. T. Baskoro, Graphs of order n with partition dimension n − 3, IAENG Int. J. Appl. Math., 53 (2023), no. 1, 152–161.
[13] Haspika, Hasmawati, and N. Aris, The partition dimension on the grid graph, J. Mat. Stat. Komp., 19 (2023), no. 2, 351–358. https://doi.org/10.20956/j.v19i2.23904
[14] M. Imrona, A. N. M. Salman, S. Uttunggadewa, and P. E. Putri, On the locating rainbow connection number of the comb product with complete graphs or trees, In Combin. Graph Theory Comput., 448 (2024), 203–214.
[15] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (atmost) reciprocal to its minimum degree, J. Graph Theory, 63(3) (2009), 195–191.
[16] D. Kuziak and I. G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877v1, 2021.
[17] T. K. Maryati, D. Sobiruddin, and F. F. Hadiputra, On metric dimension of edge comb product of symmetric graphs, J. Mat. UNAND, 13(4) (2024), 349–357.
[18] T. K. Maryati, D. Sobiruddin, M. Fatra, and F. F. Hadiputra, On metric dimension of edge comb product of vertex-transitive graphs, Trans. Combin., 14(1) (2025), 45–64.
[19] K. H. Rosen, Discrete Mathematics and its Applications, McGraw-Hill, NY, 2012.
[20] P. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Comb. Graph Theory Comput., 14 (1975), 549–559.
[21] R. C. Tillquist, R. M. Frongillo, and M. E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev., 65(4) (2023), 919–962.
[22] I. Tomescu, Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math., 308 (2008), 5026–5031.
[23] T. Vetr´ık, M. Imran, M. Knor, and R. ˇSkrekovski, The metric dimension of the circulant graph with 2k generators can be less than k, Journal of King Saud University - Science, 35(7) (2023), 102834. DOI: https://doi.org/10.1016/j.jksus.2023.102834
[24] D. Welyyanti, A. Arsyad, and L. Yulianti, Dimensi metrik amalgamasi graf theta [Metric dimension of amalgamation of theta graphs], Limits: J. Math. Appl., 20(2) (2023), 241–253. DOI: http://dx.doi.org/10.12962/limits.v20i2.16359
[25] N. I. Yahya, A. Fatmawati, Nurwan, and S. K. Nasib, Rainbow vertex connection number on comb product operation of cycle graph C4 and complete bipartite graph K3n, Barekeng: J. Math. Appl., 17(2) (2023), 673–684. DOI: https://doi.org/10.30598/barekengvol17iss2pp0673-0684