Local multiset dimension of comb product of tree graphs

1.   Introduction

One of the topics in distances in graphs is the resolving set problem. This topic has many applications in science and technology namely the application of resolving set problems can be found in network infrastructure, navigation robots, chemistry structures, and computer science. The application of metric dimension in networks is one of the described navigation robots. Each place is called the vertex and the connections between vertex are called edges. The minimum number of robots is required for each location and the vertex of some networks is called resolving set problems, for more detail this application is in ^[1].

All graphs G are simple and connected graphs. We have the vertex set and edge set, respectively are $V\left(G\right)$ and $E\left(G\right)$. The distance of $u$ and $v$ and denoted by $d(u, v)$ is the length of the shortest path of the vertices $u$ to $v$. For the set $W = \left\{{s}_{1}, {s}_{2}, ..., {s}_{k}\right\}\subset V\left(G\right)$. The vertex representations of the vertex $x$ to the set $W$ is an ordered $k$-tuple, $r\left(x\right|W) = (d(x, {s}_{1}), d(x, {s}_{2}), ..., d(x, {s}_{k}))$. The set $W$ is called the resolving set of $G$ if every vertex of $G$ has different vertex representations. The resolving set having minimum cardinality is called basis and its cardinality is called the metric dimension of $G$ and denoted by $dim\left(G\right)$ by ^[2]. Okamoto et al ^[3] introduced a new variant of resolving set problems which are called local resolving set problems. In his paper its concept is called local multiset dimension of graphs $G$. The set $W$ is called a local resolving set if $\forall xy\in E\left(G\right), r\left(x|W\right)\ne r\left(y\right|W)$. The local resolving set having minimum cardinality is called local basis and its cardinality is called the local metric dimension of $G$ and denoted by $ldim\left(G\right)$.

Simanjuntak et al. ^[4] introduced the multiset dimension of graphs $G$. Suppose the set $= \left\{{s}_{1}, {s}_{2}, \dots , {s}_{k}\right\}\subset V\left(G\right)$, the vertex representations of a vertex $x\in V\left(G\right)$ to the set $W$ is the multiset, ${r}_{m}\left(x\right|W) = \{d(x, {s}_{1}), d(x, {s}_{2}), \dots , d(x, {s}_{k})\}$ where $d(x, {s}_{i})$ is the length of the shortest path of the vertex $x$ and the vertex in $W$ together with their multiplicities. The set $W$ is called an $m$-resolving set if $\forall xy\in E\left(G\right), {r}_{m}\left(x|W\right)\ne {r}_{m}\left(y\right|W)$. If $G$ has an $m$-resolving set, then an $m$-resolving set having minimum cardinality is called a multiset basis and its cardinality is called the multiset dimension of graphs $G$ and denoted by $md\left(G\right)$ and we say that $G$ has an infinite multiset dimension and we write $md\left(G\right) = \infty$.

Alfarisi et al. ^[5] defined a new notion based on the multiset dimension of $G$, namely a local multiset dimension. Suppose the set $= \left\{{s}_{1}, {s}_{2}, \dots , {s}_{k}\right\}\subset V\left(G\right)$, the vertex representations of a vertex $x\in V\left(G\right)$ to the set $W$ is ${r}_{m}\left(x\right|W) = \{d(x, {s}_{1}), d(x, {s}_{2}), \dots , d(x, {s}_{k})\}$. The set $W$ is called a local $m$-resolving set of $G$ if ${r}_{m}\left(v|W\right)\ne {r}_{m}\left(u\right|W)$ for $uv\in E\left(G\right)$. The local $m$-resolving set having minimum cardinality is called the local multiset basis and its cardinality is called the local multiset dimension and denoted by $m{d}_{l}\left(G\right)$ and we say that $G$ has an infinite local multiset dimension and we write $m{d}_{l}\left(G\right) = \infty$. Alfarisi et al. ^[6] determined multiset dimension problems of almost hypercube graphs.

We have some results on the local multiset dimension of some known graphs namely path, star, tree, and cycle and also the local multiset dimension of graph operations namely, cartesian product ^[6], m-shadow graph ^[7], and some related cycles ^[8]. Adawiyah et al. ^[9] also studied the local multiset dimension of unicyclic graphs. There are some results used for proving the other results as follows.

Lemma 1. ^[10] Let $G$ be a connected graph and $W\subset V\left(G\right)$. If $W$ contains a resolving set of $G$, then $W$ is a resolving set of $G$.

Proposition 1. ^[11] A graph is bipartite if and only if it contains no odd cycle.

Proposition 2. ^[12] The local multiset dimension of $G$ is one if and only if $G$ is a bipartite graph.

Proposition 3. ^[12] If $T$ is a tree graph with order $n$, then $m{d}_{l}\left(T\right) = 1$.

Definition 1. ^[13] Let $G$ and $H$ be two connected graphs. Let $o$ be a vertex of $H$. The comb product of $G$ and $H$, denoted by $G⊳H$, is a graph obtained by taking one copy of $G$ and $\left|V\right(G\left)\right|$ copies of $H$ and identifying the $i-$th copy of $H$ at the vertex $o$ with the $i-th$ vertex of $G$.

Lemma 2. Let $G$ and $H$ be a connected graph. Graph $G⊳H$ is a bipartite graph if and only if $G$ and $H$ is a bipartite graph.

2.   Results

In this section, we investigated the local multiset dimension of the graph resulting of the comb product of tree and cycle. We have determined the bounds and the exact value of the local multiset dimension of the comb product of the tree and cycle.

Lemma 3. Let $T$ be a tree graph and ${C}_{m}$ be a cycle graph for $m\ge 4$. Then

Proof. The comb product of tree graph $T$ with order $n$ and cycle ${C}_{m}$ for $m\ge 3$, denoted by $T⊳{C}_{m}$. This graph has a backbone and leaves where a backbone is tree graph $T$ and leaves are the subgraph cycle (cycle leaves) such that we have $n$-cycle leaves. The graph $T⊳{C}_{m}$ has $V(T⊳{C}_{m}) = \{{v}_{i, j};i\in [1, n]$ and $j\in [1, m]\}$ and $E\left(T⊳{C}_{m}\right) = E\left(T\right)\cup \bigcup _{i = 1}^{i = n}{\left({C}_{m}\right)}_{i}$ where ${\left({C}_{m}\right)}_{i}$ is a $i$-th cycle leaves. The vertex in the backbone is called the terminal vertex and the vertex in cycle leaves is called a leaves vertex. From Figure 2, that ${v}_{i, 1}$ is terminal vertex and ${v}_{i, j}(j\ne 1)$ is leaves vertex.

Case 1. For $m$ is even

A cycle graph ${C}_{m}$ with $m$ even is a bipartite graph. Based on Lemma 2 that $T⊳{C}_{m}$ is a bipartite graph. Since $T⊳{C}_{m}$ is a bipartite graph, based on Proposition 2, $m{d}_{l}\left(T⊳{C}_{m}\right) = 1$.

Case 2. For $m$ is odd

Based on Lemma 2 that $T⊳{C}_{m}$ isn't a bipartite graph, such that $m{d}_{l}\left(T⊳{C}_{m}\right) > 1$. We prove that $m{d}_{l}\left(T⊳{C}_{m}\right)\ge n$. We will prove that $m{d}_{l}\left(T⊳{C}_{m}\right)\ge n$. Taking any $P\subset V(T⊳{C}_{m})$ with $\left|P\right| = n-1$. Graph $T⊳{C}_{m}$ has $n$ copies of ${C}_{m}$, namely ${\left({C}_{m}\right)}_{1}$, ${\left({C}_{m}\right)}_{2}$, …, ${\left({C}_{m}\right)}_{n}$. Thus, we know that there is at least one cycle that hasn't been resolver. Since ${\left({C}_{m}\right)}_{k}$ for $1\le k\le n$ isn't contained resolver, such that the two adjacent vertices ${v}_{k, \frac{m+1}{2}}, {v}_{k, \frac{m+3}{2}}$ in ${\left({C}_{m}\right)}_{k}$ have the same distance to the terminal vertex, $d\left({v}_{k, \frac{m+1}{2}}, {v}_{k, 1}\right) = \frac{m+1}{2}-1 = \frac{m-1}{2}$ and $d({v}_{k, \frac{m+3}{2}}, {v}_{k, 1}) = m+1-\frac{m+3}{2} = \frac{m-1}{2}$. We know that

It is clear that $d({v}_{k, \frac{m+1}{2}}, {v}_{i, m}) = d({v}_{k, \frac{m+3}{2}}, {v}_{i, m})$ such that ${r}_{m}\left({v}_{k, \frac{m+1}{2}}\right|W) = {r}_{m}({v}_{k, \frac{m+3}{2}}\left|W\right).$ Hence, $m{d}_{l}\left(T⊳{C}_{m}\right)\ge n$.

Theorem 1. Let ${P}_{n}⊳{C}_{m}$ be a comb product of path and cycle for $n\ge 2$ and $m\ge 3$. Then

Proof. The graphs ${P}_{n}⊳{C}_{m}$ has $V({P}_{n}⊳{C}_{m}) = \{{v}_{i, j};i\in \left[1, n\right]\mathrm{a}\mathrm{n}\mathrm{d}j\in [1, m\left]\right\}$ and $E\left({P}_{n}⊳{C}_{m}\right) = \left\{{v}_{i, 1}{v}_{i+\mathrm{1, 1}};i\in \left[1, n-1\right]\right\}\cup \left\{{v}_{i, j}{v}_{i, j+1}\right\};$$i\in \left[1, n\right], j\in \left[1, m-1\right]\}\cup \{{v}_{i, m}{v}_{i, 1};i\in [1, n]\}$ where ${\left({C}_{m}\right)}_{i}$ is a $i$-th cycle leaves. The vertex ${v}_{i, 1}$ in the backbone is called terminal vertex and vertex ${v}_{i, j}(j\ne 1)$ in cycle leaves is called a leaves vertex. This proof is divided into four cases as follows.

Case 1. For $m$ is even

A cycle graph ${C}_{m}$ with $m$ even is a bipartite graph. Based on Lemma 2 that ${P}_{n}⊳{C}_{m}$ is a bipartite graph. Since ${P}_{n}⊳{C}_{m}$ is a bipartite graph, based on Proposition 2, $m{d}_{l}\left({P}_{n}⊳{C}_{m}\right) = 1$.

Case 2. For $m$ is odd and $m\ne 3$

Choose $W = \{{v}_{1, m-1}, {v}_{i, m};i\in [2, n\left]\right\}$, so that $\left|W\right| = n$. We are going to prove that the vertex representations of two adjacent vertices in ${P}_{n}⊳{C}_{m}$ are distinct. The resolver vertex in ${\left({C}_{m}\right)}_{i}, i\in [1, n]$ exactly one resolver in every cycle leaves. The resolver ${v}_{1, m-1}$ in ${\left({C}_{m}\right)}_{1}$ and ${v}_{i, m}$ in ${\left({C}_{m}\right)}_{i}$ for $i\in [2, n].$ In the first step, we show that vertex representations of two adjacent vertices in ${\left({C}_{m}\right)}_{i}, i\in [2, n]$ respect to $W$ are distinct as follows

(1) The number of leave vertex in every cycle leave is even, such that two adjacent vertices in cycle leaves have the same distance to the terminal vertex. The vertex ${v}_{i, \frac{m+1}{2}}, {v}_{i, , \frac{m+3}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d({v}_{i, \frac{m+1}{2}}, {v}_{i, 1}) = d({v}_{i, , \frac{m+3}{2}}, {v}_{i, 1}).$

(2) The number of leave vertex in every cycle leave is even, such that two adjacent vertices in cycle leaves have the same distance to the resolver. The vertex ${v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d({v}_{i, \frac{m-1}{2}}, {v}_{i, m}) = d({v}_{i, \frac{m+1}{2}}, {v}_{i, m}).$

(3) We are going to show that two adjacent vertices in cycle leaves have distinct vertex representations with respect to $W$. For ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, \frac{m-1}{2}}, {v}_{i, 1}\right)\ne d({v}_{i, \frac{m+1}{2}}, {v}_{i, 1})$ such that

Therefore, $d\left({v}_{i, \frac{m-1}{2}}, {v}_{k, m}\right)\ne dd({v}_{i, \frac{m+1}{2}}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{i, \frac{m-1}{2}}|W\right)\ne {r}_{m}\left({v}_{i, \frac{m+1}{2}}|W\right).$

(4) Take two adjacent vertices, ${v}_{i, r}, {v}_{i, s}\in V\left({\left({C}_{m}\right)}_{i}\right)-\left\{{v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}\right\};r, s\in \left[1, m\right], r\ne s$. The resolver ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, r}, {v}_{i, 1}\right)\ne d({v}_{i, s}, {v}_{i, 1})$ such that

Therefore, $d\left({v}_{i, r}, {v}_{k, m}\right)\ne d({v}_{i, s}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{i, r}|W\right)\ne {r}_{m}\left({v}_{i, s}|W\right).$

(5) The backbone indices path ${P}_{n}, n$ odd have a symmetry vertex namely ${v}_{r, 1}\mathrm{a}\mathrm{n}\mathrm{d}{v}_{s, 1}$ with $r+s = n+1$ and ${v}_{r, 1}$ not adjacent to ${v}_{s, 1}$ because there one vertex ${v}_{\frac{n+1}{2}}$ as center vertex.

(6) The terminal vertex indices path graph such that the distance between two adjacent terminal vertex to the resolver vertex is distinct, $d\left({v}_{k, 1}, {v}_{i, m}\right)\ne d({v}_{l, 1}, {v}_{i, m})$ and $d\left({v}_{k, 1}, {v}_{1, m-1}\right)\ne d({v}_{l, 1}, {v}_{1, m-1})$ for $k, l\in \left[2, n\right], k\ne l\ne i$. Thus, ${r}_{m}\left({v}_{k, 1}|W\right)\ne {r}_{m}\left({v}_{l, 1}\right|W).$

(7) The vertex ${v}_{i, 1}$ adjacent to ${v}_{i, 2}$, $d\left({v}_{i, 1}, {v}_{i, m}\right)\ne d({v}_{i, 2}, {v}_{i, m})$ and

It is clear that $d\left({v}_{i, 1}, {v}_{k, m}\right)\ne d\left({v}_{i, 2}, {v}_{k, m}\right)$, we know that ${r}_{m}\left({v}_{i, 1}|W\right) =$$\left\{d\left({v}_{i, 1}, {v}_{i, m}\right), d\left({v}_{i, 1}, {v}_{k, m}\right)\right\}$$\ne \ \left\{d\right({v}_{i, 2}, {v}_{i, m}), d({v}_{i, 2}, {v}_{k, m}) = {r}_{m}({v}_{i, 2}\left|W\right)\}$.

Now, we prove that vertex representation of two adjacent vertices in ${\left({C}_{m}\right)}_{1}$ respect to $W$ is distinct. For ${v}_{1, m-1}$ and ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d({v}_{1, \frac{m-3}{2}}, {v}_{1, m-1}) = d({v}_{1, \frac{m-1}{2}}, {v}_{1, m-1})$ and $d\left({v}_{1, \frac{m-3}{2}}, {v}_{\mathrm{1, 1}}\right)\ne d({v}_{1, \frac{m-1}{2}}, {v}_{\mathrm{1, 1}})$ such that

It is clear that $d\left({v}_{1, \frac{m-3}{2}}, {v}_{k, m}\right)\ne d\left({v}_{1, \frac{m-1}{2}}, {v}_{k, m}\right)$ so that ${r}_{m}\left({v}_{1, \frac{m-1}{2}}|W\right)\ne {r}_{m}\left({v}_{1, \frac{m+1}{2}}|W\right).$ Next, taking two adjacent vertices, ${v}_{1, r}, {v}_{1, s}\in V\left({\left({C}_{m}\right)}_{1}\right)-\left\{v{v}_{1, \frac{m-3}{2}}, {v}_{1, \frac{m-1}{2}}\right\};r, s\in \left[1, m\right], r\ne s$. We know that $d({v}_{1, r}, {v}_{1, m-1}) = d({v}_{1, s}, {v}_{1, m-1})$ and $d\left({v}_{1, r}, {v}_{\mathrm{1, 1}}\right)\ne d\left({v}_{1, s}, {v}_{\mathrm{1, 1}}\right)$ such that

Therefore, $d\left({v}_{1, r}, {v}_{k, m}\right)\ne d({v}_{1, s}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{1, r}|W\right)\ne {r}_{m}\left({v}_{1, s}\right|W$). Hence, ${r}_{m}\left({v}_{i, j}|W\right)\ne {r}_{m}\left({v}_{k, l}\right|W)$ for ${v}_{i, j}$ adjacent to ${v}_{k, l}$ for $i\in [1, n].$ Consequently, $W$ is a local $m$-resolving set of ${P}_{n}⊳{C}_{m}$. Based on Lemma 3 that $m{d}_{l}\left({P}_{n}⊳{C}_{m}\right)\ge n$. Thus, $m{d}_{l}({P}_{n}⊳{C}_{m}) = n$. This completes the proof.

Case 3. For $m = 3$ and n is even

We choose $W = \left\{{v}_{i, 3};i\in \left[1, n\right]\right\}\cup \left\{{v}_{n, 1}\right\},$ so that $\left|W\right| = n+1$. The resolver vertex in ${\left({C}_{3}\right)}_{i}, i\in [1, n]$ exactly one resolver in every cycle leaves and one resolver in the terminal vertex. We are going to prove that the vertex representations of two adjacent vertices in ${P}_{n}⊳{C}_{3}$ are distinct. We show that vertex representations of two adjacent vertices in ${\left({C}_{m}\right)}_{i}, i\in [2, n]$ with respect to $W$ are distinct.

(1) In the first step, we focus on resolver in cycle leaves (${v}_{i, 3}$), we have ${r}_{m}({v}_{\frac{n}{2}, 1}\left|W-\left\{{v}_{n, 1}\right\}\right) = {r}_{m}({v}_{\frac{n+2}{2}, 1}\left|W-\left\{{v}_{n, 1}\right\}\right)$. Because $n$ even, there are a symmetry vertex namely ${v}_{k, 1}$ and ${v}_{l, 1}$ with $k+l = n+1$ and $k\ne l$. We know that ${v}_{\frac{n}{2}, 1}, {v}_{l, \frac{n+2}{2}}$ as two adjacent vertices and symmetry vertex in ${P}_{n}⊳{C}_{3}$ such that ${r}_{m}\left({v}_{\frac{n}{2}, 1}\right|W-\left\{{v}_{n, 1}\right\}) = \{{\mathrm{1, 2}}^{2}, {3}^{2}, \dots , {\left(\frac{n}{2}\right)}^{2}, \frac{n+2}{2}\} = {r}_{m}({v}_{\frac{n+2}{2}, 1}|W-{v}_{n, 1}).$

(2) Now, $d\left({v}_{\frac{n}{2}, 1}, {v}_{n, 1}\right) = n-\frac{n}{2} = \frac{n}{2}$ and $d({v}_{\frac{n+2}{2}, 1}, {v}_{n, 1}) = n-\frac{n+2}{2} = \frac{n-2}{2}$ so that $d\left({v}_{\frac{n}{2}, 1}, {v}_{n, 1}\right)\ne d({v}_{\frac{n+2}{2}, 1}, {v}_{n, 1}).$

Based on points (1) and (2) that

It is clear that ${r}_{m}\left({v}_{\frac{n}{2}, 1}|W\right)\ne {r}_{m}\left({v}_{\frac{n+2}{2}, 1}\right|W)$ for ${v}_{\frac{n}{2}, 1}$ adjacent to ${v}_{\frac{n+2}{2}, 1}$. Consequently, $W$ is a local $m$-resolving set of ${P}_{n}⊳{C}_{3}$.

Furthermore, we prove that W is the local $m$-resolving set with minimum cardinality. Taking any set $S\subset V\left({P}_{n}⊳{C}_{3}\right)$ with $\left|S\right| < \left|W\right|$. Let $\left|S\right| = n,$

(1) $u\in W$, every vertex $u$ in cycle leave.

Every cycle leave has one vertex as a resolver. There are the two adjacent terminal vertices in the backbone indices path ${P}_{n}$. Because n even, then there is a symmetry vertices namely ${v}_{k, 1}$ and ${v}_{l, 1}$ with $k+l = n+1$ and $k\ne l$. We know that ${v}_{\frac{n}{2}, 1}, {v}_{l, \frac{n+2}{2}}$ as two adjacent vertices and symmetry vertices in ${P}_{n}⊳{C}_{3}$ such that ${r}_{m}\left({v}_{\frac{n}{2}, 1}\right|W) = \{{\mathrm{1, 2}}^{2}, {3}^{2}, \dots , {\left(\frac{n}{2}\right)}^{2}, \frac{n+2}{2}\} = {r}_{m}({v}_{\frac{n+2}{2}, 1}\left|W\right)$.

(2) $u\in W$, there is at least one resolver that isn't in cycle leaves.

If there is at least one resolver that isn't in cycle leaves, then there are the two adjacent vertices in cycle leaves that have the same vertex representations. We take ${\left({C}_{3}\right)}_{n}$ without resolver such that

Based on above cases that ${r}_{m}\left({v}_{n, 2}|W\right) = \left\{d\left({v}_{n, 2}, {v}_{k, 3}\right), d\left({v}_{n, 2}, y\right)\right\} = \left\{d\left({v}_{n, 3}, {v}_{k, 3}\right), d\left({v}_{n, 3}, y\right)\right\} = {r}_{m}\left({v}_{n, 3}|W\right).$ Therefore, $S$ is not a local $m$-resolving set of ${P}_{n}⊳{C}_{3}$. Thus, $m{d}_{l}({P}_{n}⊳{C}_{3}) = n+1$. This completes the proof.

Theorem 2. Let ${T}_{1}$ and ${T}_{2}$ be tree graphs, then $m{d}_{l}({T}_{1}⊳{T}_{2}) = 1$.

Proof. Based on Lemma 2 that ${T}_{1}⊳{T}_{2}$ is a bipartite graph. Since ${T}_{1}⊳{T}_{2}$ is a bipartite graph, based on Proposition 2, $m{d}_{l}\left({T}_{1}⊳{T}_{2}\right) = 1$.

Theorem 3. Let $T$ be a tree graph and ${C}_{n}$ be a cycle graph for $n\ge 3$. Then

Proof. The graph ${C}_{n}⊳T$ has $V({C}_{n}⊳T) = {\bigcup }_{i = 1}^{i = n}V\left({T}_{i}\right)$ and $E\left({C}_{n}⊳T\right) = \left\{{v}_{\mathrm{1, 1}}{v}_{n, 1}, {v}_{i, 1}{v}_{i+\mathrm{1, 1}};i\in \left[1, n-1\right]\right\}\cup {\bigcup }_{i = 1}^{i = n}E\left({T}_{i}\right)$ where ${T}_{i}$ is a $i$-th tree leaves. We choose a vertex ${a}_{i}\in {T}_{i}$. The vertex ${v}_{i, 1}$ in the backbone is called terminal vertex and vertex ${v}_{i, j}(j\ne 1)$ in tree leaves is called a leaves vertex. This proof is divided into four cases as follows.

Case 1. For $n$ is even

A cycle graph ${C}_{n}$ with $m$ even is a bipartite graph. Based on Lemma 2 that ${C}_{n}⊳T$ is a bipartite graph. Since ${C}_{n}⊳T$ is a bipartite graph, based on Proposition 2, $m{d}_{l}\left({C}_{n}⊳T\right) = 1$.

Case 2. For $n$ is odd

Choose $W = \{{v}_{\mathrm{1, 1}}, {a}_{2}\}$ with ${a}_{2}\notin V\left({C}_{n}\right)$ or ${a}_{2}\in V\left({T}_{2}\right)$, so that $\left|W\right| = 2$. We are going to prove that the vertex representations of two adjacent vertices in ${C}_{n}⊳T$ are distinct. We can see that

The vertex representations of the vertices ${v}_{i, 1}$ and ${a}_{i}$ are distinct and so $W$ is a local m-resolving set of ${C}_{n}⊳T$. Thus, $m{d}_{l}\left({C}_{n}⊳T\right)\le 2.$ It concluded that $m{d}_{l}({C}_{n}⊳T) = 2$.

Furthermore, we will prove that $W$ is the local $m$-resolving set with minimum cardinality. Take any set $S\subset V({C}_{n}⊳T)$ with $\left|S\right| < \left|W\right|$. Let $\left|S\right| = 1$, suppose the local $m-$resolving set $S = \left\{v\right\}$ so that there are some conditions of this proof as follows

(1) If $v\in V\left({C}_{n}\right)$ namely $v = {v}_{i, 1}$, then

(2) If $v\in V\left({T}_{i}\right)$, then

It is clear that ${r}_{m}\left({v}_{\left(\frac{n+1}{2}+i-1\right)mod\ n, \ \ \ \ \ \ 1}\right|W) = {r}_{m}({v}_{\left(\frac{n+3}{2}+i-1\right)mod\ n, \ \ \ \ \ \ 1}\left|W\right)$. Therefore, $S$ is not a local $m$-resolving set of ${C}_{n}⊳T$. Thus, $m{d}_{l}({C}_{n}⊳T) = 2$.

Theorem 4. Let ${C}_{n}$ and ${C}_{m}$ be cycle graphs for $n, m\ge 3$. Then

Proof. The graph ${C}_{n}⊳{C}_{m}$ has $V({C}_{n}⊳{C}_{m}) = \{{v}_{i, j};i\in \left[1, n\right], j\in [1, m\left]\right\}$ and $E\left({C}_{n}⊳{C}_{m}\right) = \left\{{v}_{\mathrm{1, 1}}{v}_{n, 1}, {v}_{i, 1}{v}_{i+!, 1};i\in \left[1, n-1\right]\right\}\cup$$\left\{{v}_{i, j}{v}_{i, j+1}\right\};i\in \left[1, n\right], j\in [1, m-1]\}\cup \{{v}_{i, m}{v}_{i, 1};i\in [1, n]\}$ where ${\left({C}_{m}\right)}_{i}$ is an $i$-th cycle leaves. The vertex ${v}_{i, 1}$ in the backbone is called terminal vertex and vertex ${v}_{i, j}(j\ne 1)$ in cycle leaves is called a leaves vertex. This proof is divided into four cases as follows.

Case 1. For $n$ and $m$ are even

A cycle graph ${C}_{n}$ and ${C}_{m}$ with $n, m$ even is a bipartite graph. Based on Lemma 2 that ${C}_{n}⊳{C}_{m}$ is a bipartite graph. Since ${C}_{n}⊳{C}_{m}$ is a bipartite graph, based on Proposition 2, $m{d}_{l}\left({C}_{n}⊳{C}_{m}\right) = 1$.

Case 2. For $n$ is odd and $m$ is even

Choose $W = \{{v}_{\mathrm{1, 1}}, {v}_{2, m}\}$, so that $\left|W\right| = 2$. We are going to prove that the vertex representations of two adjacent vertices in ${C}_{n}⊳{C}_{m}$ are distinct. We can see that:

The vertex representations of the adjacent vertices ${v}_{i}$ are distinct such that $W$ is a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$. Thus, $m{d}_{l}\left({C}_{n}⊳{C}_{m}\right)\le 2$.

Furthermore, we are going to prove that $W$ is the local m-resolving set with minimum cardinality. Take any set $S\subset V({C}_{n}⊳{C}_{m})$ with $\left|S\right| < \left|W\right|$. Let $\left|S\right| = 1$, suppose the local $m$-resolving set $W = \left\{v\right\}$ so that there are some conditions of this proof as follows

(1) If $v\in V\left({C}_{n}\right)$ namely $v = {v}_{i, 1}$, then we have vertex representation as follows

(2) If $v\in V\left({\left({C}_{m}\right)}_{i}\right),$ then we have vertex representation as follows

It is clear that ${r}_{m}\left({v}_{\left(\frac{n+1}{2}+i-1\right)mod\ n, \ \ \ \ \ \ 1}\right|W) = {r}_{m}({v}_{\left(\frac{n+3}{2}+i-1\right)mod\ n, \ \ \ \ \ \ 1}\left|W\right)$. Therefore, $S$ is not a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$. Thus, $m{d}_{l}({C}_{n}⊳{C}_{m}) = 2$.

Case 3. For $n$ is even and $m$ is odd

Choose $W = \{{v}_{1, m-1}, {v}_{i, m};i\in [2, n\left]\right\}$, so that $\left|W\right| = n$. We are going to prove that the vertex representations of two adjacent vertices in ${C}_{n}⊳{C}_{m}$ are distinct. The resolver vertex in ${\left({C}_{m}\right)}_{i}, i\in [1, n]$ exactly one resolver in every cycle leaves. The resolver ${v}_{1, m-1}$ in ${\left({C}_{m}\right)}_{1}$ and ${v}_{i, m}$ in ${\left({C}_{m}\right)}_{i}$ for $i\in [2, n].$ In the first step, we show that vertex representations of two adjacent vertices in ${\left({C}_{m}\right)}_{i}, i\in [2, n]$ with respect to $W$ are distinct as follows

(1) The number of leave vertex in every cycle leave is even, such that two adjacent vertices in cycle leaves have the same distance to the terminal vertex. The vertex ${v}_{i, \frac{m+1}{2}}, {v}_{i, \frac{m+3}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d\left({v}_{i, \frac{m+1}{2}}\right\}, {v}_{i, 1}) = d({v}_{i, \frac{m+3}{2}}, {v}_{i, 1}).$

(2) The number of leave vertex in every cycle leave is even, such that two adjacent vertices in cycle leaves have the same distance to the resolver. The vertex ${v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d({v}_{i, \frac{m-1}{2}}, {v}_{i, m}) = d({v}_{i, \frac{m+1}{2}}, {v}_{i, m})$.

(3) We are going to show that two adjacent vertices in cycle leaves have distinct vertex representations with respect to $W$. For ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, \frac{m-1}{2}}, {v}_{i, 1}\right)\ne d({v}_{i, \frac{m+1}{2}}, {v}_{i, 1})$ such that

Therefore, $d\left({v}_{i, \frac{m-1}{2}}, {v}_{k, m}\right)\ne d({v}_{i, \frac{m+1}{2}}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{i, \frac{m-1}{2}}|W\right)\ne {r}_{m}\left({v}_{i, \frac{m+1}{2}}\right|W).$

(4) Take two adjacent vertices, ${v}_{i, r}, {v}_{i, s}\in V\left({\left({C}_{m}\right)}_{i}\right)-\left\{{v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}\right\}, r, s\in \left[1, m\right], r\ne s$. The resolver ${v}_{k, m}\in W$, $k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, r}, {v}_{i, s}\right)\ne d({v}_{i, s}, {v}_{i, 1})$ such that

Therefore, $d\left({v}_{i, r}, {v}_{k, m}\right)\ne d({v}_{i, s}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{i, r}|W\right)\ne {r}_{m}\left({v}_{i, s}\right|W).$

(5) The terminal vertex indices cycle graph ${C}_{n}, n$ is odd such that the distance between two adjacent terminal vertex to the resolver vertex is distinct, $d\left({v}_{k, 1}, {v}_{i, m}\right)\ne d({v}_{l.1}, {v}_{i, m})$ and $d\left({v}_{k, 1}, {v}_{1, m-1}\right)\ne d({v}_{l, 1}, {v}_{1, m-1})$ for $k, l\in \left[2, n\right], k\ne l\ne i$. Based on (6) so that ${r}_{m}\left({v}_{k, 1}|W\right)\ne {r}_{m}\left({v}_{l, 1}\right|W).$

(6) The vertex ${v}_{i, 1}$ adjacent to ${v}_{i, 2}, d\left({v}_{i, 1}, {v}_{i, m}\right)\ne d({v}_{i, 2}, {v}_{i, m})$ and

It is clear that $d\left({v}_{i, 1}, {v}_{k, m}\right)\ne d\left({v}_{i, 2}, {v}_{k, m}\right)$, we know that ${r}_{m}\left({v}_{i, 1}|W\right) = \left\{d\left({v}_{i, 1}, {v}_{i, m}\right), d\left({v}_{i, 1}, {v}_{k, m}\right)\right\}$$\ne \left\{d\left({v}_{i, 2}, {v}_{i, m}\right), d\left({v}_{i, 2}, {v}_{k, m}\right)\right\} = {r}_{m}\left({v}_{i, 2}\right|W).$

Now, we prove that vertex representation of two adjacent vertices in ${\left({C}_{m}\right)}_{1}$ respect to $W$ is distinct. For ${v}_{1, m-1}$ and ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d({v}_{1, \frac{m-3}{2}}, {v}_{1, m-1}) = d({v}_{1, \frac{m-1}{2}}, {v}_{1, m-1})$ and $d\left({v}_{1, \frac{m-3}{2}}, {v}_{\mathrm{1, 1}}\right)\ne d({v}_{1, \frac{m-1}{2}}, {v}_{\mathrm{1, 1}})$ such that

It is clear that $d\left({v}_{1, \frac{m-3}{2}}, {v}_{k, m}\right)\ne d({v}_{1, \frac{m-1}{2}}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{1, \frac{m-1}{2}}|W\right)\ne {r}_{m}\left({v}_{1, \frac{m+1}{2}}\right|W)$. Next, taking two adjacent vertices, ${v}_{1, r}, {v}_{1, s}\in V\left({\left({C}_{m}\right)}_{1}\right)-\left\{{v}_{1, \frac{m-3}{2}}, {v}_{1, \frac{m-1}{2}}\right\}, r, s\in \left[1, m\right], r\ne s$. We know that $d({v}_{1, r}, {v}_{1, m-1}) = d({v}_{1, s}, {v}_{1, m-1})$ and $d\left({v}_{1, r}, {v}_{\mathrm{1, 1}}\right)\ne d({v}_{1, s}, {v}_{\mathrm{1, 1}})$ such that

Therefore, $d\left({v}_{1, r}, {v}_{k, m}\right)\ne d({v}_{1, s}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{1, r}|W\right)\ne {r}_{m}\left({v}_{1, s}\right|W)$. Hence, ${r}_{m}\left({v}_{i, j}|W\right)\ne {r}_{m}\left({v}_{k, l}\right|W)$ for ${v}_{i, j}$ adjacent to ${v}_{k, l}$ for $i\in [1, n]$. Consequently, $W$ is a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$.

Furthermore, we will prove that $W$ is the local $m$-resolving set with minimum cardinality. Taking any set $S\subset V({C}_{n}⊳{C}_{m})$ with $\left|S\right| < \left|W\right|$. Let $\left|S\right| = n-1$, there are at least one cycle leaves which haven't resolver. For m odd, there are even leave vertex such that the two adjacent vertices ${v}_{k, \frac{m+1}{2}}, {v}_{k, \frac{m+3}{2}}\in {V\left({C}_{m}\right)}_{k}, k\in [1, m]$ have the same distance to the terminal vertex, $d\left({v}_{k, \frac{m+1}{2}}, {v}_{k, 1}\right) = \frac{m+1}{2}-1 = \frac{m-1}{2}$ and $d({v}_{k, \frac{m+3}{2}}, {v}_{k, m}) = m+1-\frac{m+3}{2} = \frac{m-1}{2}$. We know that

It is clear that $d\left({v}_{k, \frac{m+1}{2}}, {v}_{i, m}\right) = d\left({v}_{k, \frac{m+3}{2}}, {v}_{i, m}\right)$ such that ${r}_{m}\left({v}_{k, \frac{m+1}{2}}\right|W) = {r}_{m}({v}_{k, \frac{m+3}{2}}\left|W\right)$. Therefore, $S$ is not a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$. Thus, $m{d}_{l}({C}_{n}⊳{C}_{m}) = n$. This completes the proof.

Case 4. For $n$ and $m$ are odd

Choose $W = \{{v}_{1, m-1}, {v}_{3, m-1}, {v}_{4, m-1}, {v}_{i, m};i\notin \{\mathrm{1, 3}, 4\left\}\right\}$, so that $\left|W\right| = n$. We are going to prove that the vertex representations of two adjacent vertices in ${C}_{n}⊳{C}_{m}$ are distinct. The resolver vertex in ${\left({C}_{m}\right)}_{i}, i\in [1, n]$ exactly one resolver in every cycle leaves. The resolver ${v}_{i, m-1}$ in ${\left({C}_{m}\right)}_{i}, i\in \{\mathrm{1, 3}, 4\}$ and ${v}_{i, m}$ in ${\left({C}_{m}\right)}_{i}$ for $i\notin \{\mathrm{1, 3}, 4\}$. In the first step, we show that vertex representations of two adjacent vertices in ${\left({C}_{m}\right)}_{i}, i\notin \{\mathrm{1, 3}, 4\}$ with respect to $W$ are distinct as follows

(1) The number of leave vertex in every cycle leaves is even, such that two adjacent vertices in cycle leaves have the same distance to the terminal vertex. The vertex ${v}_{i, \frac{m+1}{2}}, {v}_{i, \frac{m+3}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d({v}_{i, \frac{m+1}{2}}, {v}_{i, 1}) = d({v}_{i, \frac{m+3}{2}}, {v}_{i, 1})$.

(2) The number of leave vertex in every cycle leaves is even, such that two adjacent vertices in cycle leaves have the same distance to the resolver. The vertex ${v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}$ in ${\left({C}_{m}\right)}_{i}$ so that, $d({v}_{i, \frac{m-1}{2}}, {v}_{i, m}) = d({v}_{i, \frac{m+1}{2}}, {v}_{i, m}).$

(3) We are going to show that two adjacent vertices in cycle leaves have distinct vertex representations with respect to $W$. For ${v}_{k, m}\in W, k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, \frac{m-1}{2}}, {v}_{i, 1}\right)\ne d({v}_{i, \frac{m+1}{2}}, {v}_{i, 1})$ such that

Therefore, $d({v}_{i, \frac{m-1}{2}}, {v}_{k, m}\ne d({v}_{i, \frac{m+1}{2}}, {v}_{k, m})$ so that ${r}_{m}\left({v}_{i, \frac{m-1}{2}}|W\right)\ne {r}_{m}\left({v}_{i, \frac{m+1}{2}}\right|W).$

(4) Take two adjacent vertices, ${v}_{i, r}, {v}_{i, s}\in V\left({\left({C}_{m}\right)}_{i}\right)-\left\{{v}_{i, \frac{m-1}{2}}, {v}_{i, \frac{m+1}{2}}\right\}, r, s\in \left[1, m\right], r\ne s$. The resolver ${v}_{k, m}\in W,$ $k\in [2, n]$ and $k\ne i$, we know that $d\left({v}_{i, r}, {v}_{i, 1}\right)\ne d\left({v}_{i, s}, {v}_{i, 1}\right)$ such that

Therefore, $d\left({v}_{i, r}, {v}_{k, m}\right)\ne d\left({v}_{i, s}, {v}_{k, m}\right)$ so that ${r}_{m}\left({v}_{i, r}|W\right)\ne {r}_{m}\left({v}_{i, s}|W\right).$

(5) The terminal vertex indices cycle graph ${C}_{n}, n$ is odd such that the distance between two adjacent terminal vertex to the resolver vertex is distinct, $d\left({v}_{k, 1}, {v}_{i, m}\right)\ne d({v}_{l, 1}, {v}_{i, m})$ for $i\notin \{\mathrm{1, 3}, 4\}$ and $d\left({v}_{k, 1}, {v}_{i, m-1}\right)\ne d({v}_{l, 1}, {v}_{i, m-1})$ for $k, l\in [2, n]$ and $i\in \{\mathrm{1, 3}, 4\}$ so that ${r}_{m}\left({v}_{k, 1}|W\right)\ne {r}_{m}\left({v}_{l, 1}\right|W).$

(6) The vertex ${v}_{i, 1}$ adjacent to ${v}_{i, 2}$, $d\left({v}_{i, 1}, {v}_{i, m}\right)\ne d({v}_{i, 2}, {v}_{i, m})$ and

It is clear that $d\left({v}_{i, 1}, {v}_{k, m}\right)\ne d({v}_{i, 2}, {v}_{k, m})$, we know that ${r}_{m}\left({v}_{i, 1}|W\right) = \left\{d\left({v}_{i, 1}, {v}_{i, m}\right), d\left({v}_{i, 1}, {v}_{k, m}\right)\right\}$$\ne \left\{d\left({v}_{i, 2}, {v}_{i, m}\right), d\left({v}_{i, 2}, {v}_{k, m}\right) = {r}_{m}\left({v}_{i, 2}|W\right)\right\}$.

Hence, ${r}_{m}\left({v}_{i, j}|W\right)\ne {r}_{m}\left({v}_{k, l}\right|W)$ for ${v}_{i, j}$ adjacent to ${v}_{k, l}$ for $i\in [1, n].$ Consequently, $W$ is a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$.

Furthermore, we will prove that $W$ is the local $m$-resolving set with minimum cardinality. Take any set $S\subset V({C}_{n}⊳{C}_{m})$ with $\left|S\right| < \left|W\right|$. Let $\left|S\right| = n-1$, there are at least one cycle leaves which haven't resolver. For $m$ odd, The number of leave vertex in every cycle leaves is even, such that the two adjacent vertices ${v}_{k, \frac{m+1}{2}}, {v}_{k, \frac{m+3}{2}}$ in ${\left({C}_{m}\right)}_{k}, k\in [1, m]$ have the same distance to the terminal vertex, $d\left({v}_{k, \frac{m+1}{2}}, {v}_{k, 1}\right) = \frac{m+1}{2}-1 = \frac{m-1}{2}$ and $d({v}_{k, \frac{m+3}{2}}, {v}_{k, m}) = m+1-\frac{m+3}{2} = \frac{m-1}{2}.$ We know that

It is clear that $d({v}_{k, \frac{m+1}{2}}, {v}_{i, m}) = d({v}_{k, \frac{m+3}{2}}, {v}_{i, m})$ such that ${r}_{m}\left({v}_{k, \frac{m+1}{2}}\right|W) = {r}_{m}({v}_{k, \frac{m+3}{2}}\left|W\right)$. Therefore, $S$ is not a local $m$-resolving set of ${C}_{n}⊳{C}_{m}$. Thus, $m{d}_{l}({C}_{n}⊳{C}_{m}) = n$. This completes the proof.

3.   Conclusions

We have found the sharpest bounds of LMD of the tree comb cycle, and we get the exact value of the cycle comb tree, tree comb tree, and cycle comb cycle. There are some open problems with this research as follows.

Open Problem 1. Determine the bounds of local multiset dimension of $G⊳H$ for $G$ and $H$ are any graphs.

Open Problem 2. Determine the local multiset dimension of $G$ with $m{d}_{l}\left(G\right) = n-1, n-2$.

Open Problem 3. Characterized $m{d}_{l}\left(G\right)-ldim\left(G\right) = 0$.

Acknowledgments

We gratefully acknowledgment the support from Universitas Jember and Universitas Airlangga for the year 2023.

Conflict of interest

There is no conflict of interest in this research.