A Note on Multiset Dimension and Local Multiset Dimension of Graphs
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.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
