The local metric dimension of split and unicyclic graphs

Dinny Fitriani, Anisa Rarasati, Suhadi Wido Saputro, Edy Tri Baskoro

Abstract


A set W is called a local resolving set of G if the distance of u and v to some elements of W are distinct for every two adjacent vertices u and v in G.  The local metric dimension of G is the minimum cardinality of a local resolving set of G.  A connected graph G is called a split graph if V(G) can be partitioned into two subsets V1 and V2 where an induced subgraph of G by V1 and V2 is a complete graph and an independent set, respectively.  We also consider a graph, namely the unicyclic graph which is a connected graph containing exactly one cycle.  In this paper, we provide a general sharp bounds of local metric dimension of split graph.  We also determine an exact value of local metric dimension of any unicyclic graphs.

Keywords


local basis, local metric dimension, local resolving set, split graph, unicyclic graph

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2022.6.1.3

References

Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak and L.S. Ram, Network discovery and verification, IEEE J. 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, Per. Math. Hung., 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 in 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 (2) (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.

K. Chau and S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math., 37 (4) (2017), 509–534.

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

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.

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.

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

S. Klavzar and S. Zemljic, On distances in Sierpinski 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. Rodriguez-Velazquez, G.A. Barragan-Ramırez, and C.G. Gomez, On the local metric dimension of corona product graphs, Bull. Malays. Math. Sci. Soc., 39 (2013), 157–173.

J.A. Rodriguez-Velazquez, C.G. Gomez, and G.A. Barragan-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. Rodriguez-Velzquez, 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 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.

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

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-Velazquez, On the metric dimension of corona products graphs, Comput. Math. Appl., 61 (9) (2011), 2793–2798.


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

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

View IJC Stats