Open AccessArticle

A New Technique to Uniquely Identify the Edges of a Graph

Hafiz Muhammad Ikhlaq

Rashad Ismail

^2,3,*

Hafiz Muhammad Afzal Siddiqui

and

Muhammad Faisal Nadeem

^1,*

Department of Mathematics, COMSATS University Islamabad (CUI), Lahore Campus, Lahore 54000, Pakistan

Department of Mathematics, Faculty of Science and Arts, King Khalid University, Muhayl Assir 61913, Saudi Arabia

Department of Mathematics and Computer, Faculty of Science, Ibb University, Ibb 70270, Yemen

Authors to whom correspondence should be addressed.

Symmetry 2023, 15(3), 762; https://doi.org/10.3390/sym15030762

Submission received: 4 February 2023 / Revised: 3 March 2023 / Accepted: 8 March 2023 / Published: 20 March 2023

(This article belongs to the Special Issue Theoretical Computer Science and Discrete Mathematics II)

Download

Browse Figures

Versions Notes

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 (Γ)

. If the representation of two different edges is unequal, then B is an edge-multiset resolving a set of

Γ

. The least possible cardinality of the edge-multiset resolving a set is referred to as the edge-multiset dimension of

Γ

. 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.

Keywords:

resolving set; metric dimension; edge metric dimension; mixed metric dimension; line graph; paraline graph

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 {0},

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 (T_{n, m})

L (S (T_{n, m}))

and

L (L (T_{n, m}))

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

Γ

a connected and simple graph. The vertex set of

Γ

V (Γ)

and edge set of

Γ

E (Γ)

. The distance between any pair of vertices

α

and

β \in V (Γ)

is symbolized as

d_{Γ} (α, β)

(or

d (α, β)

for short), and is described as the number of edges of the least possible path between

α

and

β

. Assume

w \in V (Γ)

, resolves (recognizes or determines) the vertices

α

and

β

, if

d_{Γ} (w, α) \neq d_{Γ} (w, β)

. For an ordered subset of t vertices

S = {v_{1}, v_{2}, \dots, 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 (u | S) = (d_{Γ} (u, v_{1}), d_{Γ} (u, v_{2}), \dots, d_{Γ} (u, v_{t})) .

If any pair of vertices of

Γ

have dissimilar metric codes or representations according to set S, then S is known as a resolving set for

Γ

. The metric dimension of

Γ

is defined as the number of vertices in the smallest resolving set for

Γ

, denoted by

d i m (Γ)

. If S is a resolving set for

Γ

of cardinality

d i m (Γ)

, then S is called a metric basis for

Γ

The distance between an edge

f = α β

and a vertex

ρ

is denoted as

d_{Γ} (f, ρ)

(or

d (f, ρ)

for short), and is defined as

d_{Γ} (f, ρ) = m i n {d_{Γ} (α, ρ), d_{Γ} (β, ρ)}

. The vertex p resolves (recognizes or determines) the edges

f_{1}

and

f_{2}

, if

d_{Γ} (f_{1}, p) \neq d_{Γ} (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 (f | S) = (d_{Γ} (f, v_{1}), d_{Γ} (f, v_{2}), \dots, d_{Γ} (f, v_{t})) .

If any pair of edges of

Γ

have specific metric codes or representations according to S, then S is known as an edge-resolving set for

Γ

. The edge metric dimension of

Γ

is then defined as the number of vertices in the smallest edge resolving set for

Γ

, denoted by

{dim}_{e} (Γ)

. If S is an edge resolving set for

Γ

of cardinality

{dim}_{e} (Γ)

, then S is called an edge metric basis for

Γ

Multiset and Edge-Multiset Dimensions of Graphs

Let

A = {a_{1}, a_{2}, \dots, a_{l}}

be a subset of

V (Γ)

. For any vertex u of

Γ

, the multiset code or representation of

u \in V (Γ)

according to A is a multiset which is defined as

r_{m} (u | A) = {d_{Γ} (u, a_{1}), d_{Γ} (u, a_{2}), \dots, d_{Γ} (u, a_{l})} .

Note that the notion of multisets allows repetitions of elements in

r_{m} (u | A)

. If

r_{m} (u | A) \neq r_{m} (v | A)

for every pair of vertices u and

v \in V (Γ)

, then A is called a multiset resolving set of

Γ

. There could be graphs containing no multiset resolving sets. For instance, consider a graph with two vertices

u and v

, which are twins; that is, they share the same neighbours in

Γ

. In this sense, no matter which set of vertices D of

Γ

one could choose, it will always happen

r_{m} (u | D) = r_{m} (v | D)

. Hence, they will never be resolved by any set of vertices of

Γ

. In this sense, if a graph

Γ

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

Γ

. In such a case, the cardinality of any multiset basis of

Γ

is called the multiset dimension of

Γ

, and is denoted as

m d (Γ)

. On to the contrary, if

Γ

does not possess a multiset resolving set, we agreed that

m d (Γ) = \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 (G) = {v_{1}, v_{2}, \dots, v_{8}}

and

E (G) = {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 (G)

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

m d (G) = 3

Now, the multiset representation

r_{e m} (e | B)

of an edge

e = x y

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_{e m} (e | B) = {d_{Γ} (e, b_{1}), d_{Γ} (e, b_{2}), \dots, d_{Γ} (e, b_{j})} .

r_{e m} (e | B) \neq r_{e m} (f | B)

for any pair of dissimilar edges e and f, then B is called an edge-multiset resolving set for

Γ

. We again remark that there can be graphs containing no edge-multiset resolving sets. If

Γ

contains an edge-multiset resolving set, then the least possible edge-multiset resolving set is called an edge-multiset basis of

Γ

. The number of elements in an edge-multiset basis of

Γ

is known as the edge-multiset dimension, and is denoted as

m d_{e} (Γ)

. If

Γ

does not contain an edge-multiset resolving set, then we assume that

m d_{e} (Γ) = \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} (G) = 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

Γ

, defining the set of vertices and the set of edges, determining the set

A \subseteq E (Γ)

, determining the multiset representations of vertices or edges of graph

Γ

, and determining the least possible resolving set for

Γ

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

m d (Γ) \geq 3 .

Theorem 3

([18]). Let

n \geq

6. The multiset dimension of the cycle

C_{n}

3 .

Theorem 4

([18]). Let

m \geq

3 and

n \geq 2 .

The multiset dimension of the grid graph

P_{n} □ P_{m}

3 .

Theorem 5

([18]). If Γ is a non-path graph of diameter at most

2,

then

m d (Γ) = \infty

Consequently, from the above-known results, there is no graph

Γ

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

K P (ϑ, λ, μ)

is obtained from two cycles of length

ϑ \geq 3

and

λ \geq 3

by joining one vertex of one cycle with a vertex of degree one in a path of length

μ \geq 2

, and another vertex of the other cycle with the other vertex of degree one in the path of length

μ

. See Figure 3 for an example. We can write the vertex set of

K P (ϑ, λ, μ)

V (K P (ϑ, λ, μ)) = {α_{1}, α_{2}, \dots α_{ϑ}} \cup {β_{1}, β_{2}, \dots, β_{λ}} \cup {γ_{1}, \dots, γ_{μ - 1}}

and the edge set as

E (K P (ϑ, λ, μ)) = {α_{i} α_{i + 1} : 1 \leq i \leq ϑ} \cup {β_{j} β_{j + 1} : 1 \leq j \leq λ} \cup {γ_{k} γ_{k + 1} : 1 \leq k \leq μ - 2} \cup {α_{1} γ_{1}, γ_{μ - 1} β_{1}}

, where

α_{ϑ + 1} = α_{1}

and

β_{λ + 1} = β_{1}

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

Theorem 6.

K P (ϑ, λ, μ)

is a kayak paddle graph with

ϑ, λ, μ \geq 4

, then

m d (K P (ϑ, λ, μ)) = 3

Proof.

Therefore, by using Theorem 2, we have that

m d (K P (ϑ, λ, μ)) \geq 3

. Set

A = {α_{2}, β_{2}, γ_{1}}

is a multiset resolving set for the graph

K P (ϑ, λ, μ)

ϑ \geq 4

with

t = ⌊ \frac{ϑ}{2} ⌋ + 1

, then the vertices represented according to A are given in Table 3:

λ \geq 4

with

t^{'} = ⌊ \frac{λ}{2} ⌋ + 1

, then the vertices represented according to A are given in Table 4:

μ \geq 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

m d (K P (ϑ, λ, μ)) \leq 3

. Hence,

m d (K P (ϑ, λ, μ)) = 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}

V (T_{n, m}) = {v_{i}, u_{j} | 1 \leq i \leq n, 1 \leq j \leq m}

and the edge set is

E (T_{n, m}) = {v_{i} v_{i + 1} : 1 \leq i \leq n - 1} \cup {u_{j} u_{j + 1} 1 \leq j \leq 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 \geq 4

and

m \geq 3

. Then

m d (T_{n, m}) = 3

Proof.

Therefore, by Theorem 2,

m d (T_{n, m}) \geq 3

. We next show that the set

A = {v_{1}, v_{2}, u_{m}}

is a multiset resolving set for

T_{n, m}

n \geq 4

is even with

t = \frac{n}{2}

, then the vertices represented according to A are given in Table 6:

n \geq 4

is odd with

t = ⌊ \frac{n}{2} ⌋

, then the vertices represented according to A are given in Table 7:

m \geq 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

m d (T_{n, m}) \leq 3

. Hence,

m d (T_{n, m}) = 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

| V (G) |

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.

P_{n} ⊳_{\circ} P_{m}

is the comb product of

P_{n}

and

P_{m}

with

n, m \geq 4

, then

m d (P_{n} ⊳_{\circ} P_{m}) = 3

Proof.

Since

P_{n} ⊳_{\circ} P_{m}

is not a path, by Theorem 2,

m d (P_{n} ⊳_{\circ} P_{m}) \geq 3

. Assume

P_{n} ⊳_{\circ} P_{m}

has

V (P_{n} ⊳_{\circ} P_{m}) = {v_{i}^{j} : 1 \leq i \leq n, 0 \leq j \leq m - 1}

and

E (P_{n} ⊳_{\circ} P_{m}) = {v_{i}^{0} v_{i + 1}^{0} : 1 \leq i \leq n - 1} \cup {v_{i}^{j} v_{i}^{j + 1} : 1 \leq i \leq n; 0 \leq j \leq 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

m d (P_{n} ⊳_{\circ} P_{m}) \leq 3

. Hence,

m d (P_{n} ⊳_{\circ} P_{m}) = 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

Γ

is at least the edge metric dimension of graph

Γ

which we prove in Lemma 1.

Lemma 1.

Let Γ be a connected graph. Then

{dim}_{e} (Γ) \leq m d_{e} (Γ)

Proof.

Let B be an edge resolving set for graph

Γ

. If we have different edges f and g which have representation with respect to B as

r_{e} (f | B) = (a, b, c)

and

r_{e} (g | B) = (b, a, c)

. For the edge metric dimension, the

r_{e} (f | B) \neq r_{e} (g | 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_{e m} (f | B) = r_{e m} (g | 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} (f_{1} | B) = (a, b, c)

and

r_{e} (g_{1} | B) = (b, a, d)

, respectively, then this satisfies the properties of the edge metric dimension. Furthermore,

{a, b, c} \neq {b, a, d}

shows that

f_{1}

and

g_{1}

have distinct edge-multiset representation with respect to B, that is

r_{e m} (f_{1} | B) \neq r_{e m} (g_{1} | B)

. Thus, we concludes that

d i m_{e} (Γ) \leq m d_{e} (Γ)

. □

To give an example of Lemma 1, assume graph

Γ

with

V (Γ) = {a_{1}, a_{2}, \dots, a_{9}}

and

E (Γ) = {f_{1}, f_{2}, \dots, f_{9}}

as given in Figure 6. Let the set

B = {a_{3}, a_{6}, a_{8}}

be an edge resolving set for graph

Γ

and

{dim}_{e} (Γ) = 3

If two different edges

f_{2}

and

f_{9}

which have representation with respect to B as

r_{e} (f_{2} | B) = (1, 2, 3)

and

r_{e} (f_{9} | B) = (3, 2, 1)

, respectively. For the edge metric dimension,

r_{e} (f_{3} | B) \neq r_{e} (f_{9} | 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_{e m} (f_{2} | B) = r_{e m} (f_{9} | B) = {1, 2, 3}

. This does not satisfy the properties of the edge-multiset dimension. Thus, we conclude that

d i m_{e} (Γ) \leq m d_{e} (Γ)

Theorem 9.

Let Γ be a graph. Then

m d_{e} (Γ) = 1

, if, and only if,

Γ = P_{n}

Proof.

Let

V (P_{n}) = {w_{i} : 1 \leq i \leq n}

and

E (P_{n}) = {e_{1} = w_{i} w_{i + 1} : 1 \leq i \leq n - 1}

. In one direction, it is clear that the set

B = {w_{1}}

is an edge-multiset basis for

P_{n}

, that is,

m d_{e} (P_{n}) = 1

For the converse, assume that

Γ

is a connected graph with

m d_{e} (Γ) = 1

. Let

B = {w_{1}}

be an edge-multiset basis of a graph

Γ

. Hence,

r_{e m} (e | B) \neq r_{e m} (f | B)

for every pair of edges e and

f \in E (Γ)

. Since the representations of all edges of

Γ

, according to B, are distinct, there must exist an edge g such that

r_{e m} (g | B) = n - 2

, where

n - 1

is the size of the graph G. Thus, the diameter of

Γ

n - 1

, which implies that

Γ

is the path

P_{n}

. □

To give an example of Theorem 9, assume graph

Γ = P_{7}

with

V (P_{7}) = {a, b, c, d, e, f, g}

and

E (P_{7}) = {e_{1}, e_{2}, \dots, e_{6}}

as given in Figure 7.

It is noted, the set

B = {a}

B = {g}

is an edge-multiset resolving set for

Γ = P_{7}

. The set B gives unique edge-multisets representations of the edges of

Γ = P_{7}

In the Lemma 2, we show that no graph

Γ

has an edge-multiset dimension of 2.

Lemma 2.

Let Γ be a connected graph. Then

m d_{e} (Γ) \neq 2

Proof.

Γ

is a path, then

m d_{e} (Γ) = 1

. So, we may assume that

Γ \neq P_{n}

. Assume that

m d_{e} (Γ) = 2

for some graph

Γ

and let

B = {a, b}

be an edge resolving set for

Γ

. If there are two edges

e = a x

and

f = y b

(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_{e m} (e | B) = {0, d (e, b)} = {0, d (f, a)} = r_{e m} (e | B)

is a contradiction. Now, if there does not exist such a pair of edges, then a and b are adjacent. Since

Γ

is not a path,

Γ

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

Γ

has an edge-multiset dimension equal to 2. □

To give an example of Lemma 2, assume graph

Γ = L (T_{7, 3})

with

V (L (T_{7, 3})) = {a_{1}, a_{2}, \dots, a_{7}, b_{1}, b_{2}, b_{3}}

and

E (L (T_{7, 3})) = {f_{1}, f_{2}, \dots, f_{11}}

, as given in Figure 8. Let the set

B = {a_{2}, b_{3}}

be an edge-multiset resolving set for

L (T_{7, 3})

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_{e m} (f_{1} | B) = {0, d (a_{1}, b_{3})} = {0, 3} = {0, d (b_{2}, a_{2})} = r_{e m} (e | B)

is a contradiction.

As we know from Lemma 2, every connected graph different from the path has

m d_{e} (Γ) \geq 3

Theorem 10.

For any connected graph Γ other than a path,

m d_{e} (Γ) \geq 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

d i m e (Γ) = 1

, if, and only if,

Γ = 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

Γ

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

| V | \geq 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

Γ

. We represent the vertices in V by

v_{1}, v_{2}, \dots, v_{p}

, where

p \geq 2

and edges in E by

e_{1}, e_{2}, \dots, e_{n}

, where

n \geq p - 1

. For

i = 1, 2, \dots, n

, we have

r_{e m} (e_{i} | 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}}, \dots {0, 0, 2^{p - 2}}

. Without loss of generality, we assume that the edge having the representation

{0, 0, 1^{p - 2}}

e_{1} = v_{1} v_{x}

and the edge having the representation

{0, 0, 2^{p - 2}}

e_{n} = v_{p} v_{y}

. Since

r_{e m} (e_{1} | V) = {0, 0, 1^{p - 2}}

, it follows that

r_{e m} (e_{1} = v_{1} v_{x} | V \ {v_{1}, v_{x}}) = {1^{p - 2}}

which is in contradiction to

r_{e m} (e_{n} | V) = {0, 0, 2^{p - 2}}

. Hence, V is not an edge-multiset resolving set of

Γ

. □

To give an example of Lemma 3, assume graph

Γ

with

V (Γ) = {a_{1}, a_{2}, \dots, a_{5}}

and

E (Γ) = {f_{1}, f_{2}, \dots, 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} (Γ) \geq 3

. We note that the set

B = {a, b, c}

is not an edge-multiset resolving set for

Γ

r_{e m} (e_{1} | B) = r_{e m} (e_{2} | B) = {0, 0, 1}

. If the set

B_{1} = {a, b, c, d}

is an edge-multiset resolving set for

Γ

, then

r_{e m} (e_{1} | B_{1}) = r_{e m} (e_{3} | B_{1}) = {0, 0, 1, 2}

, which means that the set

B_{1}

is not an edge-multiset resolving set for

Γ

. If the set

B_{2} = {a, b, c, d, e}

is an edge-multiset resolving set for

Γ

, then

r_{e m} (e_{1} | B_{2}) = r_{e m} (e_{3} | B_{2}) = r_{e m} (e_{4} | B_{2}) = {0, 0, 1, 1, 2}

, and

r_{e m} (e_{2} | B_{2}) = r_{e m} (e_{5} | B_{2}) = {0, 0, 1, 1, 1}

, which means that the set

B_{2}

is not an edge-multiset resolving set for

Γ

. It is clear that an edge-multiset resolving set for

Γ

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} (Γ) = \infty

Proof.

Assume that

v_{1}, v_{2}

and

v_{3}

are three pendant vertices adjacent to vertex

v_{x}

Γ

. 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

Γ

, then either at least two of the pendant vertices

v_{i} or v_{j}

where

i, j = 1, 2, 3

and

i \neq 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 \neq j

, cannot be resolved because

r_{e m} (e_{i}, v) = r_{e m} (e_{j}, v)

where

v \in V (Γ)

. Hence,

Γ

contains a vertex adjacent to at least three pendant vertices. Thus,

m d_{e} (Γ) = \infty

. □

To give an example of Theorem 11, assume graph

Γ

with

V (Γ) = {a, b, c, d, e, f, g}

and

E (Γ) = {e_{1}, e_{2}, \dots, 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

Γ

r_{e m} (e_{1} | B) = r_{e m} (e_{5} | B) = r_{e m} (e_{6} | B) = {0, 1, 2, 3}

. If the set

B_{1} = {a, b, c, d, e}

is an edge-multiset resolving set for

Γ

, then

r_{e m} (e_{5} | B_{1}) = r_{e m} (e_{6} | B_{1}) = {0, 1, 1, 2, 3}

, which means that the set

B_{1}

is not an edge-multiset resolving set for

Γ

. If the set

B_{2} = {a, b, c, d, e, f}

is an edge-multiset resolving set for

Γ

, then

r_{e m} (e_{1} | B_{2}) = r_{e m} (e_{6} | B_{2}) = {0, 0, 1, 1, 2, 3}

, which means that the set

B_{2}

is not an edge-multiset resolving set for

Γ

. If the set

B_{3} = {a, b, c, d, e, f, g}

is an edge-multiset resolving set for

Γ

, then

r_{e m} (e_{1} | B_{3}) = r_{e m} (e_{5} | B_{3}) = r_{e m} (e_{6} | B_{3}) = {0, 0, 1, 1, 1, 2, 3}

, which means that the set

B_{2}

is not an edge-multiset resolving set for

Γ

. It is clear that the edge-multiset resolving set for

Γ

does not exist. Hence,

Γ

contains a vertex adjacent to three pendant vertices, then

m d_{e} (Γ) = \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

Γ

is a connected graph for which

m d_{e} (Γ)

is decided, then each and every edge-multiset resolving set for

Γ

is an edge resolving set for

Γ

, and so

1 \leq d i m_{e} (Γ) \leq m d_{e} (Γ)

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 \geq 7

. Then

m d_{e} (C_{n}) = 3

Proof.

Therefore, by Theorem 10,

m d_{e} (C_{n}) \geq 3

. Assume

C_{n} = v_{0} v_{1} \dots 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}

n = 2 t

with

t > 3

, then the edge representations according to B are represented in Table 10 and Table 11.

n = 2 t + 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} (C_{n}) \leq 3

. Hence,

m d_{e} (C_{n}) = 3

. □

In Theorem 13 we show that kayak paddle graph with

ϑ, λ, μ \geq 4

has a constant edge-multiset dimension.

Theorem 13.

K P (ϑ, λ, μ)

is a kayak paddle graph with

ϑ, λ, μ \geq 4

, then

m d_{e} (K P (ϑ, λ, μ)) = 3

Proof.

By Theorem 10,

m d_{e} (K P (ϑ, λ, μ)) \geq 3

. Let

V (K P (ϑ, λ, μ)) = {α_{1}, α_{2}, \dots α_{ϑ}} \cup {β_{1}, β_{2}, \dots, β_{λ}} \cup {γ_{1}, \dots, γ_{μ - 1}}

and

E (K P (ϑ, λ, μ)) = {α_{i} α_{i + 1} : 1 \leq i \leq ϑ} \cup {β_{j} β_{j + 1} : 1 \leq j \leq λ} \cup {γ_{k} γ_{k + 1} : 1 \leq k \leq μ - 2} \cup {α_{1} γ_{1}, γ_{μ - 1} β_{1}}

, where

α_{ϑ + 1} = α_{1}

and

β_{λ + 1} = β_{1}

. All edges are labelled as follows.

e_{i} = α_{i} α_{i + 1} : 1 \leq i \leq ϑ e_{j}^{'} = β_{j} β_{j + 1} : 1 \leq j \leq λ

e_{k}^{''} = γ_{k} γ_{k - 1} : 2 \leq k \leq μ - 1 e_{1}^{''} = α_{1} γ_{1}, e_{μ}^{''} = γ_{μ - 1} β_{1}

We show that the set

B = {α_{2}, β_{2}, γ_{1}}

is an edge-multiset resolving set of

K P (ϑ, λ, μ)

ϑ \geq 4

with

t = ⌊ \frac{ϑ}{2} ⌋

, then the edge representations according to B are represented as follows in Table 14.

λ \geq 4

with

t^{'} = ⌊ \frac{λ}{2} ⌋

, then the edge representations according to B are represented in Table 15.

μ \geq 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} (K P (ϑ, λ, μ)) \leq 3

. Hence,

m d_{e} (K P (ϑ, λ, μ)) = 3

. □

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

Theorem 14.

T_{n, m}

is a dragon graph with

n \geq 4

and

m \geq 3

, then

m d_{e} (T_{n, m}) = 3

Proof.

By Theorem 10,

m d_{e} (T_{n, m}) \geq 3

. Let

V (T_{n, m}) = {v_{i}, u_{j} | 1 \leq i \leq n, 1 \leq j \leq m}

and

E (T_{n, m}) = {v_{i} v_{i + 1} : 1 \leq i \leq n} \cup {u_{j} u_{j + 1} 1 \leq j \leq m - 1} \cup {v_{n} u_{1}}

, where

v_{n + 1} = v_{1}

. The edges of

T_{n, m}

are labelled as follows.

f_{i} = {v_{i} v_{i + 1} : 1 \leq i \leq n}

f_{j + 1}^{'} = {u_{j} u_{j + 1} : 1 \leq j \leq m - 1}, f_{1}^{'} = 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}

n \geq 4

is even with

t = \frac{n}{2}

, then the edge representations according to B are represented in Table 17.

n \geq 4

is odd with

t = ⌈ \frac{n}{2} ⌉

, then the edge representations according to B are represented in Table 18.

m \geq 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} (T_{n, m}) \leq 3

. Hence,

m d_{e} (T_{n, m}) = 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.

P_{n} ⊳_{\circ} P_{m}

is the comb product of two paths

P_{n}

and

P_{m}

, with

n, m \geq 4

, then

m d_{e} (P_{n} ⊳_{\circ} P_{m}) = 3

Proof.

By Theorem 10,

m d_{e} (P_{n} ⊳_{\circ} P_{m}) \geq 3

. Let

V (P_{n} ⊳_{\circ} P_{m}) = {v_{i}^{j} : 1 \leq i \leq n, 0 \leq j \leq m - 1}

and the edges are labelled as follows.

e_{i}^{j} = \{\begin{matrix} v_{i}^{j - 1} v_{i}^{j}, & j \neq 0; \\ v_{i}^{0} a_{i + 1}^{0} & j = 0 . \end{matrix} 1 \leq i \leq n; 0 \leq j \leq 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} (P_{n} ⊳_{\circ} P_{m}) \leq 3

. Hence,

m d_{e} (P_{n} ⊳_{\circ} P_{m}) = 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

d e g (a_{i}) \leq 3

where

2 \leq i \leq n - 1

. Let

D = {i | 2 \leq i \leq 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}

V (C T_{n}) = {a_{i} | 1 \leq i \leq n} \cup {b_{i} | i \in D}

and the edge set of a caterpillar graph

C T_{n}

E (C T_{n}) = {a_{i} a_{i + 1} | 1 \leq i \leq n - 1} \cup {a_{i} b_{i} | 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

d e g (x_{i}) \leq 2

. See Figure 11 for an example.

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

Theorem 16.

C T_{n}

is a caterpillar graph with

n \geq 5

, then

m d_{e} (C T_{n}) = 3

Proof.

Therefore, by Theorem 10,

m d_{e} (C T_{n}) \geq 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.

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} (C T_{n}) \leq 3

. Hence,

m d_{e} (C T_{n}) = 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

d e g (x_{i}) \leq 3

where

3 \leq i \leq n - 2

. Let

D = {i | 3 \leq i \leq 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}

V (L_{n}) = {x_{i} | 1 \leq i \leq n} \cup {y_{i} | i \in D} \cup {z_{i} | i \in D}

and the edge set of lobster graph

L_{n}

E (L_{n}) = {x_{i} x_{i + 1} | 1 \leq i \leq n - 1} \cup {x_{i} y_{i} | i \in D} \cup {y_{i} z_{i} | 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

d e g (x_{i}) \leq 2

. See Figure 12 for an example.

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

Theorem 17.

L_{n}

is a lobster graph with

n \geq 5

, then

m d_{e} (L_{n}) = 3

Proof.

Therefore, by Theorem 10,

m d_{e} (L_{n}) \geq 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.

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.

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} (L_{n}) \leq 3

. Hence,

m d_{e} (L_{n}) = 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} (T_{n}) \neq \infty

, then

m d_{e} (T_{n}) \leq n - 2

Proof.

Therefore, if

d i a m (T_{n}) = 3

there exist two vertices a and b of

T_{n}

, such that

2 \leq d e g (a),

d e g (b) \leq 3

. We shall thus obtain the following three cases. See Figure 13 for visualization.

If $d e g (a) = d e g (b) = 2$ , then $T_{n} \equiv P_{4}$ and $m d_{e} (T_{n}) = 1 = n - 3$ ;
If $d e g (a) = 2$ and $d e g (b) = 3$ . Let $N (a) = {a_{1}, b}$ and $N (b) = {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} (T_{n}) = 3 = n - 2$ ;
If $d e g (a) = d e g (b) = 3$ . Let $N (a) = {a_{1}, a_{2}, b}$ and $N (b) = {a, b_{1}, b_{2}}$ . Then we do not have an edge-multiset resolving set for $T_{n}$ , which means $m d_{e} (T_{n}) = \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} (T_{n}) \neq \infty

, then

3 \leq m d_{e} (T_{n}) \leq n - 2

Proof.

As we know, if graph

Γ

is not a path graph then the edge-multiset dimension of any graph

Γ

m d_{e} (Γ) \geq 3

by Theorem 10.

T_{n}

is a tree graph but not a path graph so,

m d_{e} (T_{n}) \geq 3

which is the lower bound for

T_{n}

. It is clear that the edge-multiset dimension of

T_{n}

m d_{e} (T_{n}) \leq n - 2

by Lemma 4, so, we obtain

3 \leq m d_{e} (T_{n}) \leq n - 2

. □

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

Theorem 19.

C T_{n}

is a caterpillar graph with

n \geq 5

d e g (x_{i}) \leq 4

where

3 \leq i \leq n - 2

and

D = {i | 3 \leq i \leq n - 2}

, then

m d_{e} (L_{n}) = 3 + | D |

Proof.

Let

C T_{n}

be a caterpillar graph with a spine

P_{n} = (x_{1}, x_{2}, \dots, x_{n})

. Here,

d e g (x_{i}) \leq 4

with

3 \leq i \leq n - 2

. Let

D = {i | 3 \leq i \leq 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}

V (C T_{n}) = {x_{i} | 1 \leq i \leq n} \cup {y_{i}^{1}, y_{i}^{2} | i \in D}

and the edge set of caterpillar graph

C T_{n}

E (C T_{n}) = {x_{i} x_{i + 1} | 1 \leq i \leq 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

d e g (x_{i}) \leq 2

. See Figure 14 for an example.

Let the set

B = {x_{1}, x_{2}, x_{n}, y_{i}^{1} | 3 \leq i \leq n - 2}

by an edge-multiset resolving set for the graph

C T_{n}

. Suppose a vertex

y_{i}^{1}

with

3 \leq i \leq 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 \leq i \leq 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 \leq i \leq ⌈ \frac{n}{2} ⌉ - 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} (C T_{n}) \geq 3 + | D |

W = {x_{1}, x_{2}, x_{n}}

is a subset of

V (C T_{n})

, then the edge representations are presented in Table 28:

It is observed that the multiset distance of edges according to W is

r_{e m} (x_{i} y_{i}^{1} | W) = r_{e m} (x_{i} y_{i}^{2} | W)

so, the vertices

y_{i}^{1}

y_{i}^{2}

, where

i \in D

3 \leq i \leq n - 2

, are included in the set W. Therefore,

m d_{e} (C T_{n}) \leq 3 + | D |

. Hence,

m d_{e} (C T_{n}) = 3 + | D |

. □

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

Theorem 20.

L_{n}

is a lobster graph with

n > 5

d e g (x_{i}) = 4

, where

i \in D = {i | 3 \leq i \leq n - 2}

, then

m d_{e} (L_{n}) = 3 + | D |

Proof.

Let

L_{n}

be a lobster graph with a spine

P_{n} = (x_{1}, x_{2}, \dots, x_{n})

. Here,

d e g (x_{i}) \leq 4

and

3 \leq i \leq n - 2

. Let

D = {i | 3 \leq i \leq n - 2}

. For all

x_{i}

with

3 \leq i \leq 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}

V (L_{n}) = {x_{i} | 1 \leq i \leq 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}

E (L_{n}) = {x_{i} x_{i + 1} | 1 \leq i \leq 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 \leq i \leq n - 3}

is an edge-multiset resolving set for the graph

L_{n}

. Suppose that a vertex

z_{i}^{1}

with

3 \leq i \leq 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 \leq i \leq 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} (L_{n}) \geq 3 + | D |

W = {x_{1}, x_{2}, x_{n}}

is a subset of

V (L_{n})

, then the edge representations are presented in Table 29:

It is clear that the multiset distance of edges according to W are

r_{e m} (x_{i} y_{i}^{1} | W) = r_{e m} (x_{i} y_{i}^{2} | W)

and

r_{e m} (y_{i}^{1} z_{i}^{1} | W) = r_{e m} (y_{i}^{2} z_{i}^{2} | W)

. So, the vertices

z_{i}^{1}

z_{i}^{2}

, where

i \in D

3 \leq i \leq n - 3

and the vertex

y_{n - 2}^{1}

, are included in the set W. Therefore,

m d_{e} (L_{n}) \leq 3 + | D |

. Hence,

m d_{e} (L_{n}) = 3 + | D |

. □

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} (T) = 2^{h} - 1

Proof.

Let T be a complete r-ary tree of height

h \geq 1

. If

r \geq 3

, by Theorem 11 , then

m d_{e} (T) = \infty

. If

r = 1

, then T is a path and

m d_{e} (T) = 1

Let

r = 2

. If

h = 1

, then T is a path with two edges and

m d_{e} (T) = 1

. Consider the binary trees of height

h \geq 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} (T) \geq 2^{h} - 1

For every level l of T, where

1 \leq l \leq 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

| B | = \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 \leq p < q \leq 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 \leq p \leq 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

2 n

, 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}) \neq 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 {v_{1}}

. Hence, the set B is an edge-multiset resolving set and

m d_{e} (T) \leq 2^{h} - 1

. Hence,

m d_{e} (T) = 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

Γ

for which

dim (Γ) = {dim}_{e} (Γ)

dim (Γ) > {dim}_{e} (Γ)

dim (Γ) < {dim}_{e} (Γ)

. In [28], a lot of families of graphs were described for which the edge dimension was greater than the vertex dimension

dim (Γ) > {dim}_{e} (Γ)

, 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

m d (Γ) = m d_{e} (Γ)

can be realized for some graphs

Γ

(another example could be paths and cycles). We next show that

m d (Γ) < m d_{e} (Γ)

and

m d (Γ) > m d_{e} (Γ)

can also occur.

5.1. Graphs G with $m d (Γ) < m d_{e} (Γ)$

To achieve our goal in this section, we consider

Γ

be the graph with vertex set

V (Γ) = {u_{1}, u_{2}, \dots, u_{17}}

and edge set

E (Γ) = {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

Γ

. Since, the graph

Γ

is not a path graph, by Theorem 1,

m d (Γ) \geq 3

Table 30 shows the multiset representations of all vertices of

Γ

according to

A = {u_{3}, u 16, u_{17}}

. Since no two vertices have the same multiset code or representation according to A, we deduce that

m d (Γ) \leq 3

. So, by using Theorem 1 we have

m d (Γ) = 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

Γ

. Since, the graph

Γ

is not a path graph, by Theorem 10,

m d_{e} (Γ) \geq 3

Table 31 shows the edge-multiset representations of all edges of

Γ

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} (Γ) \leq 4

. We must show that

m d_{e} (Γ) \geq 4

On the contrary, suppose that

m d_{e} (Γ) = 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_{e m} (e_{1} | B_{1}) = r_{e m} (e_{16} | 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_{e m} (e_{10} | B_{2}) = r_{e m} (e_{18} | 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_{e m} (e_{12} | B_{3}) = r_{e m} (e_{13} | 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_{e m} (e_{e_{i}} | B_{4}) = r_{e m} (e_{13 - i} | B_{4})$ for $1 \leq i \leq 6$ , $r_{e m} (e_{13} | B_{4}) = r_{e m} (e_{18} | B_{4}) = {1, 3, 5}$ and $r_{e m} (e_{14} | B_{4}) = r_{e m} (e_{17} | B_{4}) = {2, 2, 6}$ which is in contradiction to our supposition.

Now, it is clear that

m d_{e} (Γ) \geq 4

. Hence,

m d_{e} (Γ) = 4

Remark 1.

The graph Γ given in Figure 17 satisfies the inequality

m d (Γ) < m d_{e} (Γ)

5.2. Graphs G with $m d (Γ) > m d_{e} (Γ)$

Let

Γ

be the graph with vertex set

V (Γ) = {v_{1}, v_{2}, \dots, v_{19}}

and edge set

E (Γ) = {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

Γ

. Since, the graph

Γ

is not a path graph, by Theorem 10,

m d_{e} (Γ) \geq 3

Table 32 shows the edge-multiset representations of all the edges of

Γ

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} (Γ) \leq 3

. So, by using Theorem 10 we have

m d_{e} (Γ) = 3

Now, we note that, for instance, the set

A = {v_{2}, v_{4}, v_{9}, v_{19}}

is a multiset resolving set for

Γ

. Since the graph

Γ

is not a path graph, by Theorem 1,

m d (Γ) \geq 3

Table 33 shows the multiset representations of all vertices of

Γ

according to A. Since no two vertices have the same multiset code or representation according to A, we deduce that

m d (Γ) \leq 4

. We must show that

m d (Γ) \geq 4

. On the contrary, suppose that

m d (Γ) = 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} (v_{13} | A_{1}) = r_{m} (v_{14} | 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} (v_{1} | A_{2}) = r_{m} (v_{5} | A_{2}) = {1, 3, 3}$ , $r_{m} (v_{2} | A_{2}) = r_{m} (v_{4} | A_{2}) = {0, 2, 4}$ , $r_{m} (v_{6} | B_{2}) = r_{m} (v_{16} | B_{2}) = {2, 2, 4}$ , $r_{m} (v_{7} | A_{2}) = r_{m} (v_{15} | A_{2}) = {1, 3, 5}$ , $r_{m} (v_{8} | A_{2}) = r_{m} (v_{14} | A_{2}) = {2, 4, 6}$ , $r_{m} (v_{9} | A_{2}) = r_{m} (v_{13} | A_{2}) = {3, 5, 6}$ and $r_{m} (v_{11} | A_{2}) = r_{m} (v_{12} | 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} (v_{4} | A_{3}) = r_{m} (v_{11} | A_{3}) = r_{m} (v_{14} | 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} (v_{1} | A_{4}) = r_{m} (v_{17} | A_{4}) = {3, 3, 6}$ , $r_{m} (v_{2} | A_{4}) = r_{m} (v_{18} | A_{4}) = {2, 4, 6}$ and $r_{m} (v_{11} | A_{4}) = r_{m} (v_{16} | A_{4}) = {2, 4, 5}$ , which is a contradiction to our supposition.

It is clear that

m d (Γ) \geq 4

. Hence,

m d (Γ) = 4

Remark 2.

The graph Γ given in Figure 18 satisfies the inequality

m d (Γ) > m d_{e} (Γ)

6. Conclusions

In this work, we defined the notion of the edge-multiset dimension of graphs. We have noted that the multiset dimension

m d (Γ)

and edge-multiset dimension

m d_{e} (Γ)

of graphs are generally not comparable. We have given examples of graphs

Γ

, where

m d (Γ) > m d_{e} (Γ)

m d (Γ) < m d_{e} (Γ)

, or

m d (Γ) = m d_{e} (Γ)

. 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

m d (Γ) > m d_{e} (Γ)

. 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

m d (Γ)

and

m d_{e} (Γ)

are finite. Can all graphs Γ for which

m d (Γ) > m d_{e} (Γ)

m d (Γ) < m d_{e} (Γ)

, or

m d (Γ) = m d_{e} (Γ)

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} (Γ)

is finite, can any upper and/or lower bounds with respect to n be found for

m d_{e} (Γ)

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.

Funding

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).

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.

References

Slater, P.J. Leaves of trees. Congr. Numer. 1975, 14, 549–559. [Google Scholar]
Harary, F.; Melter, R.A. On the metric dimension of a graph. Ars Comb. 1976, 2, 191–195. [Google Scholar]
Blumenthal, L.M. Theory and Applications of Distance Geometry; Oxford University Press: Oxford, UK, 1953. [Google Scholar]
Geneson, J. Metric dimension and pattern avoidance in graphs. Discret. Appl. Math. 2020, 284, 1–7. [Google Scholar] [CrossRef] [Green Version]
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. [Google Scholar] [CrossRef]
Sedlar, J.; skrekovski, R. Bounds on metric dimensions of graphs with edge disjoint cycles. Appl. Math. Comput. 2021, 396, 125908. [Google Scholar] [CrossRef]
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. [Google Scholar] [CrossRef]
Alhevaz, A.; Baghipur, M.; Ganie, H.A.; Shang, Y. Bounds for the Generalized Distance Eigenvalues of a Graph. Symmetry 2019, 11, 1529. [Google Scholar] [CrossRef] [Green Version]
Wang, R.; Pryadko, L.P. Distance Bounds for Generalized Bicycle Codes. Symmetry 2022, 14, 1348. [Google Scholar] [CrossRef]
Nadeem, A.; Kashif, A.; Zafar, S.; Aljaedi, A.; Akanbi, O. Fault Tolerant Addressing Scheme for Oxide Interconnection Networks. Symmetry 2022, 14, 1740. [Google Scholar] [CrossRef]
Chartrand, G.; Salehi, E.; Zhang, P. The partition dimension of a graph. Aequationes Math. 2000, 59, 45–54. [Google Scholar] [CrossRef]
Sebo, A.; Tannier, E. On metric generators of graphs. Math. Oper. Res. 2004, 29, 383–393. [Google Scholar] [CrossRef]
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, 2829–2840. [Google Scholar]
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, 599–611. [Google Scholar] [CrossRef] [Green Version]
Trujillo-Rasua, R.; Yero, I.G. k-metric antidimension: A privacy measure for social graphs. Inf. Sci. 2016, 328, 403–417. [Google Scholar] [CrossRef] [Green Version]
Okamoto, F.; Phinezy, B.; Zhang, P. The local metric dimension of a graph. Math. Bohem. 2010, 135, 239–255. [Google Scholar] [CrossRef]
Kelenc, A.; Tratnik, N.; Yero, I.G. Uniquely identifying the edges of a graph: The edge metric dimension. Discret. Appl. Math. 2018, 251, 204–220. [Google Scholar] [CrossRef] [Green Version]
Simanjuntak, R.; Siagian, P.; Vetrik, T. The multiset dimension of graphs. arXiv 2017, arXiv:1711.00225. [Google Scholar]
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. [Google Scholar] [CrossRef]
Estrada-Moreno, A. On the k-partition dimension of graphs. Theor. Comput. Sci. 2020, 806, 42–52. [Google Scholar] [CrossRef] [Green Version]
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. [Google Scholar] [CrossRef]
Zhu, E.; Taranenko, A.; Shao, Z.; Xu, J. On graphs with the maximum edge metric dimension. Discret. Appl. Math. 2019, 257, 317–324. [Google Scholar] [CrossRef]
Zhang, Y.; Gao, S. On the edge metric dimension of convex polytopes and its related graphs. J. Comb. Optim. 2020, 39, 334–350. [Google Scholar] [CrossRef]
Filipović, V.; Kartelj, A.; Kratica, J. Edge metric dimension of some generalized petersen graphs. Results Math. 2019, 74, 182. [Google Scholar] [CrossRef] [Green Version]
Klavžar, S.; Tavakoli, M. Edge metric dimensions via hierarchical product and integer linear programming. Optim. Lett. 2021, 15, 1993–2003. [Google Scholar]
Peterin, I.; Yero, I.G. Edge metric dimension of some graph operations. Bull. Malays. Math. Sci. Soc. 2020, 43, 2465–2477. [Google Scholar] [CrossRef] [Green Version]
Ikhlaq, H.M.; Siddiqui, H.M.A.; Imran, M. A Comparative Study of Three Resolving Parameters of Graphs. Complexity 2021, 2021, 1927181. [Google Scholar] [CrossRef]
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. [Google Scholar] [CrossRef]
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, 2–6. [Google Scholar] [CrossRef]
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, 890–901. [Google Scholar] [CrossRef]
Alfarisi, R.; Susilowati, L.; Dafik, D.; Prabhu, S. Local Multiset Dimension of Amalgamation Graphs. F1000Research 2023, 12, 95. [Google Scholar] [CrossRef]
Khemmani, V.; Isariyapalakul, S. The multiresolving sets of graphs with prescribed multisimilar equivalence classes. Int. J. Math. Math. Sci. 2018, 2018, 8978193. [Google Scholar] [CrossRef]
Hafidh, Y.; Kurniawan, R.; Saputro, S.; Simanjuntak, R.; Tanujaya, S.; Uttunggadewa, S. Multiset dimensions of trees. arXiv 2019, arXiv:1908.05879. [Google Scholar]
Godsil, C.D.; McKay, B.D. A new graph product and its spectrum. Bull. Aust. Math. Soc. 1978, 18, 21–28. [Google Scholar] [CrossRef] [Green Version]
Barrière, L.; Dalfó, C.; Fiol, M.A.; Mitjana, M. The generalized hierarchical product of graphs. Discret. Math. 2009, 309, 3871–3881. [Google Scholar] [CrossRef] [Green Version]
Imran, S.; Siddiqui, M.K.; Imran, M.; Hussain, M. On metric dimensions of symmetric graphs obtained by rooted product. Mathematics 2018, 6, 191. [Google Scholar] [CrossRef] [Green Version]
Klavžar, S.; Tavakoli, M. Local metric dimension of graphs: Generalized hierarchical products and some applications. Appl. Math. Comput. 2020, 364, 124676. [Google Scholar] [CrossRef]

Figure 1. A graph with the

m d (G) = 3

Figure 1. A graph with the

m d (G) = 3

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

Figure 3. The kayak paddle graph

K P (12, 8, 5)

Figure 3. The kayak paddle graph

K P (12, 8, 5)

Figure 4. The dragon graph

T_{8, 5}

Figure 4. The dragon graph

T_{8, 5}

Figure 5. The comb product of

P_{5}

and

P_{4}

P_{5} ⊳_{\circ} P_{4}

Figure 5. The comb product of

P_{5}

and

P_{4}

P_{5} ⊳_{\circ} P_{4}

Figure 6. The graph

Γ

Figure 6. The graph

Γ

Figure 7. The graph

Γ

Figure 7. The graph

Γ

Figure 8. The graph

L (T_{7, 3})

Figure 8. The graph

L (T_{7, 3})

Figure 9. The graph

Γ

Figure 9. The graph

Γ

Figure 10. The graph

Γ

Figure 10. The graph

Γ

Figure 11. Caterpillar graph

C T_{7}

with

D = {2, 4, 6}

Figure 11. Caterpillar graph

C T_{7}

with

D = {2, 4, 6}

Figure 12. Lobster graph

L_{7}

with

D = {3, 4, 5}

Figure 12. Lobster graph

L_{7}

with

D = {3, 4, 5}

Figure 13. Three cases of graph

T_{n}

with diameter 3.

Figure 13. Three cases of graph

T_{n}

with diameter 3.

Figure 14. Caterpillar graph

C T_{6}

with

D = {3, 4}

Figure 14. Caterpillar graph

C T_{6}

with

D = {3, 4}

Figure 15. Lobster graph

L_{6}

with

D = {3, 4}

Figure 15. Lobster graph

L_{6}

with

D = {3, 4}

Figure 16. Complete 2-ary tree graph with

h = 4

Figure 16. Complete 2-ary tree graph with

h = 4

Figure 17. The graph

Γ

Figure 17. The graph

Γ

Figure 18. The graph

Γ

Figure 18. The graph

Γ

Table 1. The multiset representations of the vertices of G with respect to the set

A = {v_{2}, v_{3}, v_{7}}

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}}

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_{e m} (., B)$	${0, 1, 1}$	${0, 0, 2}$	${1, 0, 3}$	${2, 1, 3}$
Edges	e	f	g	h
$r_{e m} (., B)$	${2, 2, 2}$	${1, 2, 1}$	${1, 2, 0}$	${2, 1, 4}$

Table 3. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

ϑ \geq 4

with

t = ⌊ \frac{ϑ}{2} ⌋ + 1

according to the set

A = {α_{2}, β_{2}, γ_{1}}

Table 3. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

ϑ \geq 4

with

t = ⌊ \frac{ϑ}{2} ⌋ + 1

according to the set

A = {α_{2}, β_{2}, γ_{1}}

$r_{m} (., .)$	$A = {α_{2}, β_{2}, γ_{1}}$
$α_{1}$	${1, 1, μ + 1}$
$α_{i} : 2 \leq i \leq t$	${i - 2, i, μ + i}$
$α_{i} : i = t + 1$	${i - 2, ϑ - i + 2, ϑ + μ - i + 2}$
$α_{i} : t + 2 \leq i \leq ϑ$	${ϑ - i + 2, ϑ - i + 2, ϑ + μ - i + 2}$

Table 4. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

λ \geq 4

with

t^{'} = ⌊ \frac{λ}{2} ⌋ + 1

according to the set

A = {α_{2}, β_{2}, γ_{1}}

Table 4. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

λ \geq 4

with

t^{'} = ⌊ \frac{λ}{2} ⌋ + 1

according to the set

A = {α_{2}, β_{2}, γ_{1}}

$r_{m} (., .)$	$A = {α_{2}, β_{2}, γ_{1}}$
$β_{1}$	${1, μ - 1, μ + 1}$
$β_{j} : 2 \leq j \leq t^{'}$	${j - 2, μ + j - 2, μ + j}$
$β_{j} : j = t^{'} + 1$	${j - 2, λ + μ - j + 2, λ + μ - j}$
$β_{j} : t^{'} + 2 \leq j \leq λ$	${λ - j + 2, λ + μ - j + 2, λ + μ - j}$

Table 5. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

μ \geq 4

, according to the set

A = {α_{2}, β_{2}, γ_{1}}

Table 5. The multiset representations of the vertices of

K P (ϑ, λ, μ)

, for

μ \geq 4

, according to the set

A = {α_{2}, β_{2}, γ_{1}}

$r_{m} (., .)$	$γ_{k} : 1 \leq k \leq μ - 1$
$A = {α_{2}, β_{2}, γ_{1}}$	${k + 1, k - 1, μ - k + 1}$

Table 6. The multiset representations of the vertices of

T_{n, m}

, for

n \geq 4

, even and

t = \frac{n}{2}

according to the set

A = {v_{1}, v_{2}, u_{m}}

Table 6. The multiset representations of the vertices of

T_{n, m}

, for

n \geq 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} : 2 \leq i \leq t$	${i - 1, i - 2, m + i}$
$v_{t + 1}$	${t, t - 1, m + t - 1}$
$v_{i} : t + 2 \leq i \leq n$	${n - i + 1, n - i + 2, n + m - i}$

Table 7. The multiset representations of the vertices of

T_{n, m}

, for

n \geq 4

, odd and

t = ⌊ \frac{n}{2} ⌋

according to the set

A = {v_{1}, v_{2}, u_{m}}

Table 7. The multiset representations of the vertices of

T_{n, m}

, for

n \geq 4

, odd 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} : 2 \leq i \leq 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} : t + 3 \leq i \leq n$	${n - i + 1, n - i + 2, n + m - i}$

Table 8. The multiset representations of the vertices of

T_{n, m}

, for

m \geq 4

according to the set

A = {v_{1}, v_{2}, u_{m}}

Table 8. The multiset representations of the vertices of

T_{n, m}

, for

m \geq 4

according to the set

A = {v_{1}, v_{2}, u_{m}}

$r_{m} (., .)$	$A = {v_{1}, v_{2}, u_{m}}$
$u_{j} : 1 \leq j \leq 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}}

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} : 1 \leq j \leq m - 1$	${m - j - 1, j, n + m + j - 2}$
$v_{i}^{0} : 1 \leq i \leq n$	${m + i - 2, i - 1, n + m - i - 1}$
$v_{n}^{j} : 1 \leq j \leq m - 1$	${n + m + j - 2, n + j - 1, m - j - 1}$
$v_{i}^{j} : 2 \leq i \leq n - 1, 1 \leq j \leq 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}}

Table 10. The edge-multiset representations of the edges of

C_{n}

according to the set

B = {v_{0}, v_{1}, v_{3}}

$r_{e m} (., .)$	$e_{0}$	$e_{1}$	$e_{2}$
$B = {v_{0}, v_{1}, v_{3}}$	${0, 0, 2}$	${0, 1, 1}$	${0, 1, 2}$
$r_{e m} (., .)$	$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_{e m} (., .)$	$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}}

Table 11. The edge-multiset representations of the edges of

C_{n}

according to the set

B = {v_{0}, v_{1}, v_{3}}

$r_{e m} (., .)$	$e_{i} : 3 < i < t$	$e_{t + i} : 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}}

Table 12. The edge-multiset representations of the edges of

C_{n}

according to the set

B = {v_{0}, v_{1}, v_{3}}

$r_{e m} (., .)$	$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_{e m} (., .)$	$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}}

Table 13. The edge-multiset representations of the edges of

C_{n}

according to the set

B = {v_{0}, v_{1}, v_{3}}

$r_{e m} (., .)$	$e_{i} : 3 < i < t$	$e_{t + i} : 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

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

Table 14. The edge-multiset representations of the edges of

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

$r_{e m} (., .)$	$B = {α_{2}, β_{2}, γ_{1}}$
$e_{1}$	${0, 1, μ + 1}$
$e_{i} : 2 \leq i \leq t$	${i - 2, i, μ + i}$
$e_{i} : i = t + 1$	${i - 2, ϑ - i + 1, ϑ + μ - i + 1}$
$e_{i} : t + 2 \leq i \leq ϑ$	${ϑ - i + 1, ϑ - i + 1, ϑ + μ - i + 1}$

Table 15. The edge-multiset representations of the edges of

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

Table 15. The edge-multiset representations of the edges of

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

$r_{e m} (., .)$	$B = {α_{2}, β_{2}, γ_{1}}$
$e_{1}^{'}$	${0, μ - 1, μ + 1}$
$e_{j}^{'} : 2 \leq j \leq t^{'}$	${j - 2, μ + j - 2, μ + j}$
$e_{j}^{'} : j = t^{'} + 1$	${j - 2, λ + μ - j - 1, λ + μ - j + 1}$
$e_{j}^{'} : t^{'} + 2 \leq j \leq λ$	${λ - j + 1, λ + μ - j - 1, λ + μ - j + 1}$

Table 16. The edge-multiset representations of the edges of

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

Table 16. The edge-multiset representations of the edges of

K P (ϑ, λ, μ)

according to the set

B = {α_{2}, β_{2}, γ_{1}}

$r_{e m} (., .)$	$e_{1}^{''}$	$e_{k}^{''} : 2 \leq k \leq μ$
$B = {α_{2}, β_{2}, γ_{1}}$	${0, 1, μ - k + 1}$	${k - 2, k, μ - 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}}

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_{e m} (., .)$	$B = {v_{1}, v_{2}, u_{m}}$
$f_{1}$	${0, 0, m + 1}$
$f_{i} : 2 \leq i \leq 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} : t + 2 \leq i \leq 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}}

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_{e m} (., .)$	$B = {v_{1}, v_{2}, u_{m}}$
$f_{1}$	${0, 0, m + 1}$
$f_{i} : 2 \leq i \leq 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} : t + 2 \leq i \leq 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}}

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_{e m} (., .)$	$B = {v_{1}, v_{2}, u_{m}}$
$f_{j}^{'} : 1 \leq j \leq 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}}

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_{e m} (., .)$	$B = {v_{1}^{m - 1}, v_{1}^{0}, v_{n}^{m - 1}}$
$e_{1}^{j} : 1 \leq j \leq m - 1$	${m - j - 1, j - 1, n + m + j - 3}$
$e_{i}^{0} : 1 \leq i \leq n$	${m + i - 2, i - 1, n + m - i - 2}$
$e_{n}^{j} : 1 \leq j \leq m - 1$	${n + m + j - 3, n + j - 2, m - j - 1}$
$e_{i}^{j} : 2 \leq i \leq n - 1, 1 \leq j \leq 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}}

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_{e m} (., .)$	$B = {a_{1}, a_{n - 2}, a_{n}}$
$a_{1} a_{2}$	${0, n - i - 1, n - 4}$
$a_{i} a_{i + 1} : 2 \leq i \leq 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}}

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_{e m} (., .)$	$a_{i} b_{i} : 2 \leq i \leq 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}}

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_{e m} (., .)$	$a_{1} a_{2}$	$a_{i} a_{i + 1} : 2 \leq i \leq n - 1$	$a_{i} b_{i} : 2 \leq i \leq 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}}

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_{e m} (., .)$	$x_{1} x_{2}$	$x_{i} x_{i + 1} : 2 \leq i \leq 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}}

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_{e m} (., .)$	$x_{i} y_{i} : 3 \leq i \leq n - 2$	$y_{i} z_{i} : 3 \leq i \leq 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}}

Table 26. The edge-multisets representations of the edges of

L_{n}

according to the set

B = {x_{1}, x_{2}, x_{n}}

$r_{e m} (., .)$	$x_{1} x_{2}$	$x_{i} x_{i + 1} : 2 \leq i \leq 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}}

Table 27. The edge-multisets representations of the edges of

L_{n}

according to the set

B = {x_{1}, x_{2}, x_{n}}

$r_{e m} (., .)$	$x_{i} y_{i} : 3 \leq i \leq n - 2$	$y_{i} z_{i} : 3 \leq i \leq 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}}

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_{e m} (., .)$	$x_{1} x_{2}$	$x_{i} x_{i + 1} : 2 \leq i \leq n - 1$	$x_{i} y_{i}^{1}, x_{i} y_{i}^{2} : 3 \leq i \leq 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}}

Table 29. The edge-multiset representations of some edges of

L_{n}

according to the set

W = {x_{1}, x_{2}, x_{n}}

$r_{e m} (., .)$	$x_{1} x_{2}$	$x_{i} x_{i + 1} : 2 \leq i \leq n - 1$	$x_{i} y_{i}^{1}, x_{i} y_{i}^{2} : 3 \leq i \leq n - 2$	$y_{i}^{1} z_{i}^{1}, y_{i}^{2} z_{i}^{2} : 3 \leq i \leq 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

Γ

according to the set

A = {u_{3}, v_{16}, v_{17}}

Table 30. The multiset representations of the vertices of

Γ

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

Γ

according to the set

B = {u_{1}, u_{7}, u_{13}, u_{16}}

Table 31. The edge-multiset representations of the edges of

Γ

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_{e m} (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_{e m} (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_{e m} (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

Γ

according to the set

B = {v_{2}, v_{3}, v_{12}}

Table 32. The edge-multiset representations of the edges of

Γ

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_{e m} (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_{e m} (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_{e m} (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

Γ

according to the set

A = {v_{2}, v_{4}, v_{9}, v_{19}}

Table 33. The multiset representations of the vertices of

Γ

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}$

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.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Ikhlaq, H.M.; Ismail, R.; Siddiqui, H.M.A.; Nadeem, M.F. A New Technique to Uniquely Identify the Edges of a Graph. Symmetry 2023, 15, 762. https://doi.org/10.3390/sym15030762

AMA Style

Ikhlaq HM, Ismail R, Siddiqui HMA, Nadeem MF. A New Technique to Uniquely Identify the Edges of a Graph. Symmetry. 2023; 15(3):762. https://doi.org/10.3390/sym15030762

Chicago/Turabian Style

Ikhlaq, Hafiz Muhammad, Rashad Ismail, Hafiz Muhammad Afzal Siddiqui, and Muhammad Faisal Nadeem. 2023. "A New Technique to Uniquely Identify the Edges of a Graph" Symmetry 15, no. 3: 762. https://doi.org/10.3390/sym15030762

APA Style

Ikhlaq, H. M., Ismail, R., Siddiqui, H. M. A., & Nadeem, M. F. (2023). A New Technique to Uniquely Identify the Edges of a Graph. Symmetry, 15(3), 762. https://doi.org/10.3390/sym15030762

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A New Technique to Uniquely Identify the Edges of a Graph

Abstract

1. Introduction

2. Literature Review

Multiset and Edge-Multiset Dimensions of Graphs

3. Methodology

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

4.1. Kayak Paddle Graph

4.2. Dragon Graph

4.3. Comb Products Graph

4.4. Results on the Edge-Multiset Dimension of Graphs

4.5. Graphs Having an Infinite Edge-Multiset Dimension

4.6. Graphs Having a Constant Edge-Multiset Dimension

4.7. Caterpillar Graph

4.8. Lobster Graph

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

4.10. Complete r-ary Tree Graph

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

5.1. Graphs G with $m d (Γ) < m d_{e} (Γ)$

5.2. Graphs G with $m d (Γ) > m d_{e} (Γ)$

6. Conclusions

Author Contributions

Funding

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

A New Technique to Uniquely Identify the Edges of a Graph

Abstract

1. Introduction

2. Literature Review

Multiset and Edge-Multiset Dimensions of Graphs

3. Methodology

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

4.1. Kayak Paddle Graph

4.2. Dragon Graph

4.3. Comb Products Graph

4.4. Results on the Edge-Multiset Dimension of Graphs

4.5. Graphs Having an Infinite Edge-Multiset Dimension

4.6. Graphs Having a Constant Edge-Multiset Dimension

4.7. Caterpillar Graph

4.8. Lobster Graph

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

4.10. Complete r-ary Tree Graph

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

5.1. Graphs G with m d ( Γ ) < m d e ( Γ )

5.2. Graphs G with m d ( Γ ) > m d e ( Γ )

6. Conclusions

Author Contributions

Funding

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

5.1. Graphs G with $m d (Γ) < m d_{e} (Γ)$

5.2. Graphs G with $m d (Γ) > m d_{e} (Γ)$