The local metric dimension of amalgamation of graphs

Dinny Fitriani, Suhadi Wido Saputro

Abstract


For any two adjacent vertices u and v in graph G, a set of vertices W locally resolves a graph G if the distance of u and v to some elements of W are distinct. The local metric dimension of G is the minimum cardinality of local resolving sets of G. For n ∈ N and i ∈ {1, 2, …, n}, let Hi be a simple connected graph containing a connected subgraph J. Let H = {H1, H2, …, Hn} be a finite collection of simple connected graphs. The subgraph-amalgamation of H = {H1, H2, …, Hn}, denoted by Subgraph − Amal{H; J}, is a graph obtained by identifying all elements of H in J. The subgraph J is called as a terminal subgraph of H. In this paper, we determine general bounds of the local metric dimension of subgraph-amalgamation graphs for any connected terminal subgraphs. We also determine the local metric dimension of Subgraph − Amal{H; J} for J is either K1 or P2.

Keywords


local basis, local metric dimension, local resolving set, subgraph-amalgamation

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2024.12.1.11

References

G. Abrishami, M.A. Henning, and M. Tavakoli, Local metric dimension for graphs with small clique numbers, Discrete Math. 345 (2022), 112763.

S. Akhter and R. Farooq, Metric dimension of fullerene graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 91–103.

G.A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, and J.A. Rodríguez-Velázquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019), 2481–2496.

G.A. Barragán-Ramírez and J.A. Rodríguez-Velázquez, The local metric dimension of the strong product graphs, Graph Combin. 32 (2016), 1263–1278.

Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalák, and L.S. Ram, Network discovery and verification, IEEE Journal on Selected Areas in Communications 24(12) (2006), 2168–2181.

P.S. Buszkowski, G. Chartrand, C. Poisson, and P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46(1) (2003), 9–15.

J. Caceres, C. Hernando, M. Mora, M.L. Puertas, I.M. Pelayo, C. Seara, and D.R. Wood, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005), 129–133.

J. Caceres, C. Hernando, M. Mora, M.L. Puertas, I.M. Pelayo, C. Seara, and D.R. Wood, On the metric dimension of cartesian product of graphs, SIAM J. Discrete Math. 21(12) (2007), 423–441.

G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graphs, Discrete Appl. Math. 105 (2000), 99–113.

G. Chartrand and P. Zhang, The theory and application of resolvability in graphs, Comput. Math. Appl. 39 (2000), 19–28.

J.A. Cynthia and Ramya, The local metric dimension of torus network, International Journal of Pure and Applied Mathematics 120(7) (2018), 225–233.

M. Fehr, S.Gosselin, and O.R. Oellermann, The metric dimension of Cayley digraphs, Discrete Math. 306 (2006), 31–40.

D. Fitriani, A. Rarasati, S.W. Saputro, E.T. Baskoro, The local metric dimension of split and unicyclic graphs, Indones. J. Combin. 6(1) (2022), 50–57.

W. Goodard, Mastermind revisited, J. Combin. Math. Combin. Comput. 51 (2003), 215–220.

F. Harary and R.A. Melter, On the metric dimension of a graph, Ars. Combin. 2 (1976), 191–195.

C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood, Extremal Graph Theory for Metric Dimension and Diameter, The Electron. J. Combin. 17 (2010), ♯R30.

H. Iswadi, E.T. Baskoro, and R. Simanjuntak, On the metric dimension of corona product of graphs, Far East J. Math. Sci. 52(2) (2011), 155–170.

M. Jannesari and B. Omoomi, Characterization of n-vertex graphs with metric dimension n − 3, Math. Bohem. 134 (2011), 1–23.

S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), 217–229.

S. Klavžar and M. Tavakoli, Local metric dimension of graphs: Generalized hierarchical product and some applications, Appl. Math. Comput. 364 (2020), 124676.

S. Klavžar and S. Zemljic, On distances in Sierpiński graphs: Almost-extreme vertices and metric dimension, Appl. Anal. Discrete Math. 7 (2013), 72–82.

P. Manuel, B. Rajan, I. Rajasingh, and C. Monica M., On minimum metric dimension of honeycomb networks, J. Discrete Algorithms. 6 (2008), 20–27.

F. Okamoto, B. Phinezy, and P. Zhang, The local metric dimension of a graph Math. Bohem., 135 (2010), 239–255.

C. Poisson and P. Zhang, The metric dimension of unicyclic graphs, J. Combin. Math. Combin. Comput. 40 (2002), 17–32.

J.A. Rodríguez-Velázquez, G.A. Barragán-Ramírez, and C.G. Gómez, On the local metric dimension of corona product graphs Bull. Malays. Math. Sci. Soc., 39 (2013), 157–173.

J.A. Rodríguez-Velázquez, C.G. Gómez, and G.A. Barragán-Ramírez, Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs, Comput. Math. 92(4) (2015), 686–693.

J.A. Rodríguez-Velázquez, D. Kuziak, I.G. Yero, and J.M. Sigarreta, The metric dimension of strong product graphs, Carpathian J. Math. 31(2) (2015), 261–268.

S.W. Saputro, On local metric dimension of (n − 3)-regular graph, J. Combin. Math. Combin. Comput. 98 (2016), 43–54.

S.W. Saputro, On the metric dimension of biregular graph, J. Inform. Process. 25 (2017), 634–638.

S.W. Saputro, N. Mardiana, and I.A. Purwasih, The metric dimenison of comb product graphs, Math. Vesnik 69 (2017), 248–258.

S.W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, and E.T. Baskoro, The metric dimension of the lexicographic product of graphs, Discrete Math. 313 (2013), 1045–1051.

B. Shanmukha, B. Sooryanarayana, and K.S. Harinath, Metric dimension of wheels, Far East J. Appl. Math. 8:3 (2002), 217–229.

R. Simanjuntak, S. Uttunggadewa, and S.W. Saputro, Metric dimension for amalgamation of graphs, LNCS 8986 Combin. Algorithms. (2015), 330–337.

P.J. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing., Congr. Numer. 14 (1975), 549–559.

T. Vetrík and A. Ahmad, Computing the metric dimension of the categorial product of some graphs Int. J. Comput. Math., (2015)

I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie 4 (2007), 371–376.

I.G. Yero, D. Kuziak, and J.A. Rodríguez-Velázquez, On the metric dimension of corona products graphs, Comput. Math. Appl. 61:9 (2011), 2793–2798.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats