Let G = (V, E) be a simple connected graph and W ⊆ V. For v ∈ V, the representation multiset or m-code of v is the multiset rm(v) = {d(v, w) ∣ w ∈ W}. If no two vertices in G have equal m-codes, then W is called an m-resolving set of G. The multiset dimension md(G) of G is the minimum possible cardinality of an m-resolving set of G, if such a set exists. If G does not possess an m-resolving set, then we say that G has infinite multiset dimension. In this paper, we show that all cylindrical graphs Pm ▫ Cn, where m, n ≥ 3, have finite multiset dimension. In particular, we show that md(Pm ▫ Cn) ≤ 4 if m ≥ 6 and n ≥ 3, or if m ≥ 3 and n ≥ 12. Moreover, if m ≥ 3 and n ≥ 8m + 1, we show that Pm ▫ Cn has multiset dimension 3.
Let \(G=(V,E)\) be a connected graph. The distance \(d(u,v)\) between vertices \(u\) and \(v\) in \(G\) is the length of a shortest path that joins \(u\) and \(v\). A subset \(W=\{w_1,w_2,\ldots,w_k\}\subseteq V\) is said to be a resolving set of \(G\) if \[\label{eq:resolving_set_def} \left(d(u,w_1),d(u,w_2),\ldots,d(u,w_k)\right)\ne \left(d(v,w_1),d(v,w_2),\ldots,d(v,w_k)\right),\] for any pair of distinct vertices \(u\) and \(v\) of \(G\). The smallest cardinality of a resolving set \(W\) of \(G\) is called the metric dimension of \(G\). The concepts of resolving set and metric dimension were introduced independently by Slater [14], and Harary and Melter [3]. For works on these concepts and related topics, refer to the survey articles [9] and [15].
Saenpholphat [12] and Simanjuntak et al. [13] independently introduced a stronger version of a resolving set called an m-resolving set. Given a connected graph \(G=(V,E)\) and a vertex \(v\in V\), the representation multiset or m-code \(r_{m}\left(v | W\right)\) (or simply \(r_m(v)\)) of \(v\) with respect to \(W\) is defined to be the multiset of distances between \(v\) and the vertices in \(W\); that is \(r_m(v) =\left\{ d\left( v,w\right) \mid w\in W\right\}\). If no two vertices in \(G\) have equal m-codes, then \(W\) is called an m-resolving set of \(G\). Hence, \(W=\left\{w_1,w_2,\ldots,w_k\right\}\) is an m-resolving set of \(G\) if and only if \[\label{eq:mresolving_set_def} \left\{d(u,w_1),d(u,w_2),\ldots,d(u,w_k)\right\}\ne \left\{(d(v,w_1),d(v,w_2),\ldots,d(v,w_k)\right\},\] for any pair of distinct vertices \(u\) and \(v\) of \(G\).
The multiset dimension \(\text{md}(G)\) of \(G\) is the minimum possible cardinality of an m-resolving set of \(G\), if such a set exists. If \(G\) does not possess an m-resolving set, then we say that \(G\) has infinite multiset dimension; that is, md\((G)=\infty\). If md\((G)\) is finite, then an m-resolving set with cardinality md\((G)\) is called a multiset basis of \(G\).
An m-resolving set of a graph \(G\) induces a vertex ID-coloring [1] of \(G\). Let \(c\) be a red-white coloring of a graph \(G\) that has diameter \(d\). For each vertex \(v\), we construct the \(d\)-vector \(\vec{d}(v) = (a_1, a_2, …, a_d)\), where for each \(i \in \{1,2,…,d\}\), \(a_i\) is equal to the number of red vertices of distance \(i\) from \(v\). Then \(c\) is called an ID-coloring of \(G\) if \(\vec{d}(v) \neq \vec{d}(w)\) for any pair of distinct vertices \(v,w\). Hence, \(c\) is an ID-coloring if and only if the set of vertices colored red is m-resolving.
Various studies on m-resolving sets and multiset dimension of graphs have appeared recently [2, 4, 5, 6, 7, 11, 10].
Some of the known results that are used in the study are enumerated below.
Theorem 1.2([1, 12, 13)A nontrivial connected graph \(G\) has \({md}(G) = 1\) if and only if \(G\) is a path.
For the next result, let \(P_{n}\) be the path \(\left( 0,1,2,\ldots,n-1\right)\) of order \(n\geq4\). We define a symmetric subset \(W\) of \(V(P_n)\) to be one with the property \(i\in W\) if and only if \(n-1-i\in W\), for each \(i\in V(P_n)\).
Lemma 1.3([10]).Let \(n\geq4\). If \(W\subset V\left( P_{n}\right)\) contains \(0\) and \(n-1\) and is not symmetric, then \(W\) is an m-resolving set of \(P_n\).
Theorem 1.4([11]). Let \(n\geq9\) and \(G\) be the cycle \(C_{n}\) with \(V\left( G\right) =\mathbb{Z}_{n} := \{0,1,…,n-1\}\) and \(E\left( G\right)\) consisting of edges \(\left\{ i,i+1\right\}\), for all \(i\), \(0\leq i\leq n-1\), with addition done modulo \(n\). Then \(W=\left\{ 0,\left\lfloor n/4\right\rfloor ,2\left\lfloor n/4\right\rfloor +1\right\}\) is an m-resolving set of \(G\).
Now, let \(W\) be a subset of \(V\) with cardinality \(k\). For any \(v\in V\), we can order the elements of \(r_m(v)\) as \(\mathcal{O} = \left( d_{1}\left( v\right) ,d_{2}\left( v\right) ,\ldots,d_{k}\left( v\right) \right)\), where \(d_{i}\left( v\right) \leq d_{i+1}\left( v\right)\), for \(i=1,2,\ldots,k-1\). For convenience, we also define \(\text{sum}_\ell\left( v\right) =\sum_{i=1}^\ell d_{i}\left( v\right)\); that is, \(\text{sum}_{\ell}\left( v\right)\) is the sum of the first \(\ell\) elements of \(\mathcal{O}\). When \(\ell=k\), we write sum\((v)\) for sum\(_k(v)\). Consequently, we have the following observation, which is an extension of Observation 1 in [11].
Observation 1.5. Let \(G=\left( V,E\right)\) be a connected graph and \(W\) a subset of \(V\) with cardinality \(k\), and \(1\le\ell \le k\). If \(u,v\in V\) with sum\(_\ell\left( u\right) \neq\) sum\(_\ell\left( v\right)\), then \(r_m\left( u\right) \neq\) \(r_m\left( v\right)\).
The next observation gives a sufficient condition for the m-code of a vertex in a subgraph to be equal to the m-code of the same vertex in a larger graph. We use the notation \(d_G(u,v)\) for the distance \(d(u,v)\) in the graph \(G\).
Observation 2.1([11]).Let \(G=(V,E)\) be a connected graph, \(W\subseteq V(G)\), and \(H\) a subgraph of \(G\) that satisfies the following:
1. \(W\subseteq V(H)\)
2. \(d_G(u,w)=d_H(u,w)\) for any \(u\in V(H)\) and \(w\in W\).
Then the m-code of each \(u\in V(H)\) in \(H\) is equal to the m-code of \(u\) in \(G\).
Let \(m\ge 2\) and \(n\ge 3\) be positive integers, and \(G=P_m\ \square \ C_n\). Suppose \[\begin{aligned} V\left( G\right) =&\left\{ \left( i,j\right) \mid0\leq i\leq m-1,0\leq j\leq n-1\right\} ,\text{ and }\\ E\left( G\right) =&\left\{ \left\{ \left( i,j\right) ,\left( i,j+1\right) \right\} \mid0\leq i\leq m-1,0\leq j\leq n-1\right\} \\ & \cup\left\{ \left\{ \left( i,j\right) ,\left( i+1,j\right) \right\} \mid 0\leq i\leq m-2,0\leq j\leq n-1\right\} . \end{aligned}\]
For \(0\le i\le m-1\), we denote by \(C_n(i)\) the cycle induced by \(\{(i,j)\mid 0\le j\le n-1\}\). Similarly, for \(0\le j\le n-1\), we denote by \(P_m(j)\) the path induced by \(\{(i,j)\mid 0\le i\le m-1\}\). Figure 1 shows the graph \(P_3\ \square \ C_5\) with the labels of the vertices.
Kono and Zhang [8] showed that prisms \(P_2\ \square \ C_n\) have a finite multiset dimension if and only if \(n \geq 6\). In [11], we found a multiset basis for the prisms that have finite multiset dimension. In particular, we have the following result that we will use later.
Theorem 2.2([11]). Let \(G=P_{2}\ \square \ C_n\), where \(n \geq 6\). Then \[{md}(G) = \left\{ \begin{array}{rl} 3, & \text{if } n \geq 11, n \neq 13, \\ 4, & \text{if } n = 8, 9, 10, 13, \\ 5, & \text{if } n = 6, 7. \end{array} \right.\]
Moreover, for all \(n \geq 11\), except \(n = 12, 13, 16\), the set \(\left\{ \left(0,0\right),\left(0,\left\lfloor n/4\right\rfloor\right),\left(0,2\left\lfloor n/4\right\rfloor +1\right)\right\}\) is an m-resolving set of \(G\).
We extend an observation made in [11].
Observation 2.3.Let \(G=P_m \ \square \ C_{n}\), and \(W\subseteq V\left( C_{n}\left( 0\right) \right)\) be an m-resolving set of \(C_{n}\left( 0\right)\) with \(k\) elements. Suppose \(1\le i\le m-1\), \(0\le j\le n-1\), \(1\le\ell\le k\), \(w\in W\). Then,
(i) \(d((i,j),w)=d((i-1,j),w)+1\);
(ii) \({sum}_\ell(i,j)={sum}_\ell(i-1,j)+\ell\);
(iii) the m-codes of the vertices of \(C_n(i)\) are distinct.
We state two lemmas that will be used later.
Lemma 2.4. Let \(a_1,a_2,b_1,b_2\) be positive integers such that \(a_1+a_2=b_1+b_2\) and the multisets \(\{a_1,a_1-2,a_2,a_2+1\}\) and \(\{b_1,b_1-2,b_2,b_2+1\}\) are distinct. Then \(\{a_1+1,a_1-1,a_2+1,a_2\}\ne\{b_1+1,b_1-1,b_2+1,b_2\}\).
Proof. Suppose \(a_1,a_2,b_1,b_2\) satisfy the assumptions but not the conclusion. Let \(d=a_1+a_2=b_1+b_2\). For any integer \(x\), let \(M(x)\) be the multiset \(\{x+1,x-1,d-x+1,d-x\}\). Then \(M(a_1)=M(b_1)\). The proof is complete if we can show that \(a_1=b_1\). To do this, we observe that in general, \(M(x)\) can only have the following types.
1: \(d-x+1<x-1\)
2: \(d-x+1=x-1\)
3: \(d-x+1=x\) (and so \(d-x=x-1\))
4: \(d-x+1=x+1\)
5: \(d-x+1=x+2\) (and so \(d-x=x+1\))
6: \(d-x+1>x+2\)
We show that \(M(x)\) can belong only to one type. Among the six types, only Type 1 and Type 6 result in four distinct elements for \(M(x)\). But in Type 1, the two smallest elements differ by 1, while in Type 6, they differ by 2. Among the four remaining types, only Type 3 has the smallest element repeated, and only Type 4 has the largest element repeated. Type 2 and Type 5 have the second smallest element repeated. But in Type 2 (resp., Type 5), the difference between the smallest element and the repeated element is 1 (resp., 2). Since they are equal, both \(M(a_1)\) and \(M(a_2)\) are of the same type; hence, the result follows. ◻
Lemma 2.5. Let \(a_1,a_2,b_1,b_2\) be positive integers such that \(a_1+a_2=b_1+b_2\) and the multisets \(\{a_1,a_1-2,a_2,a_2-1\}\) and \(\{b_1,b_1-2,b_2,b_2-1\}\) are distinct. Then \(\{a_1,a_1-2,a_2,a_2\}\ne\{b_1,b_1-2,b_2,b_2\}\).
Proof.Suppose \(a_1,a_2,b_1,b_2\) satisfy the assumptions but not the conclusion. Let \(d=a_1+a_2=b_1+b_2\). For any integer \(x\), let \(M^\prime(x)\) be the multiset \(\{x,x-2,d-x,d-x\}\). Then \(M^\prime(a_1)=M^\prime(b_1)\). We observe that in general, \(M^\prime(x)\) can only have the following types.
(a) \(d-x<x-2\)
(b) \(d-x=x-2\)
(c) \(d-x=x-1\)
(d) \(d-x=x\)
(e) \(d-x>x\)
We show that \(M^\prime(x)\) can only belong to one type. We observe that among the five types, only Type 2 and Type 4 have an element with multiplicity 3. In Type 2 (resp., Type 4), the repeated element is minimum (resp., maximum) of the multiset. For the remaining types, \(M^\prime(x)\) has exactly three distinct elements. Only Type 3 has the three distinct elements consecutive. In Type 1 (resp., Type 5), the minimum (resp., maximum) element is repeated. ◻
For the first main result, we need two lemmas.
Lemma 3.1. Let \(G=P_m\ \square \ C_n\), \(m\ge 6, n\ge 3\), \(W=\{(0,0),(2,0),(m-1,0),(m-1,1)\}\), \(X=\{(i,j)\mid 0\le i\le m-1, 0\le j\le \lfloor\frac{n}{2}\rfloor\}\), and \(Y=\{(i,j)\mid 0\le i\le m-1, \lceil\frac{n}{2}\rceil+1\le j\le n-1\}\). Then the following hold.
(i) sum\((i,0)=\left\{ \begin{aligned} &2m+1, &&\text{ if } i=0,\\ &2m-1, &&\text{ if } i=1,\\ &2m-3, &&\text{ if }2\le i\le m-1. \end{aligned}\right.\)
(ii) sum\((i,1)=\left\{ \begin{aligned} &2m+3, &&\text{ if } i=0,\\ &2m+1, &&\text{ if } i=1,\\ &2m-1, &&\text{ if }2\le i\le m-1. \end{aligned}\right.\)
(iii) Between any \(u\in X\) and \(w\in W\), there is a shortest path that consists of vertices from \(X\) alone.
(iv) For any \(k,i,w\) with \(2\le k\le \lfloor\frac{n}{2}\rfloor\), \(0\le i\le m-1\), and \(w\in W\), we have \(d((i,k),w)=d((i,k-1),w)+1\). Hence, sum\((i,k)={sum}(i,k-1)+4\).
(v) Between any \(u=(i,k)\in Y\) and \(w\in W\), there exists a shortest path that contains the edge \(\{(i,n-1),(i,0)\}\).
(vi) For any \(k,i,w\) with \(\lceil\frac{n}{2}\rceil+1\le k\le n-1\), \(0\le i\le m-1\), and \(w\in W\), we have \(d((i,k),w)=d((i,k+1),w)+1\) \((\)where vertex \((i,n)\) is the same as \((i,0))\). Hence, sum\((i,k)={sum}(i,k+1)+4\).
Proof. Let us label the vertices in \(W\) as follows: \[w_1=(0,0), w_2=(2,0), w_3=(m-1,0), \text{and } w_4=(m-1,1).\]
We note that, \[r_m(0,0)=\{0,2,m-1,m\},\ r_m(1,0)=\{1,1,m-2,m-1\},\ \text{and }r_m(2,0)=\{2,0,m-3,m-2\},\] so sum\((0,0)=2m+1\), sum\((1,0)=2m-1\), and sum\((2,0)=2m-3\). Now, whenever \(2\le i\le m-2\), we have \(d((i+1,0),w_j)=d((i,0),w_j)+1\), if \(j=1\) or 2; while \(d((i+1,0),w_j)=d((i,0),w_j)-1\), if \(j=3\) or 4. Hence, sum\((i,0)=2m-3\) for each \(i\), \(2\le i\le m-1\). Hence, (i) is proved.
Next, whenever \(0\le i\le m-1\), we have \[\label{eqn:dist_i1_i0} d((i,1),w_k)=d((i,0),w_k)+1 \text{ if }1\le k\le 3\text{, \quad while } d((i,1),w_4)=d((i,0),w_4)-1. \tag{1}\]
Therefore, sum\((i,1)=\text{sum}(i,0)+2\), and so sum\((0,1)=2m+3\), sum\((1,1)=2m+1\), and sum\((i,1)=2m-1\) if \(i\ge 2\), proving (ii).
Let \(0\le i\le m-1\). Property (iii) follows from the fact that for any \(2\le k\le \lfloor\frac{n}{2}\rfloor\), we have \(d((i,k),(i,0))=k\) and \(d((i,k),(i,1))=k-1\). Similarly, (v) is true because whenever \(\lceil\frac{n}{2}\rceil+1\le k\le n-1\), we have \(d((i,k),(i,0))=n-k\) and \(d((i,k),(i,1))=n-k+1\).
Properties (iv) and (vi) are immediate consequences of (iii) and (v), respectively. ◻
Lemma 3.2. Let \(m\ge 6\) and \(W=\{(0,0),(2,0),(m-1,0),(m-1,1)\}\). Then \(W\) is an m-resolving set of \(G=P_m\ \square \ C_3\).
Proof. We define \(w_i, 1\le i\le 4\), as in the proof of Lemma 3.1. Let \(P\) be the path induced by the vertices in \(\{(i,0)\mid 0\le i\le m-1\}\cup\{(m-1,1)\}\). By Lemma 1.3 and Observation 2.1, the vertices of \(P_m(0)\) have distinct codes. We also note that by Lemma 3.1(i), sum\((i,0)=\) \(2m+1\), \(2m-1\), or \(2m-3\), depending on whether \(i=0\), \(1\), or \(i\ge 2\).
We now show that the vertices of \(P_m(1)\) have distinct m-codes. First, by Lemma 3.1(ii), we have sum\((i,1)=\) \(2m+3\), \(2m+1\), or \(2m-1\), depending on whether \(i=0\), \(1\), or \(i\ge 2\). By Observation 1.5, \((0,1)\) and \((1,1)\) have different m-codes, which are both distinct from that of \((i,1)\) for each \(i\ge 2\). To show that the m-codes of \((i,1), 2\le i\le m-1\), are distinct, we use (1) in the proof of Lemma 3.1, the fact that the m-codes of \((i,0), 2\le i\le m-1\) are distinct, and Lemma 2.4. Particularly, Lemma 2.4 is applicable since when \(2 \le i \le m-1\), the following statements hold: \(d((i,0),w_1)+d((i,0),w_3)\) is constant, \(d((i,0),w_2)=d((i,0),w_1)-2\), and \(d((i,0),w_4)=d((i,0),w_3)+1\).
We can show that the m-codes of the vertices in \(V(P_m(2))\) are distinct by following a similar strategy as in \(V(P_m(1))\) and applying Lemma 2.5. For any \(i\), \(0\le i\le m-1\), note that \(d\left((i,2),w_k\right)=d\left((i,1),w_k\right)\), for \(k=1, 2\) or \(3\); while \(d\left((i,2),w_4\right)=d\left((i,1),w_4\right)+1\). For these vertices, note that the sum of the elements of the m-codes are sum\((0,2)=2m+4\), sum\((1,2)=2m+2\), and sum\((i,2)=2m\) for \(i\ge 2\).
We are now left to show that no two vertices \((i,j)\) and \((k,\ell)\), where \(j\ne \ell\), have equal m-codes. By Observation 1.5, it is enough to consider vertices (a) \((0,0)\) and \((1,1)\) that both have sum equal to \(2m+1\), and (b) \((1,0)\) and \((i,1)\), \(i\ge 2\), that have sum \(2m-1\). The m-code of \((0,0)\) has an element 0 while that of \((1,1)\) has none. For (b), \(r_m(1,0)\) contains 1 twice, but none among \((i,1), i\ge 2\), has the same property. ◻
Theorem 3.3. Let \(m\ge 6\) and \(n\ge 3\). Then \(W=\{(0,0),(2,0),(m-1,0),(m-1,1)\}\) is an m-resolving set of \(P_m\ \square \ C_n\). Hence, md\((P_m\ \square \ C_n)\le 4\).
Proof. (By induction on \(n\).) By Lemma 3.2, the statement holds if \(n=3\). Now, suppose the statement holds for some \(n \geq 3\). Let \(H=P_m\ \square \ C_n\); by the inductive assumption, \(W\) is an m-resolving set of \(H\), so the vertices of \(H\) have distinct m-codes. Let the vertices in \(H\) be denoted by \(\left(i,j\right)_H\) for \(0\le i\le m-1, 0\le j\le n-1\). Let us construct \(G=P_m\ \square \ C_{n+1}\) from \(H\) as follows. First, the vertices of \(G\) will be denoted as usual by \(\left(i,j\right)\), where \(0\le i\le m-1, 0\le j\le n\). We split each edge \(\{\left(i,\lfloor\frac{n}{2}\rfloor\right)_H,\left(i,\lfloor\frac{n}{2}\rfloor+1\right)_H\}\), \(0\le i\le m-1\), and insert a new vertex which we denote by \(\left(i,\lfloor\frac{n}{2}\rfloor+1\right)\), and join the new vertices by a path as shown in Figure 3. Then the vertices in \(G\) and \(H\) are related as follows for \(0\le i\le m-1\) and \(0\le j\le n\): \[(i,j)=\left\{ \begin{aligned} &(i,j)_H &&\text{if }0\le j\le\lfloor\textstyle\frac{n}2\rfloor,\\ &(i,j-1)_H &&\text{if }\lfloor\textstyle\frac{n}2\rfloor+2\le j\le n. \end{aligned} \right.\]
Let \(X=\{(i,j)\mid 0\le i\le m-1, 0\le j\le \lfloor\frac{n}{2}\rfloor\}\) and \(Y=\{(i,j)\mid 0\le i\le m-1, \lceil\frac{n}{2}\rceil+2\le j\le n\}\). By Lemma 3.1 (iii) and (v), it follows that the m-codes of \(X\cup Y\subset V(G)\) are distinct.
We define \(w_i, 1\le i\le 4\), as in the proof of Lemma 3.1. We consider two cases depending on the parity of \(n\). First, suppose \(n\) is even. Note that for any \(i\), \(0\le i\le m-1\), we have \[d\left(\left(i,\lfloor\textstyle\frac{n}2\rfloor+1\right),w_k\right)=\left\{ \begin{aligned} &d\left(\left(i,\lfloor\textstyle\frac{n}2\rfloor\right),w_k\right), &&\text{if }1\le k\le 3,\\ &1+d\left(\left(i,\lfloor\textstyle\frac{n}2\rfloor\right),w_k\right), &&\text{if }k=4. \end{aligned} \right.\]
Hence, by Lemma 3.1(iv), \[\text{sum}\left(i,\lfloor\textstyle\frac{n}2\rfloor+1\right)=\left\{ \begin{aligned} &2m+2n, &&\text{if }i=0,\\ &2m+2n-2, &&\text{if }i=1,\\ &2m+2n-4, &&\text{if }2\le i\le m-1. \end{aligned} \right.\]
Hence, for any \(u\in V(H)\), sum\((u)\) is odd, while for any \(v\in V(G\setminus H)\), sum\((v)\) is even; thus, \(u\) and \(v\) have distinct m-codes. Finally, by Lemma 2.5, it follows that no two vertices in \(V(G \setminus H)\) have the same m-code. This completes the proof for the case where \(n\) is even.
Now, suppose \(n\) is odd. In this case, note that \(Y = \{ (i,j)\ |\ 0 \le i \le m – 1, \lfloor\frac{n}{2}\rfloor+3 \le j \le n\}\). By Lemma 3.1, the two largest values of sum\((u)\), for \(u\in X\cup Y\), are \[\text{sum}\left(0,\lfloor\textstyle\frac{n}{2}\rfloor\right)=2m+2n-3,\text{ and } \text{sum}\left(0,\lfloor\textstyle\frac{n}{2}\rfloor+3\right)=\text{sum}\left(1,\lfloor\textstyle\frac{n}2\rfloor\right)=2m+2n-5.\]
Now, for any \(i\), \(0\le i\le m-1\), we have \[d\left(\left(i,\lfloor\frac{n}2\rfloor+1\right),w_k\right)=1+d\left(\left(i,\lfloor\frac{n}2\rfloor\right),w_k\right),\] and \[d\left(\left(i,\lfloor\frac{n}2\rfloor+2\right),w_k\right)=1+d\left(\left(i,\lfloor\frac{n}2\rfloor+3\right),w_k\right),\] for each \(k\), \(1\le k\le 4\). Then the m-codes of \(\left(i,\lfloor\frac{n}2\rfloor+1\right), 0\le i\le m-1\), are distinct. Similarly, the m-codes of \(\left(i,\lfloor\frac{n}2\rfloor+2\right), 0\le i\le m-1\), are distinct. Moreover, from Lemma 3.1, \[\text{sum}\left(i,\lfloor\textstyle\frac{n}2\rfloor+1\right)=\left\{ \begin{aligned} &2m+2n+1, &&\text{if }i=0,\\ &2m+2n-1, &&\text{if }i=1,\\ &2m+2n-3, &&\text{if }2\le i\le m-1, \end{aligned} \right.\] and \[\text{sum}\left(i,\lfloor\textstyle\frac{n}2\rfloor+2\right)=\left\{ \begin{aligned} &2m+2n-1, &&\text{if }i=0,\\ &2m+2n-3, &&\text{if }i=1,\\ &2m+2n-5, &&\text{if }2\le i\le m-1. \end{aligned} \right.\]
In light of Observation 1.5, we can complete the proof by showing that if \(u=(i,j),v=(i^\prime,j^\prime)\in V(G)\) with sum\((u)=\text{sum}(v)\), where \(j=\lfloor\frac{n}2\rfloor+1\) or \(\lfloor\frac{n}2\rfloor+2\), and \(j^\prime\ne j\), then \(u\) and \(v\) have different m-codes. We take cases.
If \(\text{sum}(u)=\text{sum}(v)=2m+2n-1\), then we can take \(u=\left(1,\lfloor\frac{n}2\rfloor+1\right)\) and \(v=\left(0,\lfloor\frac{n}2\rfloor+2\right)\). But \(d_1(v)=\lfloor\frac{n}2\rfloor<d(u,w)\) for any \(w\in W\). So \(r_m(u)\ne r_m(v)\).
If \(\text{sum}(u)=\text{sum}(v)=2m+2n-3\), then \(u,v\in\left\{u_1,u_2,v_1\right\}\), where \(u_1=\left(1,\lfloor\frac{n}2\rfloor+2\right)\), \(u_2=\left(i,\lfloor\frac{n}2\rfloor+1\right)\), for some \(2\le i\le m-1\), and \(v_1=\left(0,\lfloor\frac{n}2\rfloor\right)\). We note that \(d_1(u_1)=d(u_1,w_1)=\lfloor\frac{n}2\rfloor+1=d(u_1,w_2)=d_2(u_1)\). On the other hand, \(d_1(v_1)=d(v_1,w_1)=\lfloor\frac{n}2\rfloor\le d_2(v_1)-2\), so \(r_m(u_1)\ne r_m(v_1)\). If \(d_1(u_2)=d_1(v_1)\), then \(d_1(u_2)=d(u_2,w_4)\) and \(u_2=\left(m-1,\lfloor\frac{n}2\rfloor+1\right)\), so \(d_2(u_2)=d(u_2,w_3)=\lfloor\frac{n}2\rfloor+1\); hence, \(r_m(v_1)\ne r_m(u_2)\). However, if \(d_1(u_2)=d_1(u_1)=\lfloor\frac{n}2\rfloor+1\), then \(u_2=\left(m-2,\lfloor\frac{n}2\rfloor+1\right)\) or \(\left(2,\lfloor\frac{n}2\rfloor+1\right)\). In either case, \(d_2(u_2)>\lfloor\frac{n}2\rfloor+1\), so \(r_m(u_2)\ne r_m(u_1)\).
Finally, if \(\text{sum}(u)=\text{sum}(v)=2m+2n-5\), then \(u=\left(i,\lfloor\frac{n}2\rfloor+2\right)\), for some \(2\le i\le m-1\), and \(v=v_1=\left(0,\lfloor\frac{n}2\rfloor+3\right)\) or \(v=v_2=\left(1,\lfloor\frac{n}2\rfloor\right)\). Note that \(d_1(v_1)=\lfloor\frac{n}2\rfloor-1\) while \(d_1(u)\ge\lfloor\frac{n}2\rfloor\), so \(r_m(u)\ne r_m(v_1)\). Now, \(d_1(v_2)=d_2(v_2)=d(v_2,w_1)=d(v_2,w_2)=\lfloor\frac{n}2\rfloor+1\). If \(d_1(u)=d_1(v_2)\), then \(u=\left(m-2,\lfloor\frac{n}2\rfloor+1\right)\) or \(\left(3,\lfloor\frac{n}2\rfloor+1\right)\). In either case, \(d_2(u)>d_1(u)\), so \(r_m(u)\ne r_m(v_2)\). ◻
In the next two results, we identify cylindrical graphs \(P_m\ \square \ C_n\), where \(m,n\ge 3\), that have multiset dimension equal to 3. The case \(n=3\) has been previously studied in [11].
Theorem 3.4([11]). Let \(m\ge 3\). Then \(W=\{(0,0),(0,1),(2,0)\}\) is a multiset basis of \(P_m\ \square \ C_3\). Hence, md\((P_m\ \square \ C_3)=3\).
Our next result is a generalization of Theorem 2.2.
Theorem 3.5. Let \(G=P_{m}\ \square \ C_{n}\) with \(m\ge 2\) and \(n\ge 8m+1\). Then the set \[W=\left\{ \left(0,0\right),\left(0,\left\lfloor n/4\right\rfloor\right),\left(0,2\left\lfloor n/4\right\rfloor +1\right)\right\},\] is an m-resolving set of \(G\). Hence, md\((G)=3\).
Proof. We use induction on \(m\). By Theorem 2.2, the statement holds when \(m=2\). Let \(m\ge 3\), and suppose the theorem’s statement is true for \(P_{m-1}\ \square \ C_n\), for all \(n\ge 8(m-1)+1\). Let \(G=P_m\ \square \ C_n\).
Let us label the elements of \(W\) as follows: \(w_1=(0,0)\), \(w_2=(0,\ell)\) and \(w_3=(0,2\ell+1)\), where \(\ell=\lfloor\frac{n}4\rfloor\). We construct the following subsets of \(V(C_n(0))\) as shown in Figure 4. In the figure, note that if the vertices are equally spaced along a circle, the location of \((0,2\ell+1)\) relative to \((0,0)\) will change depending on the value of \(n\). The representation shown is when \(n=4\ell\). \[\begin{aligned} A&=\left\{(0,j)\mid 0\le j\le \ell\right\},\\ B&=\left\{(0,j)\mid \ell+1\le j\le 2\ell+1\right\},\\ C&=\left\{(0,j)\mid 2\ell+2\le j\le 2\ell+1+\lfloor\textstyle\frac{n-3\ell-3}{2}\rfloor\right\},\\ D&=\left\{(0,j)\mid 2\ell+2+\lfloor\textstyle\frac{n-3\ell-3}{2}\rfloor\le j\le n-1-\lfloor\textstyle\frac{n-3\ell-2}{2}\rfloor\right\},\\ E&=\left\{(0,j)\mid n-\lfloor\textstyle\frac{n-3\ell-2}{2}\rfloor\le j\le n-1\right\}. \end{aligned}\]
These sets satisfy the following properties:
(a) For any \(w\in A\), sum\(_2(w)=\ell\) and \(d_3(w)=d(w,w_3)\).
(b) For any \(w\in B\), sum\(_2(w)=\ell+1\) and \(d_3(w)=d(w,w_1)\).
(c) For any \(w\in C\), sum\(_2(w)=\ell+1+2h\), where \(1\le h\le \lfloor\frac{n-3\ell-3}{2}\rfloor\), sum\(_2(w)<n-2\ell-1\), \(d_1(w)=d(w,w_3)\), and \(d_3(w)=d(w,w_1)\).
(d) For any \(w\in D\), sum\(_2(w)=n-2\ell-1\) and \(d_3(w)=d(w,w_2)\).
(e) For any \(w\in E\), sum\(_2(w)=\ell+2h\), where \(1\le h\le \lfloor\frac{n-3\ell-2}{2}\rfloor\), sum\(_2(w)<n-2\ell-1\), \(d_1(w)=d(w,w_1)\), and \(d_3(w)=d(w,w_3)\).
Then by inductive assumption, and Observation 2.3, we just need to show that \(r_m(u)\ne r_m(v)\) for all vertices \(u\in V\left(C_n(0)\right))\) and \(v\in V\left(C_n(m-1)\right))\). By Observation 1.5, we may assume that sum\(_2(u)=\text{sum}_2(v)\). By (a)-(e), we have sum\(_2(u)\in\left\{\ell,\ell+1,\ldots,n-2\ell -1\right\}\). By Observation 2.3(ii), \[\text{sum}_2(v)\in \left\{\ell+2(m-1),\ell+1+2(m-1),\ldots,n-2\ell-1+2(m-1)\right\}.\]
We consider cases according to the value of sum\(_2(u)=k\in \left\{\ell+2m-2,\ell+2m-1,\ldots,n-2\ell-1\right\}\). Let us define \(E^\prime\) to consist of the vertices of the form \((m-1,j)\) whenever \((0,j)\in E\). We define \(B^\prime\) and \(C^\prime\) similarly.
If \(k=\ell+2m-2=\ell+2(m-1)\), then \(u=(0,n-(m-1))\in E\) (since \(m-1\le \lfloor\frac{n-3\ell-2}2\rfloor\)) and \(d_1(u)=m-1\). Hence, \(v=v_1=(m-1,0)\) or \(v=v_2=(m-1,\ell)\), both in \(A\). Now, \(d_3(u)=d(u,w_3)=n-(m-1)-(2\ell+1)=n-2\ell-m\), while \(d_3(v_2)=d(v_2,w_3)=(2\ell+1)-\ell+(m-1)=\ell+m\), so \(d_3(u)-d_3(v_2)=n – 3 \ell – 2m>0\). On the other hand, \(d_3(v_1)=d(v_1,w_3)=\min\left((2\ell+1)+m-1,m-1+n-(2\ell+1)\right)\). Hence, \(d_3(v_1)-d_3(u)=\min\left(4\ell+2m-n, 2m-2\right)>0\).
Suppose \(k=\ell+1+2h\) where \(m-1\le h\le \lfloor\frac{n-3\ell-3}{2}\rfloor\) (so \(k<n-2\ell-1\)). Then \(u=(0,2\ell+1+h)\in C\), \(d_1(u)=h\), and \(d_3(u)=d(u,w_1)=n-\left(2\ell+1+h\right)=n-h-2\ell-1\). Now, \(k=\ell+1+2(h-m+1) +2(m-1)\), so \(v=(m-1,2\ell+1+h-m+1)\). Note that \(v\in B^\prime\) if \(h=m-1\), and \(v\in C^\prime\), otherwise. In either case, \(d_3(v)=d(v,w_1)=n-\left(2\ell+1+h-m+1\right)+(m-1)\), so \(d_3(v)-d_3(u)=2m-2>0\).
Suppose \(k=\ell+2h\) where \(m-1< h\le \lfloor\frac{n-3\ell-2}{2}\rfloor\) (so \(k<n-2\ell-1\)). Then \(u=(0,n-h)\in E\), and \(d_3(u)=d(u,w_3)=(n-h)-(2\ell+1)=n-2\ell-h-1\). Since \(k=\ell+2(h-m+1)+2(m-1)\), we have \(v=(m-1,n-(h-m+1))\in E^\prime\). Hence, \(d_3(v)=d(v,w_3)=\left(n-h+m-1\right)-(2\ell+1)+(m-1)=n-2\ell-h+2m-3\), so \(d_3(v)-d_3(u)=2m-2>0\).
Let \(k=n-2\ell-1=\ell+(n-3\ell-1)\). Then \(u\in D\). First, suppose \(n-3\ell-1\) is odd. Then \(k=\ell+1+2\lfloor\frac{n-3\ell-2}2\rfloor=\ell+1+2(m-1)+2\left(\lfloor\frac{n-3\ell-2}2\rfloor-m+1\right)\). Hence, \(v=\left(m-1,2\ell+1+\lfloor\frac{n-3\ell-2}2\rfloor-m+1\right)\in C^\prime\), \(d_1(v)=\lfloor\frac{n-3\ell-2}2\rfloor=1+\lfloor\frac{n-3l-3}2\rfloor\), and \(d_3(v)=d(v,w_1)=n-\left(2\ell+1+\lfloor\frac{n-3\ell-2}2\rfloor-m+1\right)+(m-1)\). On the other hand, we need only to consider when \(u=\left(0,2\ell+1+1+\lfloor\frac{n-3\ell-3}2\rfloor\right)\). Hence, \(d_3(u)=d(u,w_2)=\ell+1+\lfloor\frac{n-3\ell-2}2\rfloor\), and \(d_3(v)-d_3(u)=2m-2>0\).
Now, suppose \(n-3\ell-1\) is even. Then \(k=\ell+2\lfloor\frac{n-3\ell-1}2\rfloor=\ell+2\left(\lfloor\frac{n-3\ell-1}2\rfloor-m+1\right)+2(m-1)\). Hence, \(v=\left(m-1,n-\left(\lfloor\frac{n-3\ell-1}2\rfloor-m+1\right)\right)\in E^\prime\), \(d_1(v)=\lfloor\frac{n-3\ell-1}2\rfloor=1+\lfloor\frac{n-3\ell-2}2\rfloor=1+\lfloor\frac{n-3\ell-3}2\rfloor\). Hence, we need only to consider \(u=u_1=\left(0,n-1-\lfloor\frac{n-3\ell-2}2\rfloor\right)\) or \(u=u_2=\left(0,2\ell+1+1+\lfloor\frac{n-3\ell-3}2\rfloor\right)\). Then \(d_3(u_1)=d(u_1,w_2)=\ell+1+\lfloor\frac{n-3\ell-2}2\rfloor\) while \(d_3(u_2)=d(u_2,w_2)=d_3(u_1)+1\). Now, \(d_3(v)=(m-1)+n-\left(\lfloor\frac{n-3\ell-1}2\rfloor-m+1\right)-2\ell-1\). Therefore, \(d_3(v)-d_3(u_1)>d_3(v)-d_3(u_2)=2m-3>0\).
In all cases, we were able to show that \(r_m(u)\ne r_m(v)\). Therefore, the result follows. ◻
To cover additional cases of \(P_m\ \square \ C_n\) that are not included in the previous results, we have the following theorem.
Theorem 3.6. If \(m\ge 1\) and \(n\ge 12\), then the set \(\left\{(0,0), (0,1), (0,3), \left(0,2\lfloor n/4\rfloor +1+(n \mod 2)\right)\right\}\) is an m-resolving set of \(P_m\ \square \ C_n\).
To prove the theorem, we use the notion of “strong ID-coloring” introduced in [10], which is equivalent to having a “strong” m-resolving set, defined below. Given a multiset \(T\) and an integer \(k\), we denote by \(T+k\) the multiset \(\left\{t+k\mid t\in T\right\}\).
Definition 3.7 ([10]).An m-resolving set \(W\) of a graph \(G\) is strong if for any two distinct vertices \(u\) and \(v\) of \(G\), \(r_m(u)\ne r_m(v)+k\) for any integer \(k\).
Lemma 3.8([10]). Let \(W\) be a strong m-resolving set of \(G\) and \(m\) any positive integer. Then \(W^\prime=\left\{(0,w)\mid w\in W\right\}\) is an m-resolving set of \(P_m\ \square \ G\).
We now define \(\Delta d\)-codes of vertices. Given a graph \(G\) and a set \(W\subset V(G)\) with cardinality \(\ell\), suppose for \(v\in V(G)\), \[r_m(v)=\left\{d_1,d_2,\ldots,d_\ell\right\},\] where \(d_i\le d_{i+1}\) for each \(i\), \(1\le i\le \ell-1\). Let \[\Delta d(v)=[d_2-d_1,d_3-d_2,\ldots,d_\ell-d_{\ell-1}],\] a sequence with \(\ell-1\) entries.
If \(u, v \in V(G)\) and \(r_m(u) = r_m(v) + k\) for some integer \(k\), then it is clear that \(\Delta d(u) = \Delta d(v)\). We have thus shown the following.
Lemma 3.9. Let \(G\) be a graph, \(W\subset V(G)\) such that \(\Delta d(u)\ne \Delta d(v)\) for all distinct \(u,v \in V(G)\). Then \(W\) is a strong m-resolving set of \(G\).
Proof of Theorem 3.6. It is enough to show that the set \(W=\left\{0,1,3, 2\lfloor n/4\rfloor +1+(n \mod 2)\right\}\) is a strong m-resolving set of \(C_n\) using Lemma 3.9. Let \(n=4k+r\), \(0\le r\le 3\). Denote the elements of \(W\) by \(w_i\), \(1\le i\le 4\), arranged in increasing order. Then \(w_4=2k+1\) if \(n\) is even, and \(w_4=2k+2\) if \(n\) is odd.
We identify \(C_n\) with a regular \(n\)-gon in the Euclidean plane as shown in Figure 5. Note that the vertical axis contains the vertex \(1\) if \(r=2\) or \(3\), while it bisects the edge joining vertices \(1\) and \(2\) in the other cases. In each case, we split the vertices of \(C_n\) into four sets: \(A\), \(B\), \(C\), and \(D\). \(B\) and \(C\) have four elements each. The cardinality of \(A\) and \(D\) range from \(2k-4\) to \(2k-2\), depending on \(r\). Note that if \(n=12\) or \(13\), the vertex \(0\) is in \(C\) and \(3\) is in \(B\); they are not in \(A\).
Let \(C=\left\{c_1,c_2,c_3,c_4\right\}\), arranged in increasing order. Note that for any \(r\), \(d(c_1,w_2)=d(c_1,w_1)+1\) and \(d(c_1,w_3)=d(c_1,w_2)+2\). Moreover, if \(r=0\) or \(1\), then \(d(c_1,w_1)=k\) and \(d(c_1,w_4)=k-1\); hence, \(r_m(c_1)= \{k,k+1,k+3,k-1\}\). On the other hand, if \(r=2\) or \(3\), then \(d(c_1,w_1)=k+1\) while \(d(c_1,w_4)=k\), so \(r_m(c_1)=\{k+1,k+2,k+4,k\}\). Therefore, for any \(r\), \(r_m(c_1)=\{a+1,a+2,a+4,a\}\) for some \(a\). And since for any \(i\), \(1\le i\le 3\), \(c_i\) is closer to (resp., farther from) \(w_j\) relative to \(c_{i+1}\) if \(j=4\) (resp., \(j=1,2\), or \(3\)) by one unit, we obtain the following table. \[\begin{array}{c|c|c} u & r_m(u) & \Delta d(u)\\ \hline c_1 & \{a+1,a+2,a+4,a\} &[1,1,2]\\ c_2 & \{a,a+1,a+3,a+1\} & [1,0,2]\\ c_3 & \{a-1,a,a+2,a+2\} & [1,2,0]\\ c_4 & \{a-2,a-1,a+1,a+3\} & [1,2,2] \end{array}\]
Now, let \(B=\{b_1,b_2,b_3,b_4\}\), arranged in increasing order. Then for any \(r\), \(d(b_1,w_1)=d(b_1,w_2)+1\) and \(d(b_1,w_2)=d(b_1,w_3)+2\). If \(r=0\) or \(2\), then \(d(b_1,w_3)=k-3\) and \(d(b_1,w_4)=k+1\). On the other hand, if \(r=1\) or \(3\), then \(d(b_1,w_3)=k-3\) while \(d(b_1,w_4)=k+2\). Following the same argument above, we obtain \(\Delta d(b)\) for any \(b\in B\).
| \(r=0 \text{ or } 2\) | \(r=1 \text{ or } 3\) |
| \(\begin{array}{c|c|c} \hline u & r_m(u) & \Delta d(u)\\ \hline b_1 & \{k,k-1,k-3,k+1\} &[2,1,1]\\ b_2 & \{k+1,k,k-2,k\} & [2,0,1]\\ b_3 & \{k+2,k+1,k-1,k-1\} & [0,2,1]\\ b_4 & \{k+3,k+2,k,k-2\} & [2,2,1] \end{array}\) | \(\begin{array}{c|c|c} \hline u & r_m(u) & \Delta d(u)\\ \hline b_1 & \{k,k-1,k-3,k+2\} & [2,1,2]\\ b_2 & \{k+1,k,k-2,k+1\} & [2,1,0]\\ b_3 & \{k+2,k+1,k-1,k\} & [1,1,1]\\ b_4 & \{k+3,k+2,k,k-1\} & [1,2,1] \end{array}\) |
From the above, we conclude that for any \(r\), the vertices in \(B\cup C\) have distinct \(\Delta d\)-codes. Note also that for any vertex \(u\) in \(B\cup C\), the entries in \(\Delta d(u)\) are all at most 2. To complete the proof, we take cases.
Suppose \(r=0\). Observe that
\[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 0, & \text{if }x=2,\\ 2, & \text{if }3\le x\le k-1,\\ 1, & \text{if }x=0,1,\text{ or } 3k+4\le x\le 4k-1, \end{array}\right.\] while
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 2k-4, &\text{if }x=0,\\ 2k-2, &\text{if }x=1,\\ 2k-2x+1, &\text{if } 2\le x\le k-1,\\ 2x-6k-4, & \text{if } 3k+4\le x\le 4k-1. \end{array} \right.\] From these, we see that vertices in \(A\) have distinct \(\Delta d\)-codes. Recall that if \(k=3\), the vertex \(0\notin A\); also, no vertex \(x\in A\) satisfies \(3k+4\le x\le 4k-1\). Hence, \(d_4(x)-d_3(x)\ge 3\) for each \(x\in A\). It follows that the vertices in \(A\cup B\cup C\) have distinct \(\Delta d\)-codes.
Now, for any \(x\in D\), we have \(d_2(x)\ge d(k+4,3)=k+1\) and \(d_1(x)\le d(3k-1,2k+1)=k-2\), so \(d_2(x)-d_1(x)\ge 3\). Hence, the \(\Delta d\)-codes of \(D\) are distinct from those in \(A\cup B\cup C\). It now remains to show that no two elements of \(D\) have the same \(\Delta d\)-code, which follows from
\[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 2x-2k-4, &\text{if }k+4\le x\le 2k+1,\\ 6k-2x+1, &\text{if }2k+2\le x\le 3k-1. \end{array} \right.\]
Suppose \(r=1\). We can show that no \(\Delta d\)-code is repeated in \(V(C_n)\) using the same argument used in Case 1. We have for \(x\in A\), \[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 0, & \text{if }x=2,\\ 2, & \text{if }3\le x\le k-1,\\ 1, & \text{if }x=0,1, \text{ or } 3k+5\le x\le 4k, \end{array}\right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 2k-4, &\text{if }x=0,\\ 2k-2, &\text{if }x=1,\\ 2k-2x+2, &\text{if } 2\le x\le k-1,\\ 2x-6k-6, & \text{if } 3k+5\le x\le 4k. \end{array} \right.\]
For \(x\in D\),
\[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 2x-2k-5, &\text{if }k+4\le x \le2k+1,\\ 2k-1, &\text{if }x = 2k+2,\\ 6k-2x+3, &\text{if }2k+3\le x\le 3k, \end{array} \right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 1, &\text{if }k+4\le x\le 2k, \text{ or } 2k+2\le x\le 2k+3,\\ 0, &\text{if }x=2k+1,\\ 2, & \text{if }2k+4\le x\le 3k. \end{array}\right.\]
Suppose \(r=2\). As in the previous two cases, the result follows from the following formulas.
For \(x\in A\), \[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 0, & \text{if }x=2,\\ 2, & \text{if }3\le x\le k-1,\\ 1, & \text{if }x=0,1, \text{ or } 3k+5\le x\le 4k+1, \end{array}\right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 2k-2, &\text{if }x=0 \text{ or } 1,\\ 2k-2x+1, &\text{if } 2\le x\le k-1,\\ 2x-6k-6, & \text{if } 3k+5\le x\le 4k+1. \end{array} \right.\] Note that the vertices \(0\) and \(1\) have equal values of \(d_4-d_3\) and \(d_2-d_1\). However, \(d_3(0)-d_2(0)=2\ne 1=d_3(1)-d_2(1)\).
For \(x\in D\), \[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 2x-2k-4, &\text{if }k+4\le x \le2k+1,\\ 6k-2x+3, &\text{if }2k+2\le x\le 3k, \end{array} \right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 1, &\text{if }k+4\le x\le 2k+2,\\ 0, &\text{if }x=2k+3,\\ 2, & \text{if }2k+4\le x\le 3k. \end{array}\right.\]
Suppose \(r=3\). For \(x\in A\), \[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 0, & \text{if }x=2,\\ 2, & \text{if }3\le x\le k-1,\\ 1, & \text{if }x=0,1, \text{ or } 3k+6\le x\le 4k+2, \end{array}\right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 2k-2, &\text{if }x=0,\\ 2k-1, &\text{if }x=1,\\ 2k-2x+2, &\text{if } 2\le x\le k-1,\\ 2x-6k-8, & \text{if } 3k+6\le x\le 4k+2. \end{array} \right.\]
For \(x\in D\),
\[d_2(x)-d_1(x)=\left\{\begin{array}{ll} 2x-2k-5, &\text{if }k+4\le x \le2k+2,\\ 6k-2x+5, &\text{if }2k+3\le x\le 3k+1, \end{array} \right.\] and
\[d_4(x)-d_3(x)=\left\{\begin{array}{ll} 1, &\text{if }k+4\le x\le 2k+1, \text{ or } 2k+3\le x\le 2k+4,\\ 0, &\text{if }x=2k+2,\\ 2, & \text{if }2k+5\le x\le 3k+1. \end{array}\right.\] Note that \(d_4(2k+4) – d_3(2k+4) = 1 = d_4(2k+1) – d_3(2k+1)\) and \(d_2(2k+4) – d_1(2k+4) = 2k-3 = d_2(2k+1) – d_1(2k+1)\), but \(d_3(2k+4) – d_2(2k+4) = 1 \neq 2 = d_3(2k+1) – d_2(2k+1)\).
◻
To cover all cylindrical graphs, we identify m-resolving sets for the following remaining cases of \(n\) when \(3\le m\le 5\):
Hence, we may now state the following result for all cylindrical graphs.
Theorem 3.10. All cylindrical graphs \(P_{m}\ \square \ C_{n}\) \((m,n \geq 3)\) have finite multiset dimension.
With the results of this paper, investigating the multiset dimension of \(P_{m}\ \square \ C_{n}\), for all \(m\geq 1\) and \(n\ge 3\), is nearing completion. \(P_{1}\ \square \ C_{n}\) are cycles and their multiset dimension have been discussed extensively in [1]. For \(P_{2}\ \square \ C_{n}\) (or prisms), the multiset dimension is finite if and only if \(n\geq 6\) [8]. Moreover, the multiset dimensions of such prisms have been previously determined (Theorem 2.2). For \(P_{m}\ \square \ C_{n}\) (\(m,n \geq 3\)) or cylindrical graphs, we obtained m-resolving sets (Theorems 3.3 to Theorem 3.6, and Table 1), proving that the multiset dimension is always finite. In particular, \((G)=3\) for the following cases:
1. \(P_m\ \square \ C_3\) (Theorem 3.4)
2. \(P_{m}\ \square \ C_{n}\), \(n\ge 8m+1\) (Theorem 3.5)
Solving for the multiset dimension of the remaining cases remains an open problem.
| \(n\) | |
|---|---|
| 4,5 | \(\left\{(0,0),(0,1),(0,2),(1,0),(2,1)\right\}\) |
| 6,7 | \(\left\{(0,0),(0,2),(0,4),(1,0),(2,1)\right\}\) |
| 8,10 | \(\left\{(0,0),(0,1),(0,3),(0,5)\right\}\) |
| 9 | \(\left\{(0,0),(0,1),(0,2),(0,4),(0,6)\right\}\) |
| 11 | \(\left\{(0,0),(0,1),(0,3),(0,6)\right\}\) |
Aside from the multiset dimension, we can also consider the ID spectrum, as defined by Chartrand et al. [1]. In addition, the multiset dimension of other families of graphs borne out of other graph operations (e.g., strong direct product, corona) are also suggested for future research.
This work is dedicated to the memory of our beloved colleague and friend, Agnes D. Garciano. This work has been conducted through the LS Scholarly Work Faculty Grant SOSE 06 2023 from the Ateneo de Manila University (ADMU). The authors sincerely thank the Department of Mathematics, the School of Science and Engineering, the Office of the Associate Dean for Research and Creative Work, the University Research Council, and the Office of the Vice President for the Loyola Schools of ADMU for their support in the conduct of this research.