2017/11/01 by Rinovia Simanjuntak, Simanjuntak, Rinovia, Siagian, Presli +2 · 4 citations
Computer Science · Mathematics · Engineering · #Graph Labeling and Dimension Problems #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1711.00225
We introduce a variation of metric dimension, called the multiset dimension. The representation multiset of a vertex v with respect to W (which is a subset of the vertex set of a graph G), rm (v|W), is defined as a multiset of distances between v and the vertices in W. If rm (u |W) ≠ rm(v|W) for every pair of distinct vertices u and v, then W is called an m-resolving set of G. If G has an m-resolving set, then the cardinality of a smallest m-resolving set is called the multiset dimension of G, denoted by md(G). If G does not contain an m-resolving set, we write md(G) = ∞. In this paper we present basic results on the multiset dimension. We obtain some (sharp) bounds for multiset dimension of arbitrary graphs in term of its metric dimension, order, or diameter. We provide some necessary conditions for a graph to have finite multiset dimension, with an example of an infinite family of graphs where those necessary conditions are also sufficient. We also show that the multiset dimension of any graph other than a path is at least 3 and finally we provide two families of graphs having the multiset dimension 3.