Local Metric Dimension of Certain Operation of Generalized Petersen Graph
Abstract
A subset W of V(G) is called a local resolving set of G if r(u│W)≠r(v│W) for every two adjacent vertices u,v∈V(G). The smallest cardinality of all local resolving sets in G is called the local metric dimension of G, denoted by lmd(G). The local resolving set of G with cardinality lmd(G) is called a local basis of G. In this paper, we present a novel study, a topic that has not been extensively explored in previous research, on the local metric dimension of certain operation of generalized Petersen graph sP_(n,1) and determine the lower and upper bounds of "lmd(" sP_(n,m)) with n≥3, s≥1, and 1≤m≤⌊(n-1)/2⌋ . We also show that the lower bound is sharp.
Keywords: local resolving set; local metric dimension; generalized Petersen graph.
Abstrak
Suatu subset W dari V(G) dikatakan himpunan pembeda lokal dari G jika r(u│W)≠r(v│W) untuk setiap dua titik bertetangga u,v∈V(G). Kardinalitas terkecil dari semua himpunan pembeda lokal di G disebut dimensi metrik lokal dari G, dinotasikan lmd(G). Himpunan pembeda lokal G dengan kardinalitas lmd(G) disebut basis lokal dari G. Pada artikel ini, disajikan sebuah studi baru, topik yang belum diskplorasi secara ekstensif dalam penelitian sebelumnya, tentang dimensi metrik lokal dari graf hasil operasi tertentu untuk graf Petersen diperumum sP_(n,1) dan menentukan batas atas dan bawah dari lmd(sP_(n,m)) dengan n≥3, s≥1, and 1≤m≤⌊(n-1)/2⌋. Kami juga menunjukkan bahwa batas bawah tersebut tajam.
Kata Kunci: himpunan pembeda local; dimensi metrik local; graf Petersen diperumum.
2020MSC: 05C12, 05C76
Keywords
References
F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Comb., vol. 2, pp. 191–195, 1976.
P. J. Slater, “Leaves of trees,” Proc. 6 th Southeast. Conf. Comb. Graph Theory, Comput. Congr. Numer., vol. 14, pp. 549–559, 1975.
G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discret. Appl. Math., vol. 105, no. 1–3, pp. 99–113, 2000, doi: 10.1016/S0166-218X(00)00198-0.
S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discret. Appl. Math., vol. 70, no. 3, pp. 217–229, 1996, doi: 10.1016/0166-218X(95)00106-2.
J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas, “On the metric dimension of infinite graphs,” Discret. Appl. Math., vol. 160, no. 18, pp. 2618–2626, 2012, doi: 10.1016/j.dam.2011.12.009.
P. Singh, S. Sharma, S. K. Sharma, and V. K. Bhat, “Metric dimension and edge metric dimension of windmill graphs,” AIMS Math., vol. 6, no. 9, pp. 9138–9153, 2021, doi: 10.3934/math.2021531.
S. Batool Pejman, S. Payrovi, and A. Behtoei, “Metric dimension of Andrásfai graphs,” Opusc. Math., vol. 39, no. 3, pp. 415–423, 2019, doi: 10.7494/OpMath.2019.39.3.415.
S. Akhter and R. Farooq, “Metric dimension of fullerene graphs,” Electron. J. Graph Theory Appl., vol. 7, no. 1, pp. 91–103, 2019, doi: 10.5614/ejgta.2019.7.1.7.
S. W. Saputro, D. Suprijanto, E. T. Baskoro, and A. N. M. Salman, “The Metric Dimension of a Graph Composition Products With Star,” J. Indones. Math. Soc., no. October, pp. 85–92, 2012, doi: 10.22342/jims.18.2.114.85-92.
S. W. Saputro et al., “The metric dimension of the lexicographic product of graphs,” Discrete Math., vol. 313, no. 9, pp. 1045–1051, 2013, doi: 10.1016/j.disc.2013.01.021.
S. W. Saputro, N. Mardiana, and I. A. Purwasih, “The metric dimension of comb product graphs,” Mat. Vesn., vol. 69, no. 4, pp. 248–258, 2017.
S. Nawaz, M. Ali, M. A. Khan, and S. Khan, “Computing Metric Dimension of Power of Total Graph,” IEEE Access, vol. 9, pp. 74550–74561, 2021, doi: 10.1109/ACCESS.2021.3072554.
F. Okamoto, B. Phinezy, and P. Zhang, “The local metric dimension of a graph,” Math. Bohem., vol. 135, no. 3, pp. 239–255, 2010, doi: 10.21136/mb.2010.140702.
S. W. Saputro, “On local metric dimension of (n - 3)-regular graph,” J. Comb. Math. Comb. Comput., vol. 98, pp. 43–54, 2016.
R. A. Solekhah and T. A. Kusmayadi, “On the local metric dimension of t-fold wheel, Pn o Km, and generalized fan,” Indones. J. Comb., vol. 2, no. 2, p. 88, 2018, doi: 10.19184/ijc.2018.2.2.4.
C. Yang, X. Deng, J. Liang, and Y. Liu, “On the Local Metric Dimension of Graphs,” J. Interconnect. Networks, vol. 2350033, no. 2023, pp. 1–14, 2024, doi: 10.1142/s0219265923500330.
Marsidi, Dafik, I. H. Agustin, and R. Alfarisi, “On The Local Metric Dimension of Line Graph of Special Graph,” CAUCHY – J. Mat. MURNI DAN Apl., vol. 4, no. 3, pp. 125–130, 2016.
G. A. Barragán-Ramírez and J. A. Rodríguez-Velázquez, “The Local Metric Dimension of Strong Product Graphs,” Graphs Comb., vol. 32, no. 4, pp. 1263–1278, 2016, doi: 10.1007/s00373-015-1653-z.
S. Klavžar and M. Tavakoli, “Local metric dimension of graphs: Generalized hierarchical products and some applications,” Appl. Math. Comput., vol. 364, 2020, doi: 10.1016/j.amc.2019.124676.
C. Yang, X. Deng, and W. Li, “On the Local Metric Dimension of Line Graphs,” J. Interconnect. Networks, no. November, 2023, doi: 10.1142/s0219265923500263.
M. E. Watkins, “A theorem on tait colorings with an application to the generalized Petersen graphs,” J. Comb. Theory, vol. 6, no. 2, pp. 152–164, 1969, doi: 10.1016/S0021-9800(69)80116-X.
I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimension,” Util. Math. , vol. 75, no. SE-Articles, May 2008, [Online]. Available: https://utilitasmathematica.com/index.php/Index/article/view/566.
M. Imran, A. Q. Baig, M. K. Shafiq, and I. Tomecu, “On Metric Dimension of Generalized Petersen Graphs P(n, 3),” Ars Comb., vol. 117, pp. 113–130, 2014.
F. V F and V. Jude Annie Cynthia, “Local Metric Dimension of Families of Certain Graphs,” J. Comb. Inf. Syst. Sci., vol. 42, no. 1, pp. 179–186, 2017.
A. Asmiati, A. A. Aldino, N. Notiragayu, L. Zakaria, and M. Anshori, “Dimensi Metrik Hasil Operasi Tertentu pada Graf Petersen Diperumum,” Limits J. Math. Its Appl., vol. 16, no. 2, p. 87, 2020, doi: 10.12962/limits.v16i2.5594.
DOI: 10.15408/inprime.v7i1.41320
Refbacks
- There are currently no refbacks.
.
