A New Technique to Uniquely Identify the Edges of a Graph

Abstract

Graphs are useful for analysing the structure models in computer science, operations research, and sociology. The word metric dimension is the basis of the distance function, which has a symmetric property. Moreover, finding the resolving set of a graph is NP-complete, and the possibilities of finding the resolving set are reduced due to the symmetric behaviour of the graph. In this paper, we introduce the idea of the edge-multiset dimension of graphs. A representation of an edge is defined as the multiset of distances between it and the vertices of a set, $B\subseteq V\left(\mathsf{\Gamma }\right)$. If the representation of two different edges is unequal, then B is an edge-multiset resolving a set of $\mathsf{\Gamma }$. The least possible cardinality of the edge-multiset resolving a set is referred to as the edge-multiset dimension of $\mathsf{\Gamma }$. This article presents preliminary results, special conditions, and bounds on the edge-multiset dimension of certain graphs. This research provides new insights into structure models in computer science, operations research, and sociology. They could have implications for developing computer algorithms, aircraft scheduling, and species movement between regions.

1. Introduction

The study of distance-related parameters in graph theory, especially the metric dimension, has long been a topic of interest among researchers. The metric dimension of a graph is the minimum number of vertices required to uniquely identify every vertex in the graph using distances between vertices. In everyday applications, the concept of the metric dimension is helpful in different fields, such as computer networks, pattern recognition, and network security. In computer networks, the metric dimension of a graph can be used to determine the node’s location in the network and assess the network’s reliability and performance. In recent years, the study of metric dimensions has become ever more prevalent due to the growth of internet relationships and the increasing demand for robust and secure networks. The theory of metric dimensions was proposed by Slater in 1975 [1], and independently by Harary and Melter in 1976 [2]. However, the notion of metric dimensions in metric spaces generally dates back to 1953 [3]. Some recent studies on the metric dimension of graphs are given in the following articles [4,5,6]. The concept of metric dimensions is based on the distance function $d:V\times V\to R^{+}\cup \left\{0\right\},$ which has the symmetric property. Determining the resolving set of a graph is an NP-complete problem, so it is computationally difficult to find the minimum size-resolving set for a graph. However, due to the graph’s symmetric nature, finding the resolvability reduces the number of possibilities for the elements in the resolving set. The study of distance in graphs is a fast-expanding area of research in different science fields, especially mathematics, chemistry, and computer science. The concept of distances in graphs has several applications in various fields. Researchers are constantly exploring new and innovative ways to measure and analyse graph distances and apply these methods to real-world problems. The field is marked by a high level of interdisciplinary collaboration, with computer science, mathematics, physics, and biology researchers all contributing to developing new techniques and algorithms.

In this manuscript, we define a new technique to identify the edges of a graph, termed the edge-multiset dimension and compared to the multiset dimension. Section 2 contains a comprehensive literature review and basic definitions. In Section 3, we give the methods used in the manuscript. Section 4 contains the main results of the multiset and edge-multiset dimensions of different families of graphs. This section also discusses the graphs having infinite, constant and edge-multiset dimension graphs depending on their order. In Section 5, we give different examples and compare multiset and edge-multiset dimensions. In the end we give the conclusions and open problems for future work.

2. Literature Review

Various distance-related parameters have been studied, such as the partition distance of graphs were studied in [7], Alhevaz et al. gave the sharp bounds for the generalized distance spectral radius of graphs [8], Wang studied distance bounds for generalized bicycle codes and Pryadko [9], Nadeem et al. found the fault-tolerant partition dimension of oxide interconnection networks [10]. Concerning metric dimensions, that have been of more interest to the research community, one could remark of a few of them (although possibly not all of the most remarkable ones): partition dimension [11], strong metric dimension [12], k-metric dimension [13], identifying codes [14], k-metric anti-dimension [15], local metric dimension [16], edge metric dimension [17] and multiset dimension [18] (see also [19] for the outer-multiset dimension). Each of these variations of the metric dimension mentioned above have been recently studied to a greater or lesser extent, and even some combinations between them have also appeared, including, for instance, k-partition dimension [20], or local edge dimension [21].

In their work [17], Kelenc et al. introduced the concept of the edge metric dimension of graphs and discussed various results, including comparisons with the metric dimension of graphs. Such variation has attracted the significant attention from several researchers, and we can find many papers on it. In [22], characterized the formation of the topful graph and some sufficient and important conditions of a graph to be topful were explained. The edge metric dimension of some convex polytopes and its relevant graphs were determined in [23]. The edge dimension of some generalized Petersen graphs was explained in [24]. The edge dimensions via integer linear programming and hierarchical products were given in [25], and many examples show that these methods can be used to obtain the edge dimensions for some graphs. The edge dimension of the two graphs’ join, corona, and the lexicographic product was studied in [26]. The vertex, edge and mixed dimension of the dragon graph $T_{n,m}$, $L\left(T_{n,m}\right)$, $L\left(S\left(T_{n,m}\right)\right)$ and $L\left(L\left(T_{n,m}\right)\right)$ have been computed [27]. Knor presented [28] a lot of graphs which proved that the edge dimension is less than the metric dimension, but it is impossible to bound the edge dimension of a graph by the vertex dimension. The approximation algorithm was presented for the edge dimension problem in [29]. On the other hand, Simanjuntak, et al. [18], presented the notion of using multisets for uniquely identifying the vertices of a graph, which allowed the birth of the multiset dimension of graphs in 2017. They presented some primary results, showed sufficient conditions for a graph to have a multiset dimension infinite, and computed the multiset dimension of some graphs. Some other results on this variant appeared in [30,31,32]. In connection with this, in [19], another version of the multiset dimension (called the outer-multiset dimension) was introduced as an attempt to avoid the existence of graphs with infinite multiset dimensions (that is, graphs for which the multiset dimension cannot be computed).

Based on the significance of these two latter variants of metric dimension (edge and multiset), we aim to introduce and begin the study of a natural combination of them, that is, the edge-multiset dimension of graphs. From now onward, we consider $\mathsf{\Gamma }$ a connected and simple graph. The vertex set of $\mathsf{\Gamma }$ is $V\left(\mathsf{\Gamma }\right)$ and edge set of $\mathsf{\Gamma }$ is $E\left(\mathsf{\Gamma }\right)$. The distance between any pair of vertices $\alpha$ and $\beta \in V\left(\mathsf{\Gamma }\right)$ is symbolized as $d_{\mathsf{\Gamma }}(\alpha ,\beta )$ (or $d(\alpha ,\beta )$ for short), and is described as the number of edges of the least possible path between $\alpha$ and $\beta$. Assume $w\in V\left(\mathsf{\Gamma }\right)$, resolves (recognizes or determines) the vertices $\alpha$ and $\beta$, if $d_{\mathsf{\Gamma }}(w,\alpha )\ne d_{\mathsf{\Gamma }}(w,\beta )$. For an ordered subset of t vertices $S=\{v_1,v_2,\cdots ,v_t\}$, the metric code or representation of a vertex u according to S is the ordered $t-$tuple of distances between u and the vertices in S, which is written as

$r\left(u\right|S)=(d_{\mathsf{\Gamma }}(u,v_1),d_{\mathsf{\Gamma }}(u,v_2),\dots ,d_{\mathsf{\Gamma }}(u,v_t)).$

If any pair of vertices of $\mathsf{\Gamma }$ have dissimilar metric codes or representations according to set S, then S is known as a resolving set for $\mathsf{\Gamma }$. The metric dimension of $\mathsf{\Gamma }$ is defined as the number of vertices in the smallest resolving set for $\mathsf{\Gamma }$, denoted by $dim\left(\mathsf{\Gamma }\right)$. If S is a resolving set for $\mathsf{\Gamma }$ of cardinality $dim\left(\mathsf{\Gamma }\right)$, then S is called a metric basis for $\mathsf{\Gamma }$.

The distance between an edge $f=\alpha \beta$ and a vertex $\rho$ is denoted as $d_{\mathsf{\Gamma }}(f,\rho )$ (or $d(f,\rho )$ for short), and is defined as $d_{\mathsf{\Gamma }}(f,\rho )=min\{d_{\mathsf{\Gamma }}(\alpha ,\rho ),d_{\mathsf{\Gamma }}(\beta ,\rho )\}$. The vertex p resolves (recognizes or determines) the edges $f_1$ and $f_2$, if $d_{\mathsf{\Gamma }}(f_1,p)\ne d_{\mathsf{\Gamma }}(f_2,p)$. For an ordered subset of t vertices $S=\{v_1,v_2,\dots ,v_t\}$, the metric code or representation of an edge f according to set S is the ordered $t-$tuple of distances between f and the vertices in S, which is written as

$r\left(f\right|S)=(d_{\mathsf{\Gamma }}(f,v_1),d_{\mathsf{\Gamma }}(f,v_2),\dots ,d_{\mathsf{\Gamma }}(f,v_t)).$

If any pair of edges of $\mathsf{\Gamma }$ have specific metric codes or representations according to S, then S is known as an edge-resolving set for $\mathsf{\Gamma }$. The edge metric dimension of $\mathsf{\Gamma }$ is then defined as the number of vertices in the smallest edge resolving set for $\mathsf{\Gamma }$, denoted by ${dim}_e\left(\mathsf{\Gamma }\right)$. If S is an edge resolving set for $\mathsf{\Gamma }$ of cardinality ${dim}_e\left(\mathsf{\Gamma }\right)$, then S is called an edge metric basis for $\mathsf{\Gamma }$.

Multiset and Edge-Multiset Dimensions of Graphs

Let $A=\{a_1,a_2,\cdots ,a_l\}$ be a subset of $V\left(\mathsf{\Gamma }\right)$. For any vertex u of $\mathsf{\Gamma }$, the multiset code or representation of $u\in V\left(\mathsf{\Gamma }\right)$ according to A is a multiset which is defined as

$r_m\left(u\right|A)=\{d_{\mathsf{\Gamma }}(u,a_1),d_{\mathsf{\Gamma }}(u,a_2),\cdots ,d_{\mathsf{\Gamma }}(u,a_l)\}.$

Note that the notion of multisets allows repetitions of elements in $r_m\left(u\right|A)$. If $r_m\left(u\right|A)\ne r_m\left(v\right|A)$ for every pair of vertices u and $v\in V\left(\mathsf{\Gamma }\right)$, then A is called a multiset resolving set of $\mathsf{\Gamma }$. There could be graphs containing no multiset resolving sets. For instance, consider a graph with two vertices $u\mathrm{and}v$, which are twins; that is, they share the same neighbours in $\mathsf{\Gamma }$. In this sense, no matter which set of vertices D of $\mathsf{\Gamma }$ one could choose, it will always happen $r_m\left(u\right|D)=r_m\left(v\right|D)$. Hence, they will never be resolved by any set of vertices of $\mathsf{\Gamma }$. In this sense, if a graph $\mathsf{\Gamma }$ contains at least one multiset resolving set, then a multiset resolving set containing the smallest possible number of vertices is called a multiset basis of $\mathsf{\Gamma }$. In such a case, the cardinality of any multiset basis of $\mathsf{\Gamma }$ is called the multiset dimension of $\mathsf{\Gamma }$, and is denoted as $md\left(\mathsf{\Gamma }\right)$. On to the contrary, if $\mathsf{\Gamma }$ does not possess a multiset resolving set, we agreed that $md\left(\mathsf{\Gamma }\right)=\infty$. For some partial information on graphs satisfying this property, we suggest [33].

To give an example of the above concepts, assume graph G with $V\left(G\right)=\{v_1,v_2,\cdots ,v_8\}$ and $E\left(G\right)=\{a,b,c,d,e,f,g,h\}$ as given in Figure 1. We note that for instance, the set $A=\{v_2,v_3,v_7\}$ is a multiset resolving set of G.

Next, we show Table 1, where the multiset codes or representations of $V\left(G\right)$ of G according to A are given. It can be easily verified that no multiset resolving set having cardinality less than three is a multiset resolving sets for G, which altogether leads to $md\left(G\right)=3$.

Now, the multiset representation $r_{em}\left(e\right|B)$ of an edge $e=xy$ according to the set B, is defined as a multiset containing the distances between the edge e and the vertices in B. That is,

$r_{em}\left(e\right|B)=\{d_{\mathsf{\Gamma }}(e,b_1),d_{\mathsf{\Gamma }}(e,b_2),\cdots ,d_{\mathsf{\Gamma }}(e,b_j)\}.$

If $r_{em}\left(e\right|B)\ne r_{em}\left(f\right|B)$ for any pair of dissimilar edges e and f, then B is called an edge-multiset resolving set for $\mathsf{\Gamma }$. We again remark that there can be graphs containing no edge-multiset resolving sets. If $\mathsf{\Gamma }$ contains an edge-multiset resolving set, then the least possible edge-multiset resolving set is called an edge-multiset basis of $\mathsf{\Gamma }$. The number of elements in an edge-multiset basis of $\mathsf{\Gamma }$ is known as the edge-multiset dimension, and is denoted as $m{d}_e\left(\mathsf{\Gamma }\right)$. If $\mathsf{\Gamma }$ does not contain an edge-multiset resolving set, then we assume that $m{d}_e\left(\mathsf{\Gamma }\right)=\infty$.

In a similar manner to the case of the multiset dimension, Table 2 shows the multiset representations of all the edges of the graph G given in Figure 1, according to $B=\{v_2,v_3,v_7\}$. It can be easily determined that no set with less than three vertices is an edge-multiset resolving set for G; thus, $m{d}_e\left(G\right)=3$.

After introducing the multiset dimension, it is natural to ask what the representation of edges will be with respect to the multiset resolving set. We introduce and study a new concept called the edge-multiset dimension of graphs, which combines two significant variants of the metric dimension (edge and multiset).

3. Methodology

There are many steps in this research known as determining the graph $\mathsf{\Gamma }$, defining the set of vertices and the set of edges, determining the set $A\subseteq E\left(\mathsf{\Gamma }\right)$, determining the multiset representations of vertices or edges of graph $\mathsf{\Gamma }$, and determining the least possible resolving set for $\mathsf{\Gamma }$.

Next, we present on the following known results for the multiset dimension of graphs that are interesting for this exposition.

Theorem 1

([18]). The multiset dimension of a graph Γ is one if, and only if, Γ is a path.

Theorem 2

([18]). Let Γ be a graph other than a path. Then $md\left(\mathsf{\Gamma }\right)\ge 3.$

Theorem 3

([18]). Let $n\ge$6. The multiset dimension of the cycle $C_n$ is $3.$

Theorem 4

([18]). Let $m\ge$3 and $n\ge 2.$ The multiset dimension of the grid graph $P_n\square P_m$ is $3.$

Theorem 5

([18]). If Γ is a non-path graph of diameter at most $2,$ then $md\left(\mathsf{\Gamma }\right)=\infty$.

Consequently, from the above-known results, there is no graph $\mathsf{\Gamma }$ with a multiset dimension of 2. Since the graphs with a multiset dimension are characterized in Theorem 1, it would be desirable to characterize (at least partially) the graphs with a multiset dimension of 3. In concordance with this. Figure 2 shows the flow chart of the research methodology used in this paper.

4. Results on the Multiset and Edge-Multiset Dimensions of Graphs

Next, we give some families of graphs, kayak paddle, dragon and comb products of two path graphs with a multiset dimension of 3.

4.1. Kayak Paddle Graph

The kayak paddle graph, denoted by $KP(\vartheta ,\lambda ,\mu )$ is obtained from two cycles of length $\vartheta \ge 3$ and $\lambda \ge 3$ by joining one vertex of one cycle with a vertex of degree one in a path of length $\mu \ge 2$, and another vertex of the other cycle with the other vertex of degree one in the path of length $\mu$. See Figure 3 for an example. We can write the vertex set of $KP(\vartheta ,\lambda ,\mu )$ as $V\left(KP(\vartheta ,\lambda ,\mu )\right)=\{{\alpha }_1,{\alpha }_2,\dots {\alpha }_{\vartheta }\}\cup \{{\beta }_1,{\beta }_2,\dots ,{\beta }_{\lambda }\}\cup \{{\gamma }_1,\dots ,{\gamma }_{\mu -1}\}$ and the edge set as $E\left(KP(\vartheta ,\lambda ,\mu )\right)=\{{\alpha }_i{\alpha }_{i+1}:1\le i\le \vartheta \}\cup \{{\beta }_j{\beta }_{j+1}:1\le j\le \lambda \}\cup \{{\gamma }_k{\gamma }_{k+1}:1\le k\le \mu -2\}\cup \{{\alpha }_1{\gamma }_1,{\gamma }_{\mu -1}{\beta }_1\}$, where ${\alpha }_{\vartheta +1}={\alpha }_1$ and ${\beta }_{\lambda +1}={\beta }_1$.

In Theorem 6 we determine the exact value of the multiset dimension of the kayak paddle graph.

Theorem 6.

If $KP(\vartheta ,\lambda ,\mu )$ is a kayak paddle graph with $\vartheta ,\lambda ,\mu \ge 4$, then

$md\left(KP\right(\vartheta ,\lambda ,\mu \left)\right)=3$

.

Proof. 

Therefore, by using Theorem 2, we have that $md\left(KP\right(\vartheta ,\lambda ,\mu \left)\right)\ge 3$. Set $A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$ is a multiset resolving set for the graph $KP(\vartheta ,\lambda ,\mu )$.

If $\vartheta \ge 4$ with $t=\lfloor \frac{\vartheta }{2}\rfloor +1$, then the vertices represented according to A are given in Table 3:

If $\lambda \ge 4$ with $t^{\prime }=\lfloor \frac{\lambda }{2}\rfloor +1$, then the vertices represented according to A are given in Table 4:

If $\mu \ge 4$, then the vertices represented according to A are given in Table 5:

Therefore, any two vertices do not have the same multiset code or representation according to A, as shown in Table 3, Table 4 and Table 5. This implies that $md\left(KP\right(\vartheta ,\lambda ,\mu \left)\right)\le 3$. Hence, $md\left(KP\right(\vartheta ,\lambda ,\mu \left)\right)=3$. □

4.2. Dragon Graph

The dragon graph $T_{n,m}$ is obtained by joining a vertex $v_n$ of a cycle graph $C_n$ with a vertex $u_1$ of a path graph $P_m$ with a bridge. See Figure 4 for an example. The vertex set of a dragon graph $T_{n,m}$ is $V\left(T_{n,m}\right)=\{v_i,u_j|1\le i\le n,1\le j\le m\}$ and the edge set is $E\left(T_{n,m}\right)=\{v_i{v}_{i+1}:1\le i\le n-1\}\cup \{u_j{u}_{j+1}1\le j\le m-1\}\cup \{v_1{v}_n,v_n{u}_1\}$.

In Theorem 7 we determine the exact value of the multiset dimension of a dragon graph.

Theorem 7.

Let $T_{n,m}$ be a dragon graph with $n\ge 4$ and $m\ge 3$. Then $md\left(T_{n,m}\right)=3$.

Proof. 

Therefore, by Theorem 2, $md\left(T_{n,m}\right)\ge 3$. We next show that the set $A=\{v_1,v_2,u_m\}$ is a multiset resolving set for $T_{n,m}$.

If $n\ge 4$ is even with $t=\frac{n}{2}$, then the vertices represented according to A are given in Table 6:

If $n\ge 4$ is odd with $t=\lfloor \frac{n}{2}\rfloor$, then the vertices represented according to A are given in Table 7:

If $m\ge 4$ then the vertices represented according to A are given in Table 8:

Therefore, any two vertices do not have the same multiset code or representation according to A, as shown in Table 6, Table 7 and Table 8. This implies that $md\left(T_{n,m}\right)\le 3$. Hence, $md\left(T_{n,m}\right)=3$. □

4.3. Comb Products Graph

Let G and H be two graphs. Then the comb product, symbolically written as $G{⊳}_{\circ }H$, is produced by picking $\left|V\right(G\left)\right|$ copies of H and one copy of G and identifying the ith copy of graph H at vertex o to the ith vertex of graph G. Such a product is also called a rooted product graph, as introduced in [34], or a hierarchical product graph as defined in [35]. Several studies related to metric dimension parameters of such graphs are found in the literature, for a couple of recent ones, see [36,37]. A fairly representative example of a comb product graph of $P_5$ and $P_4$ appears in Figure 5.

In Theorem 8 we determine the exact value of the multiset dimension of the comb product of $P_n$ and $P_m$.

Theorem 8.

If $P_n{⊳}_{\circ }{P}_m$ is the comb product of $P_n$ and $P_m$ with $n,m\ge 4$, then $md\left(P_n{⊳}_{\circ }{P}_m\right)=3$.

Proof. 

Since $P_n{⊳}_{\circ }{P}_m$ is not a path, by Theorem 2, $md\left(P_n{⊳}_{\circ }{P}_m\right)\ge 3$. Assume $P_n{⊳}_{\circ }{P}_m$ has $V\left(P_n{⊳}_{\circ }{P}_m\right)=\{v_i^j:1\le i\le n,0\le j\le m-1\}$ and $E\left(P_n{⊳}_{\circ }{P}_m\right)=\{v_i^0{v}_{i+1}^0:1\le i\le n-1\}\cup \{v_i^j{v}_i^{j+1}:1\le i\le n;0\le j\le m-2\}.$ Let us show that the set $A=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$ is a multiset resolving set for the graph $P_n{⊳}_{\circ }{P}_m$. The vertices represented according to A are given in Table 9.

Therefore, any two vertices do not have the same multiset code or representation according to A, as shown in Table 9. This implies that $md\left(P_n{⊳}_{\circ }{P}_m\right)\le 3$. Hence, $md\left(P_n{⊳}_{\circ }{P}_m\right)=3.$ □

4.4. Results on the Edge-Multiset Dimension of Graphs

By definition of the edge-multiset dimension and the edge metric dimension, It is clear that the edge-multiset dimension of a connected graph $\mathsf{\Gamma }$ is at least the edge metric dimension of graph $\mathsf{\Gamma }$ which we prove in Lemma 1.

Lemma 1.

Let Γ be a connected graph. Then ${dim}_e\left(\mathsf{\Gamma }\right)\le m{d}_e\left(\mathsf{\Gamma }\right)$.

Proof. 

Let B be an edge resolving set for graph $\mathsf{\Gamma }$. If we have different edges f and g which have representation with respect to B as $r_e\left(f\right|B)=(a,b,c)$ and $r_e\left(g\right|B)=(b,a,c)$. For the edge metric dimension, the $r_e\left(f\right|B)\ne r_e\left(g\right|B)$. This satisfies the properties of the edge metric dimension. However, if we focus on the edge-multiset distance, which leads to $\{a,b,c\}=\{b,a,c\}$, this gives the same edge-multiset representation of edges f and g according to B, $r_{em}\left(f\right|B)=r_{em}\left(g\right|B)=\{a,b,c\}$. This does not satisfy the properties of the edge-multiset dimension. On the other hand, if we have two edges $f_1$ and $g_1$ which have representation according to B, $r_e\left(f_1\right|B)=(a,b,c)$ and $r_e\left(g_1\right|B)=(b,a,d)$, respectively, then this satisfies the properties of the edge metric dimension. Furthermore, $\{a,b,c\}\ne \{b,a,d\}$ shows that $f_1$ and $g_1$ have distinct edge-multiset representation with respect to B, that is $r_{em}\left(f_1\right|B)\ne r_{em}\left(g_1\right|B)$. Thus, we concludes that $di{m}_e\left(\mathsf{\Gamma }\right)\le m{d}_e\left(\mathsf{\Gamma }\right)$. □

To give an example of Lemma 1, assume graph $\mathsf{\Gamma }$ with $V\left(\mathsf{\Gamma }\right)=\{a_1,a_2,\cdots ,a_9\}$ and $E\left(\mathsf{\Gamma }\right)=\{f_1,f_2,\cdots ,f_9\}$ as given in Figure 6. Let the set $B=\{a_3,a_6,a_8\}$ be an edge resolving set for graph $\mathsf{\Gamma }$ and ${dim}_e\left(\mathsf{\Gamma }\right)=3$.

If two different edges $f_2$ and $f_9$ which have representation with respect to B as $r_e\left(f_2\right|B)=(1,2,3)$ and $r_e\left(f_9\right|B)=(3,2,1)$, respectively. For the edge metric dimension, $r_e\left(f_3\right|B)\ne r_e\left(f_9\right|B)$. This satisfies the properties of the edge metric dimension. However, if we focus on the edge-multiset distance, which leads to $\{1,2,3\}=\{3,2,1\}$, this gives the same edge-multiset representation of edges $f_2$ and $f_9$ according to B, $r_{em}\left(f_2\right|B)=r_{em}\left(f_9\right|B)=\{1,2,3\}$. This does not satisfy the properties of the edge-multiset dimension. Thus, we conclude that $di{m}_e\left(\mathsf{\Gamma }\right)\le m{d}_e\left(\mathsf{\Gamma }\right)$.

Theorem 9.

Let Γ be a graph. Then $m{d}_e\left(\mathsf{\Gamma }\right)=1$, if, and only if, $\mathsf{\Gamma }=P_n$.

Proof. 

Let $V\left(P_n\right)=\{w_i:1\le i\le n\}$ and $E\left(P_n\right)=\{e_1=w_i{w}_{i+1}:1\le i\le n-1\}$. In one direction, it is clear that the set $B=\left\{w_1\right\}$ is an edge-multiset basis for $P_n$, that is, $m{d}_e\left(P_n\right)=1$.

For the converse, assume that $\mathsf{\Gamma }$ is a connected graph with $m{d}_e\left(\mathsf{\Gamma }\right)=1$. Let $B=\left\{w_1\right\}$ be an edge-multiset basis of a graph $\mathsf{\Gamma }$. Hence, $r_{em}\left(e\right|B)\ne r_{em}\left(f\right|B)$ for every pair of edges e and $f\in E\left(\mathsf{\Gamma }\right)$. Since the representations of all edges of $\mathsf{\Gamma }$, according to B, are distinct, there must exist an edge g such that $r_{em}\left(g\right|B)=n-2$, where $n-1$ is the size of the graph G. Thus, the diameter of $\mathsf{\Gamma }$ is $n-1$, which implies that $\mathsf{\Gamma }$ is the path $P_n$. □

To give an example of Theorem 9, assume graph $\mathsf{\Gamma }=P_7$ with $V\left(P_7\right)=\{a,b,c,d,e,f,g\}$ and $E\left(P_7\right)=\{e_1,e_2,\cdots ,e_6\}$ as given in Figure 7.

It is noted, the set $B=\left\{a\right\}$ or $B=\left\{g\right\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }=P_7$. The set B gives unique edge-multisets representations of the edges of $\mathsf{\Gamma }=P_7$.

In the Lemma 2, we show that no graph $\mathsf{\Gamma }$ has an edge-multiset dimension of 2.

Lemma 2.

Let Γ be a connected graph. Then $m{d}_e\left(\mathsf{\Gamma }\right)\ne 2$.

Proof. 

If $\mathsf{\Gamma }$ is a path, then $m{d}_e\left(\mathsf{\Gamma }\right)=1$. So, we may assume that $\mathsf{\Gamma }\ne P_n$. Assume that $m{d}_e\left(\mathsf{\Gamma }\right)=2$ for some graph $\mathsf{\Gamma }$ and let $B=\{a,b\}$ be an edge resolving set for $\mathsf{\Gamma }$. If there are two edges $e=ax$ and $f=yb$ (it is possible that $x=y$) such that the vertices x and y lie on the shortest path between a and b, then $d(e,b)=d(f,a)$. Thus, $r_{em}\left(e\right|B)=\{0,d(e,b)\}=\{0,d(f,a)\}=r_{em}\left(e\right|B)$ is a contradiction. Now, if there does not exist such a pair of edges, then a and b are adjacent. Since $\mathsf{\Gamma }$ is not a path, $\mathsf{\Gamma }$ cannot be $P_2$, and so, one of the following possibilities must occur:

• (i). there are two edges incident to a or to b;

• (ii). there is one edge incident to a and one edge incident to b.

In both cases, we observe that two edges have the same multiset representation, which is impossible. Therefore, no graph $\mathsf{\Gamma }$ has an edge-multiset dimension equal to 2. □

To give an example of Lemma 2, assume graph $\mathsf{\Gamma }=L\left(T_{7,3}\right)$ with $V\left(L\left(T_{7,3}\right)\right)=\{a_1,a_2,\cdots ,a_7,b_1,b_2,b_3\}$ and $E\left(L\left(T_{7,3}\right)\right)=\{f_1,f_2,\cdots ,f_{11}\}$, as given in Figure 8. Let the set $B=\{a_2,b_3\}$ be an edge-multiset resolving set for $L\left(T_{7,3}\right)$.

There are two edges $f_1=a_1{a}_2$ and $f_{11=b_2{b}_3}$ such that the vertices $a_1$ and $b_2$ lie on the shortest path between $a_2$ and $b_3$, then $d(a_1,b_3)=d(b_2,a_2)=3$. Thus, $r_{em}\left(f_1\right|B)=\{0,d(a_1,b_3)\}=\{0,3\}=\{0,d(b_2,a_2)\}=r_{em}\left(e\right|B)$ is a contradiction.

As we know from Lemma 2, every connected graph different from the path has $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$.

Theorem 10.

For any connected graph Γ other than a path, $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$.

In view of the previous result, it is interesting to characterize the graphs having an edge-multiset dimension of 3 as we know that $dime\left(\mathsf{\Gamma }\right)=1$, if, and only if, $\mathsf{\Gamma }=P_n$ and we obtain the same result for the edge-multiset dimension.

4.5. Graphs Having an Infinite Edge-Multiset Dimension

In this section, we present a few conditions a graph needs to satisfy to have an infinite edge-multiset dimension. In Lemma 3, we show that if the distance between a vertex and an edge is no more than 2, then the graph $\mathsf{\Gamma }$ does not have an edge-multiset resolving set.

Lemma 3.

Let Γ be a graph with a set of vertices and edges, V and E, respectively, where $\left|V\right|\ge 2$. If the distance between a vertex and an edge is at most 2, then Γ does not contain an edge-multiset resolving set.

Proof. 

On the contrary, suppose that every pair of edges in E is of distance at most 2 and V is an edge-multiset resolving set of $\mathsf{\Gamma }$. We represent the vertices in V by $v_1,v_2,\cdots ,v_p$, where $p\ge 2$ and edges in E by $e_1,e_2,\cdots ,e_n$, where $n\ge p-1$. For $i=1,2,\cdots ,n$, we have $r_{em}\left(e_i\right|V)=\{0,0,1^{m_1},2^{m_2}\}$ where $m_1+m_2=p-2$. Therefore, we have p vertices in V and n edges in E. All edges have different representations with respect to V and their representations should be of the form $\{0,0,1^{p-2}\},\{0,0,1^{p-3},2\},\{0,0,1^{p-4}{2}^2\},\cdots \{0,0,2^{p-2}\}$. Without loss of generality, we assume that the edge having the representation $\{0,0,1^{p-2}\}$ is $e_1=v_1{v}_x$ and the edge having the representation $\{0,0,2^{p-2}\}$ is $e_n=v_p{v}_y$. Since $r_{em}\left(e_1\right|V)=\{0,0,1^{p-2}\}$, it follows that $r_{em}(e_1=v_1{v}_x|V\backslash \{v_1,v_x\})=\left\{1^{p-2}\right\}$ which is in contradiction to $r_{em}\left(e_n\right|V)=\{0,0,2^{p-2}\}$. Hence, V is not an edge-multiset resolving set of $\mathsf{\Gamma }$. □

To give an example of Lemma 3, assume graph $\mathsf{\Gamma }$ with $V\left(\mathsf{\Gamma }\right)=\{a_1,a_2,\cdots ,a_5\}$ and $E\left(\mathsf{\Gamma }\right)=\{f_1,f_2,\cdots ,f_5\}$, as given in Figure 9. The distance between a vertex a and an edge $e_3$ (or $e_4$) is 2.

Therefore, by Theorem 10, $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$. We note that the set $B=\{a,b,c\}$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$ as $r_{em}\left(e_1\right|B)=r_{em}\left(e_2\right|B)=\{0,0,1\}$. If the set $B_1=\{a,b,c,d\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$, then $r_{em}\left(e_1\right|B_1)=r_{em}\left(e_3\right|B_1)=\{0,0,1,2\}$, which means that the set $B_1$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$. If the set $B_2=\{a,b,c,d,e\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$, then $r_{em}\left(e_1\right|B_2)=r_{em}\left(e_3\right|B_2)=r_{em}\left(e_4\right|B_2)=\{0,0,1,1,2\}$, and $r_{em}\left(e_2\right|B_2)=r_{em}\left(e_5\right|B_2)=\{0,0,1,1,1\}$, which means that the set $B_2$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$. It is clear that an edge-multiset resolving set for $\mathsf{\Gamma }$ does not exist.

In Theorem 11, we classify the graphs whose edge-multiset dimension is not finite.

Theorem 11.

If any graph Γ has a vertex adjacent to at least three pendant vertices, then $m{d}_e\left(\mathsf{\Gamma }\right)=\infty$.

Proof. 

Assume that $v_1,v_2$ and $v_3$ are three pendant vertices adjacent to vertex $v_x$ in $\mathsf{\Gamma }$. Let $e_1=v_1{v}_x,e_2=v_2{v}_x$ and $e_3=v_3{v}_x$ be three edges incident on pendant vertices $v_1,v_2$ and $v_3$, respectively. Let B be any edge-multiset resolving set of graph $\mathsf{\Gamma }$, then either at least two of the pendant vertices $v_i\mathrm{or}{v}_j$ where $i,j=1,2,3$ and $i\ne j$, are in B or at least two of the pendant vertices are not in B. In both cases, edges $e_i$ and $e_j$ where $i,j=1,2,3$ and $i\ne j$, cannot be resolved because $r_{em}(e_i,v)=r_{em}(e_j,v)$ where $v\in V\left(\mathsf{\Gamma }\right)$. Hence, $\mathsf{\Gamma }$ contains a vertex adjacent to at least three pendant vertices. Thus, $m{d}_e\left(\mathsf{\Gamma }\right)=\infty$. □

To give an example of Theorem 11, assume graph $\mathsf{\Gamma }$ with $V\left(\mathsf{\Gamma }\right)=\{a,b,c,d,e,f,g\}$ and $E\left(\mathsf{\Gamma }\right)=\{e_1,e_2,\cdots ,e_6\}$, as given in Figure 10.

There are three pendant vertices $a,g$ and f. We note that the set $B=\{b,c,d,e\}$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$ as $r_{em}\left(e_1\right|B)=r_{em}\left(e_5\right|B)=r_{em}\left(e_6\right|B)=\{0,1,2,3\}$. If the set $B_1=\{a,b,c,d,e\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$, then $r_{em}\left(e_5\right|B_1)=r_{em}\left(e_6\right|B_1)=\{0,1,1,2,3\}$, which means that the set $B_1$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$. If the set $B_2=\{a,b,c,d,e,f\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$, then $r_{em}\left(e_1\right|B_2)=r_{em}\left(e_6\right|B_2)=\{0,0,1,1,2,3\}$, which means that the set $B_2$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$. If the set $B_3=\{a,b,c,d,e,f,g\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$, then $r_{em}\left(e_1\right|B_3)=r_{em}\left(e_5\right|B_3)=r_{em}\left(e_6\right|B_3)=\{0,0,1,1,1,2,3\}$, which means that the set $B_2$ is not an edge-multiset resolving set for $\mathsf{\Gamma }$. It is clear that the edge-multiset resolving set for $\mathsf{\Gamma }$ does not exist. Hence, $\mathsf{\Gamma }$ contains a vertex adjacent to three pendant vertices, then $m{d}_e\left(\mathsf{\Gamma }\right)=\infty$.

Example 1 give some graphs of infinite edge-multiset dimensions.

Example 1.

The following families of graphs have infinite edge-multiset dimensions. Complete graph, star graph, friendship graph, wheel graph, the Peterson graph, fan graph, complete bipartite graph and cycle graph with at most 6 vertices.

The edge-multiset resolving set is determined for only some connected graphs. If $\mathsf{\Gamma }$ is a connected graph for which $m{d}_e\left(\mathsf{\Gamma }\right)$ is decided, then each and every edge-multiset resolving set for $\mathsf{\Gamma }$ is an edge resolving set for $\mathsf{\Gamma }$, and so $1\le di{m}_e\left(\mathsf{\Gamma }\right)\le m{d}_e\left(\mathsf{\Gamma }\right)$

4.6. Graphs Having a Constant Edge-Multiset Dimension

Next, we present some families of graphs, cycle, kayak paddle, comb product of two paths, caterpillar and lobster which have constant edge-multiset dimensions. In Theorem 12, we show that $C_n$ has a constant edge-multiset dimension.

Theorem 12.

Let $C_n$ be a cycle graph with $n\ge 7$. Then $m{d}_e\left(C_n\right)=3$.

Proof. 

Therefore, by Theorem 10, $m{d}_e\left(C_n\right)\ge 3$. Assume $C_n=v_0{v}_1\cdots v_{n-1}{v}_0$. Let us show that the set $B=\{v_0,v_1,v_3\}$ is an edge-multiset resolving set for $C_n$.

If $n=2t$ with $t>3$, then the edge representations according to B are represented in Table 10 and Table 11.

If $n=2t+1$ with $t>3$, then the edge representations according to B are represented in Table 12 and Table 13.

Therefore, any two edges do not have the same multiset code or representation according to B, as shown in Table 10, Table 11, Table 12 and Table 13. This implies that $m{d}_e\left(C_n\right)\le 3$. Hence, $m{d}_e\left(C_n\right)=3$. □

In Theorem 13 we show that kayak paddle graph with $\vartheta ,\lambda ,\mu \ge 4$ has a constant edge-multiset dimension.

Theorem 13.

If $KP(\vartheta ,\lambda ,\mu )$ is a kayak paddle graph with $\vartheta ,\lambda ,\mu \ge 4$, then

$m{d}_e\left(KP(\vartheta ,\lambda ,\mu )\right)=3$

.

Proof. 

By Theorem 10, $m{d}_e\left(KP(\vartheta ,\lambda ,\mu )\right)\ge 3$. Let $V\left(KP(\vartheta ,\lambda ,\mu )\right)=\{{\alpha }_1,{\alpha }_2,\cdots {\alpha }_{\vartheta }\}\cup \{{\beta }_1,{\beta }_2,\cdots ,{\beta }_{\lambda }\}\cup \{{\gamma }_1,\cdots ,{\gamma }_{\mu -1}\}$ and $E\left(KP(\vartheta ,\lambda ,\mu )\right)=\{{\alpha }_i{\alpha }_{i+1}:1\le i\le \vartheta \}\cup \{{\beta }_j{\beta }_{j+1}:1\le j\le \lambda \}\cup \{{\gamma }_k{\gamma }_{k+1}:1\le k\le \mu -2\}\cup \{{\alpha }_1{\gamma }_1,{\gamma }_{\mu -1}{\beta }_1\}$, where ${\alpha }_{\vartheta +1}={\alpha }_1$ and ${\beta }_{\lambda +1}={\beta }_1$. All edges are labelled as follows.

$e_i={\alpha }_i{\alpha }_{i+1}:1\le i\le \vartheta e_j^{\prime }={\beta }_j{\beta }_{j+1}:1\le j\le \lambda$

$e_k^{\prime \prime }={\gamma }_k{\gamma }_{k-1}:2\le k\le \mu -1e_1^{\prime \prime }={\alpha }_1{\gamma }_1,e_{\mu }^{\prime \prime }={\gamma }_{\mu -1}{\beta }_1$

We show that the set $B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$ is an edge-multiset resolving set of $KP(\vartheta ,\lambda ,\mu )$.

If $\vartheta \ge 4$ with $t=\lfloor \frac{\vartheta }{2}\rfloor$, then the edge representations according to B are represented as follows in Table 14.

If $\lambda \ge 4$ with $t^{\prime }=\lfloor \frac{\lambda }{2}\rfloor$, then the edge representations according to B are represented in Table 15.

If $\mu \ge 4$, then the edge representations according to B are represented in Table 16.

Therefore, any two edges do not have the same multiset code or representation according to B, as shown in Table 14, Table 15 and Table 16. This implies that $m{d}_e\left(KP(\vartheta ,\lambda ,\mu )\right)\le 3$. Hence, $m{d}_e\left(KP(\vartheta ,\lambda ,\mu )\right)=3$. □

In the next theorem we determine the exact value of the multiset dimension of the dragon graph.

Theorem 14.

If $T_{n,m}$ is a dragon graph with $n\ge 4$ and $m\ge 3$, then $m{d}_e\left(T_{n,m}\right)=3$.

Proof. 

By Theorem 10, $m{d}_e\left(T_{n,m}\right)\ge 3$. Let $V\left(T_{n,m}\right)=\{v_i,u_j|1\le i\le n,1\le j\le m\}$ and $E\left(T_{n,m}\right)=\{v_i{v}_{i+1}:1\le i\le n\}\cup \{u_j{u}_{j+1}1\le j\le m-1\}\cup \left\{v_n{u}_1\right\}$, where $v_{n+1}=v_1$. The edges of $T_{n,m}$ are labelled as follows.

$f_i=\{v_i{v}_{i+1}:1\le i\le n\}$

$f_{j+1}^{\prime }=\{u_j{u}_{j+1}:1\le j\le m-1\},f_1^{\prime }=v_n{u}_1$

Now, we prove that $B=\{v_1,v_2,u_m\}$ is an edge-multiset resolving set for $T_{n,m}$.

If $n\ge 4$ is even with $t=\frac{n}{2}$, then the edge representations according to B are represented in Table 17.

If $n\ge 4$ is odd with $t=\lceil \frac{n}{2}\rceil$, then the edge representations according to B are represented in Table 18.

If $m\ge 4$, then the edge representations according to B are represented in Table 19.

Therefore, any two edges do not have the same multiset code or representation according to $B$, as shown in Table 17, Table 18 and Table 19. We have $m{d}_e\left(T_{n,m}\right)\le 3$. Hence, $m{d}_e\left(T_{n,m}\right)=3$. □

Theorem 15 determines the exact value of the edge-multiset dimension of a comb product of two paths $P_n$ and $P_m.$

Theorem 15.

If $P_n{⊳}_{\circ }{P}_m$ is the comb product of two paths $P_n$ and $P_m$, with $n,m\ge 4$, then $m{d}_e\left(P_n{⊳}_{\circ }{P}_m\right)=3$.

Proof. 

By Theorem 10, $m{d}_e\left(P_n{⊳}_{\circ }{P}_m\right)\ge 3$. Let $V\left(P_n{⊳}_{\circ }{P}_m\right)=\{v_i^j:1\le i\le n,0\le j\le m-1\}$ and the edges are labelled as follows.

$e_i^j=\left\{\begin{array}{cc}{v}_i^{j-1}{v}_i^j,\hfill & j\ne 0;\hfill \\ v_i^0{a}_{i+1}^0\hfill & j=0.\hfill \end{array}\right.1\le i\le n;0\le j\le m-1$

We show that the set $B=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$ is an edge-multiset resolving set for $P_n{⊳}_{\circ }{P}_m$. The edge representations according to B are represented in Table 20.

Therefore, any two edges do not have the same multiset code or representation according to B, as shown in Table 20. We thus deduced that $m{d}_e\left(P_n{⊳}_{\circ }{P}_m\right)\le 3$. Hence, $m{d}_e\left(P_n{⊳}_{\circ }{P}_m\right)=3.$ □

4.7. Caterpillar Graph

A caterpillar is a tree. A path graph is obtained if all a caterpillar graph’s leaves are removed. Throughout the article, we denote a caterpillar graph by $C{T}_n$ with a diametral path $P=(a_1,a_2,\dots ,a_n)$. $C{T}_n$ is a caterpillar with $deg\left(a_i\right)\le 3$ where $2\le i\le n-1$. Let $D=\left\{i\right|2\le i\le n-1\}$. Let $b_i$ be the pendent vertices of $C{T}_n$ of degree 1 joined to $a_i$. Thus, the vertex set of a caterpillar graph $C{T}_n$ is $V\left(C{T}_n\right)=\left\{a_i\right|1\le i\le n\}\cup \left\{b_i\right|i\in D\}$ and the edge set of a caterpillar graph $C{T}_n$ is $E\left(C{T}_n\right)=\left\{a_i{a}_{i+1}\right|1\le i\le n-1\}\cup \left\{a_i{b}_i\right|i\in D\}$. If $i\notin D$, then $a_i$ is a non-leg or gap vertex. A leg vertex has degree 3m=, a gap vertex $a_i$, $i\notin D$, and $deg\left(x_i\right)\le 2$. See Figure 11 for an example.

Theorem 16 shows that the edge-multiset dimension of a caterpillar graph is 3.

Theorem 16.

If $C{T}_n$ is a caterpillar graph with $n\ge 5$, then $m{d}_e\left(C{T}_n\right)=3$.

Proof. 

Therefore, by Theorem 10, $m{d}_e\left(C{T}_n\right)\ge 3$. If n is even and the set $B=\{a_1,a_{n-2},a_n\}$ is an edge-multiset resolving set for the graph $C{T}_n$, then the edge representations according to B are represented in Table 21.

If $i\in D$, then the edge representations according to B are represented in Table 22.

If n is odd, $i\in D$ and the set $B=\{a_1,a_2,a_n\}$ is an edge-multiset resolving set for the graph $C{T}_n$, then the edge representations according to B are represented in Table 23.

Therefore, no two edges have the same multiset code or representation according to B, as shown in Table 21, Table 22 and Table 23. We thus deduce that $m{d}_e\left(C{T}_n\right)\le 3$. Hence, $m{d}_e\left(C{T}_n\right)=3$. □

4.8. Lobster Graph

Throughout the article, we denote a lobster graph by $L_n$ with a diametral path $P=(x_1,x_2,\dots ,x_n)$. Obviously, $P_n$ is the spine of $L_n$. Let $L_n$ be a lobster with $deg\left(x_i\right)\le 3$ where $3\le i\le n-2$. Let $D=\left\{i\right|3\le i\le n-2\}$. If $i\in D$, then $x_i$ is a base-leg vertex. For $i\in D$, let $y_i$ be the vertex of $L_n$ of degree 2 joined to $x_i$, and $z_i$ be the pendent vertex of $L_n$ joined to $y_i$. Thus, the vertex set of lobster graph $L_n$ is $V\left(L_n\right)=\left\{x_i\right|1\le i\le n\}\cup \left\{y_i\right|i\in D\}\cup \left\{z_i\right|i\in D\}$ and the edge set of lobster graph $L_n$ is $E\left(L_n\right)=\left\{x_i{x}_{i+1}\right|1\le i\le n-1\}\cup \left\{x_i{y}_i\right|i\in D\}\cup \left\{y_i{z}_i\right|i\in D\}$. If $i\notin D$, then $x_i$ is a gap vertex or a non-leg vertex. Thus, a leg vertex is of degree 3, a gap vertex $x_i$, and $i\notin D$ is of degree $deg\left(x_i\right)\le 2$. See Figure 12 for an example.

Theorem 17 shows that a lobster graph also has a constant edge-mutiset dimension.

Theorem 17.

If $L_n$ is a lobster graph with $n\ge 5$, then $m{d}_e\left(L_n\right)=3$.

Proof. 

Therefore, by Theorem 10, $m{d}_e\left(L_n\right)\ge 3$. If n is even and the set $B=\{x_1,x_2,x_{n-1}\}$ is an edge-multiset resolving set for the graph $L_n$, then the edge representations according to B are represented in Table 24.

If $i\in D$ then the edge representations according to B are represented in the Table 25.

If n is odd and the set $B=\{x_1,x_2,x_n\}$ is an edge-multiset resolving set for the graph $L_n$, then the edge representations according to B are represented in the Table 26.

If $i\in D$, then the edge representations according to B are represented in Table 27.

Therefore, no two edges have the same multiset code or representation according to B as shown in Table 24, Table 25, Table 26 and Table 27. We thus deduce that $m{d}_e\left(L_n\right)\le 3$. Hence, $m{d}_e\left(L_n\right)=3$. □

4.9. Graphs Having Dependent Edge-Multiset Dimension on Their Order

In this section, Lemma 4 characterizes the trees of order n and diameter 3.

Lemma 4.

Let $T_n$ be a tree with order n and diameter 3. If $m{d}_e\left(T_n\right)\ne \infty$, then $m{d}_e\left(T_n\right)\le n-2$.

Proof. 

Therefore, if $diam\left(T_n\right)=3$ there exist two vertices a and b of $T_n$, such that $2\le deg\left(a\right),$$deg\left(b\right)\le 3$. We shall thus obtain the following three cases. See Figure 13 for visualization.

• If $deg\left(a\right)=deg\left(b\right)=2$, then $T_n\equiv P_4$ and $m{d}_e\left(T_n\right)=1=n-3$;

• If $deg\left(a\right)=2$ and $deg\left(b\right)=3$. Let $N\left(a\right)=\{a_1,b\}$ and $N\left(b\right)=\{a,b_1,b_2\}$. Then we have $B=\{a_1,a,b_1\}$ as an edge-multiset resolving set for $T_n$, which means $m{d}_e\left(T_n\right)=3=n-2$;

• If $deg\left(a\right)=deg\left(b\right)=3$. Let $N\left(a\right)=\{a_1,a_2,b\}$ and $N\left(b\right)=\{a,b_1,b_2\}$. Then we do not have an edge-multiset resolving set for $T_n$, which means $m{d}_e\left(T_n\right)=\infty$.

□

Theorem 18 gives the bounds of the edge-multiset dimension of trees with order $n,$ which is not a path.

Theorem 18.

Let $T_n$ be a tree with order n and $T_n$ as not a path. If $m{d}_e\left(T_n\right)\ne \infty$, then $3\le m{d}_e\left(T_n\right)\le n-2$.

Proof. 

As we know, if graph $\mathsf{\Gamma }$ is not a path graph then the edge-multiset dimension of any graph $\mathsf{\Gamma }$ is $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$ by Theorem 10. $T_n$ is a tree graph but not a path graph so, $m{d}_e\left(T_n\right)\ge 3$ which is the lower bound for $T_n$. It is clear that the edge-multiset dimension of $T_n$ is $m{d}_e\left(T_n\right)\le n-2$ by Lemma 4, so, we obtain $3\le m{d}_e\left(T_n\right)\le n-2$. □

In Theorem 19, the exact value of the edge-multiset dimension of a caterpillar graph is obtain.

Theorem 19.

If $C{T}_n$ is a caterpillar graph with $n\ge 5$, $deg\left(x_i\right)\le 4$ where $3\le i\le n-2$ and $D=\left\{i\right|3\le i\le n-2\}$, then $m{d}_e\left(L_n\right)=3+\left|D\right|$.

Proof. 

Let $C{T}_n$ be a caterpillar graph with a spine $P_n=(x_1,x_2,\dots ,x_n)$. Here, $deg\left(x_i\right)\le 4$ with $3\le i\le n-2$. Let $D=\left\{i\right|3\le i\le n-2\}$. For $i\in D$, let $y_i^1$ and $y_i^2$ be the pendant vertices of $C{T}_n$ of degree 1. Thus, the vertex set of a caterpillar graph $C{T}_n$ is $V\left(C{T}_n\right)=\left\{x_i\right|1\le i\le n\}\cup \{y_i^1,y_i^2|i\in D\}$ and the edge set of caterpillar graph $C{T}_n$ is $E\left(C{T}_n\right)=\left\{x_i{x}_{i+1}\right|1\le i\le n-1\}\cup \{x_i{y}_i^1,x_i{y}_i^2|i\in D\}$. If $i\notin D$, $x_i$ is called a gap vertex. Thus, a leg vertex is of degree 4, a gap vertex $x_i$, and $i\notin D$, is of degree $deg\left(x_i\right)\le 2$. See Figure 14 for an example.

Let the set $B=\{x_1,x_2,x_n,y_i^1|3\le i\le n-2\}$ by an edge-multiset resolving set for the graph $C{T}_n$. Suppose a vertex $y_i^1$ with $3\le i\le n-2$ is not an element of the set B. Then the edges $x_i{y}_i^1$, $x_i{y}_i^2$ have the same multiset distance from the elements of B, which is a contradiction. Therefore $y_i^1$, with $i\in D$, $3\le i\le n-2$, are elements of set B. If vertex $x_1$ is not an element of B, then the edges $x_2{x}_3$ and $x_3{y}_3^1$ have the same multiset distance from the elements of B, which is a contradiction. If vertex $x_2$ is not an element of B, then the edges $x_i{x}_{i+1}$ and $x_{n-i}{x}_{n-i+1}$, where $1\le i\le \lceil \frac{n}{2}\rceil -1$, have the same multiset distance from the elements of B, which is a contradiction. If vertex $x_n$ is not an elements of B, then the edges $x_{n-2}{x}_{n-1}$ and $x_{n-2}{y}_{n-2}^2$ have the same multiset distance from the elements of B, which is a contradiction. Therefore, $m{d}_e\left(C{T}_n\right)\ge 3+\left|D\right|$.

If $W=\{x_1,x_2,x_n\}$ is a subset of $V\left(C{T}_n\right)$, then the edge representations are presented in Table 28:

It is observed that the multiset distance of edges according to W is $r_{em}\left(x_i{y}_i^1\right|W)=r_{em}\left(x_i{y}_i^2\right|W)$ so, the vertices $y_i^1$ or $y_i^2$, where $i\in D$, $3\le i\le n-2$, are included in the set W. Therefore, $m{d}_e\left(C{T}_n\right)\le 3+\left|D\right|$. Hence, $m{d}_e\left(C{T}_n\right)=3+\left|D\right|$. □

In Theorem 20, the exact value of the edge-multiset dimension of a lobster graph is obtain.

Theorem 20.

If $L_n$ is a lobster graph with $n>5$, $deg\left(x_i\right)=4$, where $i\in D=\left\{i\right|3\le i\le n-2\}$, then $m{d}_e\left(L_n\right)=3+\left|D\right|$.

Proof. 

Let $L_n$ be a lobster graph with a spine $P_n=(x_1,x_2,\dots ,x_n)$. Here, $deg\left(x_i\right)\le 4$ and $3\le i\le n-2$. Let $D=\left\{i\right|3\le i\le n-2\}$. For all $x_i$ with $3\le i\le n-2$ there exist $i\in D$, such that $y_i^1$ and $y_i^2$ are the vertices of $L_n$ of degree 2 joined to $x_i$. $z_i^1$ and $z_i^2$ are the pendant vertices of $L_n$ joined to $y_i^1$ and $y_i^2$, respectively. Thus, the vertex set of a lobster graph $L_n$ is $V\left(L_n\right)=\left\{x_i\right|1\le i\le n\}\cup \{y_i^1,y_i^2|i\in D\}\cup \{z_i^1,z_i^2|i\in D\}$ and the edge set of the lobster graph $L_n$ is $E\left(L_n\right)=\left\{x_i{x}_{i+1}\right|1\le i\le n-1\}\cup \{x_i{y}_i^1,x_i{y}_i^2|i\in D\}\cup \{y_i^1{z}_i^1,y_i^2{z}_i^2|i\in D\}$. See Figure 15 for an example.

Let the set $B=\{x_1,x_2,x_n,y_{n-2}^1,z_i^1|3\le i\le n-3\}$ is an edge-multiset resolving set for the graph $L_n$. Suppose that a vertex $z_i^1$ with $3\le i\le n-3$ is not an element of the set B. Then the edges $x_i{y}_i^1$ and $x_i{y}_i^2$ have the same multiset distances from the elements of B, and the edges $y_i^1{z}_i^1$ and $y_i^2{z}_i^2$ also have the same multiset distances from the elements of B, which is a contradiction. Therefore, $y_i^1$ with $i\in D$, $3\le i\le n-3$ are elements of the set B. If vertex $x_1$ is not an element of B, then the edges $x_1{x}_2$ and $y_{n-2}^1{y}_{n-2}^2$ have the same multiset distances from the elements of B, and the edges $x_2{x}_3$ and $x_{n-2}{y}_{n-2}^1$ also have the same multiset distances from the element of B, which is a contradiction. If vertex $x_2$ is not an element of B, then the edges $x_1{x}_2$ and $y_3^1{y}_3^2$ and the edges $x_2{x}_3$ and $x_3{y}_3^1$ have the same multiset distances from the elements of B, which is a contradiction. If vertex $x_n$ is not an element of B, then the edges $x_{n-2}{x}_{n-1}$ and $x_{n-2}{y}_{n-2}^1$ and the edges $x_{n-1}{x}_n$ and $y_{n-2}^1{y}_{n-2}^2$ have the same multiset distances from the elements of B, which is a contradiction. If the set B does not contain $z_{n-2}^1$ the edges $x_{n-2}{y}_{n-2}^1$ and $x_{n-2}{y}_{n-2}^2$ and the edges $y_{n-2}^1{z}_{n-2}^1$ and $y_{n-2}^2{y}_{n-2}^2$ have the same multiset distances from the elements of B, which is a contradiction. Therefore, $m{d}_e\left(L_n\right)\ge 3+\left|D\right|$.

If $W=\{x_1,x_2,x_n\}$ is a subset of $V\left(L_n\right)$, then the edge representations are presented in Table 29:

It is clear that the multiset distance of edges according to W are $r_{em}\left(x_i{y}_i^1\right|W)=r_{em}\left(x_i{y}_i^2\right|W)$ and $r_{em}\left(y_i^1{z}_i^1\right|W)=r_{em}\left(y_i^2{z}_i^2\right|W)$. So, the vertices $z_i^1$ or $z_i^2$, where $i\in D$, $3\le i\le n-3$ and the vertex $y_{n-2}^1$, are included in the set W. Therefore, $m{d}_e\left(L_n\right)\le 3+\left|D\right|$. Hence, $m{d}_e\left(L_n\right)=3+\left|D\right|$. □

In Theorem 21, we show that the edge-multiset dimension of a complete r-ary tree is finite if, and only if, r is either 1 or 2. If r is greater than 2, then the edge-multiset dimension of the complete r-ary tree is infinite.

4.10. Complete r-ary Tree Graph

Theorem 21.

The multiset dimension of a complete r-ary tree is finite if, and only if, $r=1$ or 2. Moreover, if T is a complete binary tree of height h, then $m{d}_e\left(T\right)=2^h-1$.

Proof. 

Let T be a complete r-ary tree of height $h\ge 1$. If $r\ge 3$, by Theorem 11 , then $m{d}_e\left(T\right)=\infty$. If $r=1$, then T is a path and $m{d}_e\left(T\right)=1$.

Let $r=2$. If $h=1$, then T is a path with two edges and $m{d}_e\left(T\right)=1$. Consider the binary trees of height $h\ge 2$. Let the set B be any edge-multiset resolving set of T. Examine the last level h of T containing $2^{h-1}$ pairs of pendant vertices of distance two and the edges are linked with these pendant vertices of distance 1. From the pair of these pendant vertices, one vertex is necessary for set B; otherwise, the representation of edges linked with pendant edges is the same. Now, we examine the $h-1$ level of T, having $2^{h-2}$ pair of edges of distance 1. Edges of each pair have the same multiset representations according to the vertices in the set B, which are in level h, and these edges have the same distance to any other vertex of T. So, these pair of edges cannot be resolved by any other vertices, which means that exactly one of the vertex linked with each pair of edges of $h-1$ level is in the set B. Similarly, for the next level $h-2,h-3,\dots ,1$ we obtained $2^{h-1}+2^{h-2}+\dots +1=2^h-1$ vertices that must be in the set B. Thus, $m{d}_e\left(T\right)\ge 2^h-1$.

For every level l of T, where $1\le l\le h$, there are exactly $2^{l-1}$ pairs of edges of distance 1, these edges join the vertices of level $l-1$ and level l. Let the set B contain exactly one vertex of level l from each such pair. So, the $\left|B\right|={\sum }_{l=1}^h{2}^{l-1}=2^h-1$. We prove that the set B is an edge-multiset resolving set. Let us show that B resolves any two edges f and g of T. We consider two cases.

• The edges f and g are in different levels, say p and q, respectively, where $0\le p<q\le h$:

The distance between edge g joined to vertices of level q and $q-1$ and $2^{h-2}$ vertices of the set B in level h is $h+q-1$. There is no vertex in set B of distance $h+q-1$ from edge f. Thus, the edges g and f have different representations.

• The edges f and g are in the same level (the edges f and g are linked the vertices of levels $p-1$ and p), say p, where $0\le p\le h$:

The edges f and g have different representations if exactly one vertex of level p is linked with the edges f or g is in the set B. If there is no vertex of level p linked with the edges f and g in the set B or two vertices (a vertex linked with edge f and a vertex linked with edge g) are in the set B, then let us denote by v the central vertex of the path connecting edges f and g (initial and final vertex of the path are in level q). This path has an even length, say $2n$, and then v is in level $q-n$. The vertex v is adjacent to two vertices, say $v_1$ and $v_2$, in level $q-n+1$. The vertices $v_1$ and $v_2$ belong to the path containing the edges f and g and one vertex from $v_1$ and $v_2$ are in the set B, thus obtaining $d(f,v_1)\ne d(g,v_2)$. It can be easily verified that the edges f and g have the same multiset code or representation according to set $B\left\{v_1\right\}$. Hence, the set B is an edge-multiset resolving set and $m{d}_e\left(T\right)\le 2^h-1$. Hence, $m{d}_e\left(T\right)=2^h-1$. □

The complete 2-ary tree graph with $h=4$, as given in Figure 16, is an example of Theorem 21. The red vertices are included in the edge-multiset resolving set for a complete 2-ary tree graph with $h=4$.

5. Discussion on the Multiset and Edge-Multiset Dimensions of Graphs

It is already known from [17] that the edge metric and the metric dimensions of graphs are not comparable since there are graphs $\mathsf{\Gamma }$ for which $dim\left(\mathsf{\Gamma }\right)={dim}_e\left(\mathsf{\Gamma }\right)$, $dim\left(\mathsf{\Gamma }\right)>{dim}_e\left(\mathsf{\Gamma }\right)$ or $dim\left(\mathsf{\Gamma }\right)<{dim}_e\left(\mathsf{\Gamma }\right)$. In [28], a lot of families of graphs were described for which the edge dimension was greater than the vertex dimension $dim\left(\mathsf{\Gamma }\right)>{dim}_e\left(\mathsf{\Gamma }\right)$, and an open problem was presented in [17].

In concordance with this, it is natural to consider comparing the multiset and edge-multiset dimensions of graphs by wondering if a similar situation happens to the metric and edge metric dimensions. We next see that this is precisely the case. For instance, Section 4 there were given some values for the multiset and edge-multiset dimensions of some graphs (comb product of paths, kayak paddle graphs and dragon graphs), respectively. This shows that the equality $md\left(\mathsf{\Gamma }\right)=m{d}_e\left(\mathsf{\Gamma }\right)$ can be realized for some graphs $\mathsf{\Gamma }$ (another example could be paths and cycles). We next show that $md\left(\mathsf{\Gamma }\right)<m{d}_e\left(\mathsf{\Gamma }\right)$ and $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$ can also occur.

5.1. Graphs G with $md\left(\mathsf{\Gamma }\right)<m{d}_e\left(\mathsf{\Gamma }\right)$

To achieve our goal in this section, we consider $\mathsf{\Gamma }$ be the graph with vertex set $V\left(\mathsf{\Gamma }\right)=\{u_1,u_2,\dots ,u_{17}\}$ and edge set $E\left(\mathsf{\Gamma }\right)=\{e_1,e_2,\dots ,e_{18}\}$, as shown in Figure 17.

We note that, for instance, the set $A=\{u_3,u_{16},u_{17}\}$ is a multiset resolving set for $\mathsf{\Gamma }$. Since, the graph $\mathsf{\Gamma }$ is not a path graph, by Theorem 1, $md\left(\mathsf{\Gamma }\right)\ge 3$.

Table 30 shows the multiset representations of all vertices of $\mathsf{\Gamma }$ according to $A=\{u_3,u16,u_{17}\}$. Since no two vertices have the same multiset code or representation according to A, we deduce that $md\left(\mathsf{\Gamma }\right)\le 3$. So, by using Theorem 1 we have $md\left(\mathsf{\Gamma }\right)=3$.

Now, we note that for instance, the set $B=\{u_1,u_7,u_{13},u_{16}\}$ is an edge-multiset resolving set of $\mathsf{\Gamma }$. Since, the graph $\mathsf{\Gamma }$ is not a path graph, by Theorem 10, $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$.

Table 31 shows the edge-multiset representations of all edges of $\mathsf{\Gamma }$ according to B. Since any two edges do not have the identical edge-multiset code or representation according to B, we deduce that $m{d}_e\left(\mathsf{\Gamma }\right)\le 4$. We must show that $m{d}_e\left(\mathsf{\Gamma }\right)\ge 4$.

On the contrary, suppose that $m{d}_e\left(\mathsf{\Gamma }\right)=3$; no two edges have the same edge-multiset representation.

• If $B_1=\{u_1,v_{13},v_{16}\}$ is an edge-multiset resolving set, then $r_{em}\left(e_1\right|B_1)=r_{em}\left(e_{16}\right|B_1)=\{0,2,4\}$ which is in contradiction to our supposition.

• If $B_2=\{u_7,u_{13},u_{16}\}$ is an edge-multiset resolving set, then $r_{em}\left(e_{10}\right|B_2)=r_{em}\left(e_{18}\right|B_2)=\{2,3,5\}$ which is in contradiction to our supposition.

• If $B_3=\{u_1,u_7{u}_{13}\}$ is an edge-multiset resolving set, then $r_{em}\left(e_{12}\right|B_3)=r_{em}\left(e_{13}\right|B_3)=\{0,1,5\}$ which is in contradiction to our supposition.

• If $B_4=\{u_1,v_7,v_{16}\}$ is an edge-multiset resolving set, then $r_{em}\left(e_{e_i}\right|B_4)=r_{em}\left(e_{13-i}\right|B_4)$ for $1\le i\le 6$, $r_{em}\left(e_{13}\right|B_4)=r_{em}\left(e_{18}\right|B_4)=\{1,3,5\}$ and $r_{em}\left(e_{14}\right|B_4)=r_{em}\left(e_{17}\right|B_4)=\{2,2,6\}$ which is in contradiction to our supposition.

Now, it is clear that $m{d}_e\left(\mathsf{\Gamma }\right)\ge 4$. Hence, $m{d}_e\left(\mathsf{\Gamma }\right)=4$.

Remark 1.

The graph Γ given in Figure 17 satisfies the inequality $md\left(\mathsf{\Gamma }\right)<m{d}_e\left(\mathsf{\Gamma }\right)$.

5.2. Graphs G with $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$

Let $\mathsf{\Gamma }$ be the graph with vertex set $V\left(\mathsf{\Gamma }\right)=\{v_1,v_2,\dots ,v_{19}\}$ and edge set $E\left(\mathsf{\Gamma }\right)=\{e_1,e_2,\dots ,e_{21}\}$, as shown in Figure 18.

We note that, for instance, the set $B=\{v_2,v_3,v_{12}\}$ is an edge-multiset resolving set for $\mathsf{\Gamma }$. Since, the graph $\mathsf{\Gamma }$ is not a path graph, by Theorem 10, $m{d}_e\left(\mathsf{\Gamma }\right)\ge 3$.

Table 32 shows the edge-multiset representations of all the edges of $\mathsf{\Gamma }$ according to $B=\{v_2,v_3,v_{12}\}$. Since no two edges have the same edge-multiset code or representation according to B, we deduce that $m{d}_e\left(\mathsf{\Gamma }\right)\le 3$. So, by using Theorem 10 we have $m{d}_e\left(\mathsf{\Gamma }\right)=3$.

Now, we note that, for instance, the set $A=\{v_2,v_4,v_9,v_{19}\}$ is a multiset resolving set for $\mathsf{\Gamma }$. Since the graph $\mathsf{\Gamma }$ is not a path graph, by Theorem 1, $md\left(\mathsf{\Gamma }\right)\ge 3$.

Table 33 shows the multiset representations of all vertices of $\mathsf{\Gamma }$ according to A. Since no two vertices have the same multiset code or representation according to A, we deduce that $md\left(\mathsf{\Gamma }\right)\le 4$. We must show that $md\left(\mathsf{\Gamma }\right)\ge 4$. On the contrary, suppose that $md\left(\mathsf{\Gamma }\right)=3$; no two vertices have the same multiset representation.

• If $A_1=\{v_2,v_4,v_9\}$ is a multiset resolving set, then $r_m\left(v_{13}\right|A_1)=r_m\left(v_{14}\right|A_1)=\{4,5,6\}$, which is a contradiction to our supposition.

• If $A_2=\{v_2,v_4,v_{19}\}$ is a multiset resolving set, then $r_m\left(v_1\right|A_2)=r_m\left(v_5\right|A_2)=\{1,3,3\}$, $r_m\left(v_2\right|A_2)=r_m\left(v_4\right|A_2)=\{0,2,4\}$, $r_m\left(v_6\right|B_2)=r_m\left(v_{16}\right|B_2)=\{2,2,4\}$, $r_m\left(v_7\right|A_2)=r_m\left(v_{15}\right|A_2)=\{1,3,5\}$, $r_m\left(v_8\right|A_2)=r_m\left(v_{14}\right|A_2)=\{2,4,6\}$, $r_m\left(v_9\right|A_2)=r_m\left(v_{13}\right|A_2)=\{3,5,6\}$ and $r_m\left(v_{11}\right|A_2)=r_m\left(v_{12}\right|A_2)=\{4,5,5\}$, which is a contradiction to our supposition.

• If $A_3=\{v_2,v_9,v_{19}\}$ is a multiset resolving set, then $r_m\left(v_4\right|A_3)=r_m\left(v_{11}\right|A_3)=r_m\left(v_{14}\right|A_3)=\{2,4,5\}$, which is a contradiction to our supposition.

• If $A_4=\{v_4,v_9,v_{19}\}$ is a multiset resolving set, then $r_m\left(v_1\right|A_4)=r_m\left(v_{17}\right|A_4)=\{3,3,6\}$, $r_m\left(v_2\right|A_4)=r_m\left(v_{18}\right|A_4)=\{2,4,6\}$ and $r_m\left(v_{11}\right|A_4)=r_m\left(v_{16}\right|A_4)=\{2,4,5\}$, which is a contradiction to our supposition.

It is clear that $md\left(\mathsf{\Gamma }\right)\ge 4$. Hence, $md\left(\mathsf{\Gamma }\right)=4$.

Remark 2.

The graph Γ given in Figure 18 satisfies the inequality $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$.

6. Conclusions

In this work, we defined the notion of the edge-multiset dimension of graphs. We have noted that the multiset dimension $md\left(\mathsf{\Gamma }\right)$ and edge-multiset dimension $m{d}_e\left(\mathsf{\Gamma }\right)$ of graphs are generally not comparable. We have given examples of graphs $\mathsf{\Gamma }$, where $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$, $md\left(\mathsf{\Gamma }\right)<m{d}_e\left(\mathsf{\Gamma }\right)$, or $md\left(\mathsf{\Gamma }\right)=m{d}_e\left(\mathsf{\Gamma }\right)$. In particular, we found the exact values of the multiset dimension and edge-multiset dimension of the kayak paddle, dragon, and comb product of $P_n$ and $P_m$ graphs. We have proven that they have the same multiset dimension and edge-multiset dimension. Furthermore, the edge-multiset dimension of a connected graph is at least the edge metric dimension. No graph has an edge-multiset dimension of 2, which means every connected graph (other than the path graph whose edge-multiset dimension is one) always has an edge-multiset dimension greater than or equal to three.

Further, we classify the graphs as having infinite edge-multiset dimensions. Some classes of graphs with constant edge-multiset dimensions are also discussed. Graphs with dependent edge-multiset dimensions on their order have also been studied. In the end, we compare the multiset and edge-multiset dimensions of the graph.

The less explored case is that of $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$. In connection with all our expositions, we remark on some possible future lines that could be explored on this topic.

Problem 1.

What is the computational complexity of the edge-multiset dimension of a graph?

Problem 2.

Let Γ be a graph such that $md\left(\mathsf{\Gamma }\right)$ and $m{d}_e\left(\mathsf{\Gamma }\right)$ are finite. Can all graphs Γ for which $md\left(\mathsf{\Gamma }\right)>m{d}_e\left(\mathsf{\Gamma }\right)$, $md\left(\mathsf{\Gamma }\right)<m{d}_e\left(\mathsf{\Gamma }\right)$, or $md\left(\mathsf{\Gamma }\right)=m{d}_e\left(\mathsf{\Gamma }\right)$ be characterized?

Problem 3.

Is there any relationship between the multiset and edge-multiset dimensions with the classical metric and edge metric dimensions of a graph?

Problem 4.

Let Γ be a graph with n vertices. If $m{d}_e\left(\mathsf{\Gamma }\right)$ is finite, can any upper and/or lower bounds with respect to n be found for $m{d}_e\left(\mathsf{\Gamma }\right)$?

Author Contributions

Conceptualization, H.M.I. and H.M.A.S.; methodology, H.M.I., R.I. and M.F.N.; validation, H.M.I., H.M.A.S. and M.F.N.; formal analysis, H.M.I. and R.I.; investigation, H.M.I., R.I. and H.M.A.S.,; writing—original draft preparation, H.M.A.S. and H.M.I.; writing—review and editing, R.I. and M.F.N.; funding acquisition, R.I. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

All the data used to finding the results is included in the manuscript.

Acknowledgments

The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through the Larg Groups Project under grant number (R.G.P.2/163/44).

Conflicts of Interest

The authors have no conflict of interest to disclose.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. A graph with the [Forumla omitted. See PDF.].

Figure 2. Diagram for the multiset and edge-multiset dimension.

Figure 3. The kayak paddle graph [Forumla omitted. See PDF.].

Figure 4. The dragon graph [Forumla omitted. See PDF.].

Figure 5. The comb product of [Forumla omitted. See PDF.] and [Forumla omitted. See PDF.], [Forumla omitted. See PDF.].

Figure 6. The graph [Forumla omitted. See PDF.].

Figure 7. The graph [Forumla omitted. See PDF.].

Figure 8. The graph [Forumla omitted. See PDF.].

Figure 9. The graph [Forumla omitted. See PDF.].

Figure 10. The graph [Forumla omitted. See PDF.].

Figure 11. Caterpillar graph [Forumla omitted. See PDF.] with [Forumla omitted. See PDF.].

Figure 12. Lobster graph [Forumla omitted. See PDF.] with [Forumla omitted. See PDF.].

Figure 13. Three cases of graph [Forumla omitted. See PDF.] with diameter 3.

Figure 14. Caterpillar graph [Forumla omitted. See PDF.] with [Forumla omitted. See PDF.].

Figure 15. Lobster graph [Forumla omitted. See PDF.] with [Forumla omitted. See PDF.].

Figure 16. Complete 2-ary tree graph with [Forumla omitted. See PDF.].

Figure 17. The graph [Forumla omitted. See PDF.].

Figure 18. The graph [Forumla omitted. See PDF.].

Table 1

The multiset representations of the vertices of G with respect to the set $A=\{v_2,v_3,v_7\}$.

$v_i$	$v_1$	$v_2$	$v_3$	$v_4$
$r_m(v_i,A)$	$\{1,2,1\}$	$\{0,1,2\}$	$\{1,0,3\}$	$\{2,1,4\}$
$v_i$	$v_5$	$v_6$	$v_7$	$v_8$
$r_m(v_i,A)$	$\{3,2,3\}$	$\{2,3,2\}$	$\{2,3,0\}$	$\{3,2,5\}$

Table 2

The multiset representations of the edges of G according to the set $B=\{v_2,v_3,v_7\}$.

Edges	a	b	c	d
$r_{em}(.,B)$	$\{0,1,1\}$	$\{0,0,2\}$	$\{1,0,3\}$	$\{2,1,3\}$
Edges	e	f	g	h
$r_{em}(.,B)$	$\{2,2,2\}$	$\{1,2,1\}$	$\{1,2,0\}$	$\{2,1,4\}$

Table 3

The multiset representations of the vertices of $KP(\vartheta ,\lambda ,\mu )$, for $\vartheta \ge 4$ with $t=\lfloor \frac{\vartheta }{2}\rfloor +1$ according to the set $A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_m(.,.)$	$A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$
${\alpha }_1$	$\{1,1,\mu +1\}$
${\alpha }_i\text{:}2\le i\le t$	$\{i-2,i,\mu +i\}$
${\alpha }_i\text{:}i=t+1$	$\{i-2,\vartheta -i+2,\vartheta +\mu -i+2\}$
${\alpha }_i\text{:}t+2\le i\le \vartheta$	$\{\vartheta -i+2,\vartheta -i+2,\vartheta +\mu -i+2\}$

Table 4

The multiset representations of the vertices of $KP(\vartheta ,\lambda ,\mu )$, for $\lambda \ge 4$ with $t^{\prime }=\lfloor \frac{\lambda }{2}\rfloor +1$ according to the set $A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_m(.,.)$	$A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$
${\beta }_1$	$\{1,\mu -1,\mu +1\}$
${\beta }_j\text{:}2\le j\le t^{\prime }$	$\{j-2,\mu +j-2,\mu +j\}$
${\beta }_j\text{:}j=t^{\prime }+1$	$\{j-2,\lambda +\mu -j+2,\lambda +\mu -j\}$
${\beta }_j\text{:}{t}^{\prime }+2\le j\le \lambda$	$\{\lambda -j+2,\lambda +\mu -j+2,\lambda +\mu -j\}$

Table 5

The multiset representations of the vertices of $KP(\vartheta ,\lambda ,\mu )$, for $\mu \ge 4$, according to the set $A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_m(.,.)$	${\gamma }_k\text{:}1\le k\le \mu -1$
$A=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$	$\{k+1,k-1,\mu -k+1\}$

Table 6

The multiset representations of the vertices of $T_{n,m}$, for $n\ge 4$, even and $t=\frac{n}{2}$ according to the set $A=\{v_1,v_2,u_m\}$.

$r_m(.,.)$	$A=\{v_1,v_2,u_m\}$
$v_1$	$\{0,1,m+1\}$
$v_i\text{:}2\le i\le t$	$\{i-1,i-2,m+i\}$
$v_{t+1}$	$\{t,t-1,m+t-1\}$
$v_i\text{:}t+2\le i\le n$	$\{n-i+1,n-i+2,n+m-i\}$

Table 7

The multiset representations of the vertices of $T_{n,m}$, for $n\ge 4$, odd and $t=\lfloor \frac{n}{2}\rfloor$ according to the set $A=\{v_1,v_2,u_m\}$.

$r_m(.,.)$	$A=\{v_1,v_2,u_m\}$
$v_1$	$\{0,1,m+1\}$
$v_i\text{:}2\le i\le t$	$\{i-1,i-2,m+i\}$
$v_{t+1}$	$\{t,t-1,m+t\}$
$v_{t+2}$	$\{t,t,m+t-1\}$
$v_i\text{:}t+3\le i\le n$	$\{n-i+1,n-i+2,n+m-i\}$

Table 8

The multiset representations of the vertices of $T_{n,m}$, for $m\ge 4$ according to the set $A=\{v_1,v_2,u_m\}$.

$r_m(.,.)$	$A=\{v_1,v_2,u_m\}$
$u_j\text{:}1\le j\le m$	$\{j+1,j+2,m-j\}$

Table 9

The multiset representations of the vertices of $P_n{⊳}_{\circ }{P}_m$ according to the set $A=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$.

$r_m(.,.)$	$A=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$
$v_1^j\text{:}1\le j\le m-1$	$\{m-j-1,j,n+m+j-2\}$
$v_i^0\text{:}1\le i\le n$	$\{m+i-2,i-1,n+m-i-1\}$
$v_n^j\text{:}1\le j\le m-1$	$\{n+m+j-2,n+j-1,m-j-1\}$
$v_i^j\text{:}2\le i\le n-1,1\le j\le m-1$	$\{m+i+j-2,i+j-1,n+m+j-i-1\}$

Table 10

The edge-multiset representations of the edges of $C_n$ according to the set $B=\{v_0,v_1,v_3\}$.

$r_{em}(.,.)$	$e_0$	$e_1$	$e_2$
$B=\{v_0,v_1,v_3\}$	$\{0,0,2\}$	$\{0,1,1\}$	$\{0,1,2\}$
$r_{em}(.,.)$	$e_3$	$e_t$	$e_{t+1}$
$B=\{v_0,v_1,v_3\}$	$\{0,2,3\}$	$\{t-3,t-1,t-1\}$	$\{t-2,t-2,t-1\}$
$r_{em}(.,.)$	$e_{t+2}$	$e_{t+3}$
$B=\{v_0,v_1,v_3\}$	$\{t-3,t-2,t-1\}$	$\{t-4,t-3,t-1\}$

Table 11

The edge-multiset representations of the edges of $C_n$ according to the set $B=\{v_0,v_1,v_3\}$.

$r_{em}(.,.)$	$e_i\text{:}3<i<t$	$e_{t+i}\text{:}3<i<t$
$B=\{v_0,v_1,v_3\}$	$\{i-3,i-1,i\}$	$\{t-i-1,t-i,t-i+2\}$

Table 12

The edge-multiset representations of the edges of $C_n$ according to the set $B=\{v_0,v_1,v_3\}$.

$r_{em}(.,.)$	$e_0$	$e_1$	$e_2$	$e_3$
$B=\{v_0,v_1,v_3\}$	$\{0,0,2\}$	$\{0,1,1\}$	$\{0,1,2\}$	$\{0,2,3\}$
$r_{em}(.,.)$	$e_t$	$e_{t+1}$	$e_{t+2}$	$e_{t+3}$
$B=\{v_0,v_1,v_3\}$	$\{t-3,t-1,t\}$	$\{t-2,t-1,t\}$	$\{t-2,t-1,t-1\}$	$\{t-3,t-2,t\}$

Table 13

The edge-multiset representations of the edges of $C_n$ according to the set $B=\{v_0,v_1,v_3\}$.

$r_{em}(.,.)$	$e_i\text{:}3<i<t$	$e_{t+i}\text{:}3<i<t$
$B=\{v_0,v_1,v_3\}$	$\{i-3,i-1,i\}$	$\{t-i,t-i+1,t-i+3\}$

Table 14

The edge-multiset representations of the edges of $KP(\vartheta ,\lambda ,\mu )$ according to the set $B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_{em}(.,.)$	$B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$
$e_1$	$\{0,1,\mu +1\}$
$e_i\text{:}2\le i\le t$	$\{i-2,i,\mu +i\}$
$e_i\text{:}i=t+1$	$\{i-2,\vartheta -i+1,\vartheta +\mu -i+1\}$
$e_i\text{:}t+2\le i\le \vartheta$	$\{\vartheta -i+1,\vartheta -i+1,\vartheta +\mu -i+1\}$

Table 15

The edge-multiset representations of the edges of $KP(\vartheta ,\lambda ,\mu )$ according to the set $B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_{em}(.,.)$	$B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$
$e_1^{\prime }$	$\{0,\mu -1,\mu +1\}$
$e_j^{\prime }\text{:}2\le j\le t^{\prime }$	$\{j-2,\mu +j-2,\mu +j\}$
$e_j^{\prime }\text{:}j=t^{\prime }+1$	$\{j-2,\lambda +\mu -j-1,\lambda +\mu -j+1\}$
$e_j^{\prime }\text{:}{t}^{\prime }+2\le j\le \lambda$	$\{\lambda -j+1,\lambda +\mu -j-1,\lambda +\mu -j+1\}$

Table 16

The edge-multiset representations of the edges of $KP(\vartheta ,\lambda ,\mu )$ according to the set $B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$.

$r_{em}(.,.)$	$e_1^{\prime \prime }$	$e_k^{\prime \prime }\text{:}2\le k\le \mu$
$B=\{{\alpha }_2,{\beta }_2,{\gamma }_1\}$	$\{0,1,\mu -k+1\}$	$\{k-2,k,\mu -k+1\}$

Table 17

The edge-multiset representations of the edges of $T_{n,m}$ according to the set $B=\{v_1,v_2,u_m\}$.

$r_{em}(.,.)$	$B=\{v_1,v_2,u_m\}$
$f_1$	$\{0,0,m+1\}$
$f_i\text{:}2\le i\le t-1$	$\{i-1,i-2,m+i\}$
$f_t$	$\{t-1,t-2,m+t-1\}$
$f_{t+1}$	$\{t,t,m+t-2\}$
$f_i\text{:}t+2\le i\le n-1$	$\{n-i,n-i+1,n+m-i-1\}$
$f_n$	$\{0,1,m\}$

Table 18

The edge-multiset representations of the edges of $T_{n,m}$ according to the set $B=\{v_1,v_2,u_m\}$.

$r_{em}(.,.)$	$B=\{v_1,v_2,u_m\}$
$f_1$	$\{0,0,m+1\}$
$f_i\text{:}2\le i\le t-1$	$\{i-1,i-2,m+i\}$
$f_t$	$\{t-1,t-2,m+t-2\}$
$f_{t+1}$	$\{t-1,t-2,m+t-3\}$
$f_i\text{:}t+2\le i\le n-1$	$\{n-i,n-i+1,n+m-i-1\}$
$f_n$	$\{0,1,m\}$

Table 19

The edge-multiset representations of the edges of $T_{n,m}$ according to the set $B=\{v_1,v_2,u_m\}$.

$r_{em}(.,.)$	$B=\{v_1,v_2,u_m\}$
$f_j^{\prime }\text{:}1\le j\le m$	$\{j,j+1,m-j\}$

Table 20

The edge-multiset representations of the edges of $P_n{⊳}_{\circ }{P}_m$ according to the set $B=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$.

$r_{em}(.,.)$	$B=\{v_1^{m-1},v_1^0,v_n^{m-1}\}$
$e_1^j\text{:}1\le j\le m-1$	$\{m-j-1,j-1,n+m+j-3\}$
$e_i^0\text{:}1\le i\le n$	$\{m+i-2,i-1,n+m-i-2\}$
$e_n^j\text{:}1\le j\le m-1$	$\{n+m+j-3,n+j-2,m-j-1\}$
$e_i^j\text{:}2\le i\le n-1,1\le j\le m-1$	$\{m+i+j-3,i+j-2,n+m+j-i-2\}$

Table 21

The edge-multiset representations of the edges of $C{T}_n$ according to the set $B=\{a_1,a_{n-2},a_n\}$.

$r_{em}(.,.)$	$B=\{a_1,a_{n-2},a_n\}$
$a_1{a}_2$	$\{0,n-i-1,n-4\}$
$a_i{a}_{i+1}\text{:}2\le i\le n-3$	$\{i-1,n-i-1,n-i-3\}$
$a_{n-2}{a}_{n-1}$	$\{i-1,n-i-1,0\}$
$a_{n-1}{a}_n$	$\{i-1,n-i-1,1\}$

Table 22

The edge-multiset representations of the edges of $C{T}_n$ according to the set $B=\{a_1,a_{n-2},a_n\}$.

$r_{em}(.,.)$	$a_i{b}_i\text{:}2\le i\le n-2$	$a_{n-1}{b}_{n-1}$
$B=\{a_1,a_{n-2},a_n\}$	$\{i-1,n-i,n-i-2\}$	$\{i-1,n-i,1\}$

Table 23

The edge-multiset representations of the edges of $C{T}_n$ according to the set $B=\{a_1,a_2,a_n\}$.

$r_{em}(.,.)$	$a_1{a}_2$	$a_i{a}_{i+1}\text{:}2\le i\le n-1$	$a_i{b}_i\text{:}2\le i\le n-1$
$B=\{a_1,a_2,a_n\}$	$\{0,n-2,0\}$	$\{i-1,i-2,n-i-1\}$	$\{i-1,i-2,n-i\}$

Table 24

The edge-multisets representations of the edges of $L_n$ according to the set $B=\{x_1,x_2,x_{n-1}\}$.

$r_{em}(.,.)$	$x_1{x}_2$	$x_i{x}_{i+1}\text{:}2\le i\le n-2$	$x_{n-1}{x}_n$
$B=\{x_1,x_2,x_{n-1}\}$	$\{0,0,n-3\}$	$\{i-1,i-2,n-i-2\}$	$\{i-1,i-2,0\}$

Table 25

The edge-multisets representations of the edges of $L_n$ according to the set $B=\{x_1,x_2,x_{n-1}\}$.

$r_{em}(.,.)$	$x_i{y}_i\text{:}3\le i\le n-2$	$y_i{z}_i\text{:}3\le i\le n-2$
$B=\{x_1,x_2,x_{n-1}\}$	$\{i-1,i-2,n-i-1\}$	$\{i,i-1,n-i\}$

Table 26

The edge-multisets representations of the edges of $L_n$ according to the set $B=\{x_1,x_2,x_n\}$.

$r_{em}(.,.)$	$x_1{x}_2$	$x_i{x}_{i+1}\text{:}2\le i\le n-1$
$B=\{x_1,x_2,x_n\}$	$\{0,0,n-2\}$	$\{i-1,i-2,n-i-1\}$

Table 27

The edge-multisets representations of the edges of $L_n$ according to the set $B=\{x_1,x_2,x_n\}$.

$r_{em}(.,.)$	$x_i{y}_i\text{:}3\le i\le n-2$	$y_i{z}_i\text{:}3\le i\le n-2$
$B=\{x_1,x_2,x_n\}$	$\{i-1,i-2,n-i\}$	$\{i,i-1,n-i+1\}$

Table 28

The edge-multisets representations of some edges of $C{T}_n$ according to the set $W=\{x_1,x_2,x_n\}$.

$r_{em}(.,.)$	$x_1{x}_2$	$x_i{x}_{i+1}\text{:}2\le i\le n-1$	$x_i{y}_i^1,x_i{y}_i^2\text{:}3\le i\le n-2$
$W=\{x_1,x_2,x_n\}$	$\{0,0,n-2\}$	$\{i-1,i-2,n-i-1\}$	$\{i-1,i-2,n-i\}$

Table 29

The edge-multiset representations of some edges of $L_n$ according to the set $W=\{x_1,x_2,x_n\}$.

$r_{em}(.,.)$	$x_1{x}_2$	$x_i{x}_{i+1}\text{:}2\le i\le n-1$	$x_i{y}_i^1,x_i{y}_i^2\text{:}3\le i\le n-2$	$y_i^1{z}_i^1,y_i^2{z}_i^2\text{:}3\le i\le n-2$
$W=\{x_1,x_2,x_n\}$	$\{0,0,n-2\}$	$\{i-1,i-2,n-i-1\}$	$\{i-1,i-2,n-i\}$	$\{i,i-1,n-i+1\}$

Table 30

The multiset representations of the vertices of $\mathsf{\Gamma }$ according to the set $A=\{u_3,v_{16},v_{17}\}$.

$u_i$	$u_1$	$u_2$	$u_3$	$u_4$	$u_5$	$u_6$
$r_m(u_i,A)$	$\{2,2,5\}$	$\{1,1,4\}$	$\{0,2,5\}$	$\{1,3,6\}$	$\{2,4,7\}$	$\{3,5,8\}$
$u_i$	$u_7$	$u_8$	$u_9$	$u_{10}$	$u_{11}$	$u_{12}$
$r_m(u_i,A)$	$\{4,6,9\}$	$\{5,7,8\}$	$\{6,6,7\}$	$\{5,5,6\}$	$\{4,4,5\}$	$\{3,3,4,\}$
$u_i$	$u_{13}$	$u_{14}$	$u_{15}$	$u_{16}$	$u_{17}$
$r_m(u_i,A)$	$\{2,3,4\}$	$\{1,2,3\}$	$\{1,2,4\}$	$\{0,3,5\}$	$\{0,2,3\}$

Table 31

The edge-multiset representations of the edges of $\mathsf{\Gamma }$ according to the set $B=\{u_1,u_7,u_{13},u_{16}\}$.

$e_i$	$e_1$	$e_2$	$e_3$	$e_4$	$e_5$	$e_6$
$r_{em}(e_i,B)$	$\{0,2,5,4\}$	$\{1,3,4,4\}$	$\{2,3,4,5\}$	$\{2,3,5,6\}$	$\{1,4,6,7\}$	$\{0,5,6,8\}$
$e_i$	$e_7$	$e_8$	$e_9$	$e_{10}$	$e_{11}$	$e_{12}$
$r_{em}(e_i,B)$	$\{0,5,5,8\}$	$\{1,4,4,7\}$	$\{2,3,3,6\}$	$\{2,2,3,5\}$	$\{1,1,4,4\}$	$\{0,1,4,5\}$
$e_i$	$e_{13}$	$e_{14}$	$e_{15}$	$e_{16}$	$e_{17}$	$e_{18}$
$r_{em}(e_i,B)$	$\{0,1,3,5\}$	$\{0,2,2,6\}$	$\{1,1,3,7\}$	$\{0,2,4,8\}$	$\{1,2,2,6\}$	$\{1,2,3,5\}$

Table 32

The edge-multiset representations of the edges of $\mathsf{\Gamma }$ according to the set $B=\{v_2,v_3,v_{12}\}$.

$e_i$	$e_1$	$e_2$	$e_3$	$e_4$	$e_5$	$e_6$	$e_7$
$r_{em}(e_i,B)$	$\{0,1,5\}$	$\{0,0,4\}$	$\{0,1,4\}$	$\{1,2,5\}$	$\{2,3,6\}$	$\{3,4,5\}$	$\{4,4,5\}$
$e_i$	$e_8$	$e_9$	$e_{10}$	$e_{11}$	$e_{12}$	$e_{13}$	$e_{14}$
$r_{em}(e_i,B)$	$\{3,5,6\}$	$\{2,4,5\}$	$\{1,3,4\}$	$\{0,3,4\}$	$\{0,4,5\}$	$\{1,4,5\}$	$\{2,3,4\}$
$e_i$	$e_{15}$	$e_{16}$	$e_{17}$	$e_{18}$	$e_{19}$	$e_{20}$	$e_{21}$
$r_{em}(e_i,B)$	$\{2,3,3\}$	$\{1,2,4\}$	$\{1,2,3\}$	$\{1,2,2\}$	$\{0,1,3\}$	$\{3,3,4\}$	$\{4,4,4\}$

Table 33

The multiset representations of the vertices of $\mathsf{\Gamma }$ according to the set $A=\{v_2,v_4,v_9,v_{19}\}$.

$v_i$	$v_1$	$v_2$	$v_3$	$v_4$	$v_5$
$r_m(v_i,A)$	$\{1,3,3,6\}$	$\{0,2,4,6\}$	$\{1,1,5,5\}$	$\{0,2,4,5\}$	$\{1,3,3,4\}$
$v_i$	$v_6$	$v_7$	$v_8$	$v_9$	$v_{10}$
$r_m(v_i,A)$	$\{2,2,3,4\}$	$\{1,2,3,5\}$	$\{1,2,4,6\}$	$\{0,3,5,6\}$	$\{1,4,5,5\}$
$v_i$	$v_{11}$	$v_{12}$	$v_{13}$	$v_{14}$	$v_{15}$
$r_m(v_i,A)$	$\{2,4,4,5\}$	$\{3,4,5,5\}$	$\{3,4,5,6\}$	$\{2,4,5,6\}$	$\{1,3,4,5\}$
$v_i$	$v_{16}$	$v_{17}$	$v_{18}$	$v_{19}$
$r_m(v_i,A)$	$\{2,2,4,5\}$	$\{3,3,3,6\}$	$\{2,2,4,6\}$	$\{0,3,4,4\}$

References

1. Slater, P.J. Leaves of trees. Congr. Numer.; 1975; 14, pp. 549-559.

2. Harary, F.; Melter, R.A. On the metric dimension of a graph. Ars Comb.; 1976; 2, pp. 191-195.

3. Blumenthal, L.M. Theory and Applications of Distance Geometry; Oxford University Press: Oxford, UK, 1953.

4. Geneson, J. Metric dimension and pattern avoidance in graphs. Discret. Appl. Math.; 2020; 284, pp. 1-7. [DOI: https://dx.doi.org/10.1016/j.dam.2020.03.001]

5. Hussain, Z.; Munir, M.; Ahmad, A.; Chaudhary, M.; Khan, J.A.; Ahmed, I. Metric basis and metric dimension of 1-pentagonal carbon nanocone graphs. Sci. Rep.; 2020; 10, 19687. [DOI: https://dx.doi.org/10.1038/s41598-020-76516-1]

6. Sedlar, J.; skrekovski, R. Bounds on metric dimensions of graphs with edge disjoint cycles. Appl. Math. Comput.; 2021; 396, 125908. [DOI: https://dx.doi.org/10.1016/j.amc.2020.125908]

7. Nadjafi-Arani, M.J.; Mirzargar, M.; Emmert-Streib, F.; Dehmer, M. Partition and Colored Distances in Graphs Induced to Subsets of Vertices and Some of Its Applications. Symmetry; 2020; 12, 2027. [DOI: https://dx.doi.org/10.3390/sym12122027]

8. Alhevaz, A.; Baghipur, M.; Ganie, H.A.; Shang, Y. Bounds for the Generalized Distance Eigenvalues of a Graph. Symmetry; 2019; 11, 1529. [DOI: https://dx.doi.org/10.3390/sym11121529]

9. Wang, R.; Pryadko, L.P. Distance Bounds for Generalized Bicycle Codes. Symmetry; 2022; 14, 1348. [DOI: https://dx.doi.org/10.3390/sym14071348]

10. Nadeem, A.; Kashif, A.; Zafar, S.; Aljaedi, A.; Akanbi, O. Fault Tolerant Addressing Scheme for Oxide Interconnection Networks. Symmetry; 2022; 14, 1740. [DOI: https://dx.doi.org/10.3390/sym14081740]

11. Chartrand, G.; Salehi, E.; Zhang, P. The partition dimension of a graph. Aequationes Math.; 2000; 59, pp. 45-54. [DOI: https://dx.doi.org/10.1007/PL00000127]

12. Sebo, A.; Tannier, E. On metric generators of graphs. Math. Oper. Res.; 2004; 29, pp. 383-393. [DOI: https://dx.doi.org/10.1287/moor.1030.0070]

13. Estrada-Moreno, A.; Rodríguez-Velázquez, J.A.; Yero, I.G. The k-metric dimension of a graph. Appl. Math. Inf. Sci.; 2015; 9, pp. 2829-2840.

14. Karpovsky, M.G.; Chakrabarty, K.; Levitin, L.B. On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory; 1998; 44, pp. 599-611. [DOI: https://dx.doi.org/10.1109/18.661507]

15. Trujillo-Rasua, R.; Yero, I.G. k-metric antidimension: A privacy measure for social graphs. Inf. Sci.; 2016; 328, pp. 403-417. [DOI: https://dx.doi.org/10.1016/j.ins.2015.08.048]

16. Okamoto, F.; Phinezy, B.; Zhang, P. The local metric dimension of a graph. Math. Bohem.; 2010; 135, pp. 239-255. [DOI: https://dx.doi.org/10.21136/MB.2010.140702]

17. Kelenc, A.; Tratnik, N.; Yero, I.G. Uniquely identifying the edges of a graph: The edge metric dimension. Discret. Appl. Math.; 2018; 251, pp. 204-220. [DOI: https://dx.doi.org/10.1016/j.dam.2018.05.052]

18. Simanjuntak, R.; Siagian, P.; Vetrik, T. The multiset dimension of graphs. arXiv; 2017; arXiv: 1711.00225

19. Gil-Pons, R.; Ramírez-Cruz, Y.; Trujillo-Rasua, R.; Yero, I.G. Distance-based vertex identification in graphs: The outer multiset dimension. Appl. Math. Comput.; 2019; 363, 124612. [DOI: https://dx.doi.org/10.1016/j.amc.2019.124612]

20. Estrada-Moreno, A. On the k-partition dimension of graphs. Theor. Comput. Sci.; 2020; 806, pp. 42-52. [DOI: https://dx.doi.org/10.1016/j.tcs.2018.09.022]

21. Adawiyah, R.; Alfarisi, R.; Prihandini, R.M.; Agustin, I.H.; Venkatachalam, M. The local edge metric dimension of graph. J. Phys. Conf. Ser.; 2020; 1543, 012009. [DOI: https://dx.doi.org/10.1088/1742-6596/1543/1/012009]

22. Zhu, E.; Taranenko, A.; Shao, Z.; Xu, J. On graphs with the maximum edge metric dimension. Discret. Appl. Math.; 2019; 257, pp. 317-324. [DOI: https://dx.doi.org/10.1016/j.dam.2018.08.031]

23. Zhang, Y.; Gao, S. On the edge metric dimension of convex polytopes and its related graphs. J. Comb. Optim.; 2020; 39, pp. 334-350. [DOI: https://dx.doi.org/10.1007/s10878-019-00472-4]

24. Filipović, V.; Kartelj, A.; Kratica, J. Edge metric dimension of some generalized petersen graphs. Results Math.; 2019; 74, 182. [DOI: https://dx.doi.org/10.1007/s00025-019-1105-9]

25. Klavžar, S.; Tavakoli, M. Edge metric dimensions via hierarchical product and integer linear programming. Optim. Lett.; 2021; 15, pp. 1993-2003.

26. Peterin, I.; Yero, I.G. Edge metric dimension of some graph operations. Bull. Malays. Math. Sci. Soc.; 2020; 43, pp. 2465-2477. [DOI: https://dx.doi.org/10.1007/s40840-019-00816-7]

27. Ikhlaq, H.M.; Siddiqui, H.M.A.; Imran, M. A Comparative Study of Three Resolving Parameters of Graphs. Complexity; 2021; 2021, 1927181. [DOI: https://dx.doi.org/10.1155/2021/1927181]

28. Knor, M.; Majstorovic, S.; Toshi, A.T.M.; Skrekovski, R.; Yero, I.G. Graphs with the edge metric dimension smaller than the metric dimension. Appl. Math. Comput.; 2020; 401, 126076. [DOI: https://dx.doi.org/10.1016/j.amc.2021.126076]

29. Huang, Y.; Hou, B.; Liu, W.; Wu, L.; Rainwater, S.; Gao, S. On approximation algorithm for the edge metric dimension problem. Theor. Comput. Sci.; 2021; 853, pp. 2-6. [DOI: https://dx.doi.org/10.1016/j.tcs.2020.05.005]

30. Alfarisi, R.; Lin, Y.; Ryan, J.; Dafik, D.; Agustin, I.H. A note on multiset dimension and local multiset dimension of graphs. Stat. Optim. Inf. Comput.; 2020; 8, pp. 890-901. [DOI: https://dx.doi.org/10.19139/soic-2310-5070-727]

31. Alfarisi, R.; Susilowati, L.; Dafik, D.; Prabhu, S. Local Multiset Dimension of Amalgamation Graphs. F1000Research; 2023; 12, 95. [DOI: https://dx.doi.org/10.12688/f1000research.128866.1]

32. Khemmani, V.; Isariyapalakul, S. The multiresolving sets of graphs with prescribed multisimilar equivalence classes. Int. J. Math. Math. Sci.; 2018; 2018, 8978193. [DOI: https://dx.doi.org/10.1155/2018/8978193]

33. Hafidh, Y.; Kurniawan, R.; Saputro, S.; Simanjuntak, R.; Tanujaya, S.; Uttunggadewa, S. Multiset dimensions of trees. arXiv; 2019; arXiv: 1908.05879

34. Godsil, C.D.; McKay, B.D. A new graph product and its spectrum. Bull. Aust. Math. Soc.; 1978; 18, pp. 21-28. [DOI: https://dx.doi.org/10.1017/S0004972700007760]

35. Barrière, L.; Dalfó, C.; Fiol, M.A.; Mitjana, M. The generalized hierarchical product of graphs. Discret. Math.; 2009; 309, pp. 3871-3881. [DOI: https://dx.doi.org/10.1016/j.disc.2008.10.028]

36. Imran, S.; Siddiqui, M.K.; Imran, M.; Hussain, M. On metric dimensions of symmetric graphs obtained by rooted product. Mathematics; 2018; 6, 191. [DOI: https://dx.doi.org/10.3390/math6100191]

37. Klavžar, S.; Tavakoli, M. Local metric dimension of graphs: Generalized hierarchical products and some applications. Appl. Math. Comput.; 2020; 364, 124676. [DOI: https://dx.doi.org/10.1016/j.amc.2019.124676]