A Note on Multiset Dimension and Local Multiset Dimension of Graphs

  • Ridho Alfarisi UNIVERSITAS JEMBER
  • Yuqing Lin University of Newcastle
  • Joe Ryan University of Newcastle
  • Dafik Dafik University of Jember
  • Ika Hesti Agustin University of Jember
Keywords: Resolving set, Multiset Dimension, Local Resolving set, Local Multiset Dimension, Cartesian product, Hypercube Graph, Almost Hypercube Graph, Trees

Abstract

All graphs in this paper are nontrivial and connected simple graphs. For a set W = {s1,s2,...,sk} of verticesof G, the multiset representation of a vertex v of G with respect to W is r(v|W) = {d(v,s1),d(v,s2),...,d(v,sk)} whered(v,si) is the distance between of v and si. If the representation r(v|W)̸= r(u|W) for every pair of vertices u,v of a graph G, the W is called the resolving set of G, and the cardinality of a minimum resolving set is called the multiset dimension, denoted by md(G). A set W is a local resolving set of G if r(v|W) ̸= r(u|W) for every pair of adjacent vertices u,v of a graph G. The cardinality of a minimum local resolving set W is called local multiset dimension, denoted by µl(G). In our paper, we discuss the relationship between the multiset dimension and local multiset dimension of graphs and establish bounds of local multiset dimension for some families of graph.

References

J. L. Gross, J. Yellen, and P. Zhang, Handbook of graph Theory Second Edition CRC Press Taylor and Francis Group, 2014.

G. Chartrand and L. Lesniak, Graphs and digraphs 3rd ed (London: Chapman and Hall), 2000.

N. Hartsfield and G. Ringel, Pearls in Graph Theory Academic Press. United Kingdom, 1994.

S. Khuller, B. Raghavachari and A. Rosenfeld, Localization in Graphs, Technical Report CS-Tr-3326, University of Maryland at College Park, 1994.

P. J. Slater, Leaves of trees, in:Proc. 6th Southeast Conf. Comb., Graph Theory, Comput. Boca Rotan, vol. 14, pp 549-559, 1975.

F. Harary and R. A. Melter, On The metric dimension of a graph, Ars Combin, vol. 2, pp 191-195, 1976.

R. Simanjuntak, T. Vetrik and P. B. Mulia, The multiset dimension of graphs, arXiv preprint arXiv:1711.00225, 2017.

R. Alfarisi, Dafik, A. I. Kristiana, I. H. Agustin, Local multiset dimension of graphs, Preprint, 2018.

S. W. Saputro, A. Semanicova-Fenovcikova, M. Baca, M. Lascsakova, On fractional metric dimension of comb product graphs, STATISTICS, OPTIMIZATION AND INFORMATION COMPUTING, vol.6, pp. 150-158, 2018.

R. Adawiyah, Dafik, I. H. Agustin, R. M. Prihandini, R. Alfarisi and E. R.Albirri, On the local multiset dimension of m-shadow graph, Journal of Physics: Conference Series, vol. 1211, p. 012006, 2019.

R. Adawiyah, Dafik, I. H. Agustin, R. M. Prihandini, R. Alfarisi and E. R.Albirri, The local multiset dimension of unicyclic graph, IOP Conference Series: Earth and Environmental Science, vol. 243, p. 012075, 2019.

Published
2020-09-24
How to Cite
Alfarisi, R., Lin, Y., Ryan, J., Dafik, D., & Agustin, I. H. (2020). A Note on Multiset Dimension and Local Multiset Dimension of Graphs. Statistics, Optimization & Information Computing, 8(4), 890-901. https://doi.org/10.19139/soic-2310-5070-727
Section
Research Articles