Novi H. Bonga , Yuqing Linb
aDepartment of Mathematical Sciences, University of Delaware, Newark, DE, USA bSchool of Electrical Engineering and Computing, The University of Newcastle, Australia
nhbong@udel.edu, yuqing.lin@newcastle.edu.au
The multiset dimension was introduced by Rinovia Simanjuntak et al. as a variation of metric dimension. In this problem, the representation of a vertex v with respect to a resolving set W is expressed as a multiset of distances between v and all vertices in W, including their multiplicities. The multiset dimension is defined to be the minimum cardinality of the resolving set. Clearly, this is at least the metric dimension of a graph. In this paper, we study the properties of the multiset dimension of graphs.
Keywords: multiset dimension, distance metric dimension, upper bound
Mathematics Subject Classification: 05C35
DOI: 10.5614/ejgta.2021.9.1.19
1. Introduction
Let G(V, E) be a simple connected graph. The distance between two vertices u, v ∈ V (G), denoted by d(u, v), is the length of the shortest path between them. A vertex w ∈ V (G) resolves a pair of vertices u, v if d(u, w) 6= d(v, w). For an ordered set of k vertices W = {w1, w2, . . . , wk}, the representation of distances of a vertex v with respect to W is the ordered k-tuple
\[r(v|W) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k)).\]
A set of vertices W ⊆ V (G) is a resolving set of G if every two vertices of G have distinct representation with respect to W. A smallest resolving set is called a metric basis and its cardinality
Received: 5 April 2020, Revised: 12 February 2021, Accepted: 3 March 2021.
is called the metric dimension. This metric dimension was introduced by Slater [7], also independently by Harary and Melter [4]. It has some applications in chemistry [2] or in combinatorial optimization [5], etc. Metric dimension of some particular family of graphs has also been studied, for example, for circulant and Harary graphs [3], for fullerene graphs [1], and many more.
A new variant of metric dimension was introduced by Simanjuntak et al. [6], where the representation of distances of a vertex v with respect to W is expressed in terms of a multiset, instead of the ordered tuple. In multiset dimension, given a set W ⊆ V , the representation of a vertex v with respect to a set W is expressed as a multiset of distances between v and all vertices in W, including their multiplicities. The set W ⊆ G is said to be resolving set of G if any pair of vertices of G have distinct representations. Formally, the multiset dimension is defined as follows.
Definition 1.1. Let G be a simple and connected graph with vertex set V (G). Suppose that W is a subset of V (G) and v is a vertex of G. The representation multiset of v with respect to W, rm(v | W), is defined as a multiset of distances between v and the vertices in W together with their multiplicities. If rm(u | W) 6= rm(v | W) for every pair of distinct vertices u and v, then W is called a resolving set of G. A resolving set having minimum cardinality is called a multiset basis. If G has a multiset basis, then its cardinality is called the multiset dimension of G, denoted by md(G). If G does not contain a multiset basis, we say that G has an infinite multiset dimension and we write md(G) = ∞.
Simanjuntak et al. [6] showed that the only graphs with multiset dimension 1 are paths and there is no graph with multiset dimension 2. Therefore, any graph other than a path has multiset dimension at least 3. Figure 1 shows an example of a graph of multiset dimension 3.
Figure 1. An example of a graph with multiset dimension 3.
2. Main results
Let G1 and G2 be simple and connected graphs where |V (G2)| < |V (G1)| or |E(G2)| < |E(G1)|. The multiset dimension of G2 is not necessary less than the multiset dimension of G1, even when G2 is a subgraph of G1.
Theorem 2.1. The multiset dimension is not monotonic.
Proof. A graph that has less vertices does not necessary to have less multiset dimension. We are going to give an example of two graphs G1 and G2 where |V (G1)| > |V (G2)| but md(G1) < md(G2). Observe the following graph G1 of 13 vertices. Let a cherry be a vertex that is connected to two leaves. In order to distinguish the representation of these two leaves, one of them has to be included in the resolving set. Since this graph has 3 cherries where one of its leaves in each cherry has to be included in the resolving set (represented by red vertices), then the multiset dimension of this graph is at least 3. Figure 1 showed that this graph indeed has multiset dimension 3.
Figure 2. Graph G1 with 13 vertices and md(G1) = 3.
Figure 3 shows a graph with one less vertex. Since it still contains 3 cherries, then the multiset dimension is at least 3. However, it is insufficient for this particular graph, because the two vertices indicated in blue now have the same representation. Therefore, one of the blue vertex has to be included in resolving set. The multiset dimension will be at least 4.
Figure 3. Graph G2 with 12 vertices and md(G2) = 4.
Similarly, a graph with less number of edges can have a larger multiset dimension.
Figure 4. Graph G3 with 12 edges and md(G3) = 3 and graph G4 with 11 edges and md(G4) = 4.
Charles Delorme in his correspondence with Simanjuntak [6], mentioned the possibility of a graph having the infinite multiset dimension if it has too many symmetries. However, this is not a necessary condition.
Lemma 2.1. There exists an asymmetric graph with multiset dimension equals infinity.
Proof. The following graph is an asymmetric graph on 6 vertices. There is no set of vertices that can resolve this graph, hence, its multiset dimension equals ∞.
Theorem 2.2. Given any positive integer m ≥ 3, there exists a simple graph whose multiset dimension equals m.
Proof. We give a recursive construction of the graphs with multiset dimension m. Let Gm in this construction be a graph of multiset dimension m. The base graph is the graph G3 shown in Figure 1 with multiset dimension 3. To obtain G4, we identify the left most vertex of the subgraph shown in Figure 5(a) to the last vertex of the main path of G3. In general, we obtain Gk+1 by identifying the left most vertex of a subgraph shown in Figure 5(b) to the last vertex on the main path of the graph Gk. The leaf in red will be in the resolving set of the final graph. Clearly, the constructed graph will have multiset dimension no smaller than m, as there are m pairs of leaf nodes in the graph. To see that the multiset dimension of the constructed graph is indeed equal to m, we first examine the presentations for all vertices on the main path of the constructed graph, it is straightforward to see the representations are different, as in each iteration, the path added has different length. And it is easy to verify the leaf node will be resolved by the neighbour leaf node.
Figure 5. (a) Additional subgraph from G3 to G4; (b) Additional subgraph from Gm to Gm+1.
Figure 6 shows examples of graphs with multiset dimension 3 and 4 while Figure 7 gives an example of the same construction of graph, with multiset dimension 5.
2.1. Graphs of multiset dimension 3
In this section, we focus on the graph that has multiset dimension 3. Let G be a graph on n vertices of diameter k. Let W = {w1, w2, w3} ⊆ V be a resolving set. The representation of vertex v ∈ V \W with respect to W will be in the form of {1 x1 , 2 x2 , . . . , kxk }, where x1+x2+. . .+xk = 3.
Figure 6. Graphs \(G_3\) and \(G_4\).
Figure 7. Graph \(G_5\)
Observation 2.1. The distance of a vertex in a resolving set W to the other two vertices in W has to be distinct. In other words, for \(r, s, t \in \{1, 2, 3\}\) and \(r \neq s \neq t\), \(d(w_r, w_s) \neq d(w_r, w_t)\).
If \(d(w_1, w_2) = d(w_1, w_3) = 1\), then \(d(w_2, w_3) \le 2\). In this case, at most 2 distinct representations are available for these 3 vertices, that is (0, 1, 1), (0, 1, 2) which by pigeonhole principle, at least two of them have to be the same.
Theorem 2.3. If G is a graph on n vertices of diameter k with multiset dimension 3, then
\[n \le \frac{k^3 + 3k^2 + 2k + 12}{6}\]
and this bound is the best possible.
Proof. From the observation we know that (0,1,1) cannot be a representation of any vertex in a graph of multiset dimension 3. Similarly, the representation (1,1,1) cannot exist for any vertex in the graph.
The representation of vertex \(v \in V\) outside the resolving set W with respect to W will be in the form of \(\{1^{x_1}, 2^{x_2}, \dots, k^{x_k}\}\), where \(x_1 + x_2 + \dots + x_k = 3\). The number of solutions to this equation is \(\binom{k+2}{k-1} = \frac{k^3 + 3k^2 + 2k}{6}\). Since (1,1,1) should be excluded, then the maximum number of possible representations for vertices outside the resolving set is
\[\frac{k^3 + 3k^2 + 2k}{6} - 1.\]
Since there are n-3 vertices outside the resolving set, then
\[\frac{k^3 + 3k^2 + 2k}{6} - 1 \ge n - 3.\]
Therefore,
\[n \le \frac{k^3 + 3k^2 + 2k}{6} - 1 + 3 = \frac{k^3 + 3k^2 + 2k + 12}{6}.\]
This bound is sharp. The equality is achieved by the graph in Figure 8.
Figure 8. Graphs on 12 vertices of diameter 3 with multiset dimension 3.
3. Open problems
This research area has a lot more to be explored. Here are some open problems:
Problem 1. Find the necessary and sufficient conditions for a graph to have multiset dimension 3.
Problem 2. Does there exist graph on n vertices with multiset dimension equals n? Find the necessary and sufficient conditions for this to happen.
Problem 3. Study the algebraic properties of graphs and their relation to the multiset dimension.
References
- [1] S. Akhter and R. Farooq, Metric dimension of fullerene graphs, Electron. J. Graph Theory Appl., 7 (1) (2019), 91–103.
- [2] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99–113.
- [3] C. Grigorious, P. Manuel, M. Miller, B. Rajan, and S. Stephen, On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014), 47–54.
- [4] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191– 195.
- [5] A. Sebo and E. Tannier, On metric generators of graphs, ¨ Math. Oper. Res. 29 (2) (2004), 383–393.
- [6] R. Simanjuntak, T. Vetr´ık, and P. B. Mulia, The Multiset Dimension of Graphs, submitted, https://arxiv.org/pdf/1711.00225.pdf
- [7] P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.