On Minimal Edge Version of Doubly Resolving Sets of a Graph

Ahmad,  Muhammad; Zahid, Zohaib; Zafar, Sohail

doi:10.61091/jcmcc119-18

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 119
Pages: 175-184

Research article

On Minimal Edge Version of Doubly Resolving Sets of a Graph

^¹, ^¹, ^¹

¹Department of Mathematics, School of Science, University of Management and Technology, Lahore 54770, Pakistan

Received: 11/06/2020
Accepted: 15/06/2021
Published: 31/03/2024

Copyright Link
License

Abstract

In this paper, we introduce the edge version of doubly resolving set of a graph which is based on the edge distances of the graph. As a main result, we computed the minimum cardinality $ψ_{E}$ of edge version of doubly resolving sets of family of $n$ -sunlet graph $S_{n}$ and prism graph $Y_{n}$ .

Keywords: Edge version of metric dimension, Edge version of doubly resolving set, Prism graph, $n$-sunlet graph

1. Introduction and Preliminaries

Let us take a graph $G = (V (G), E (G)),$ which is simple, connected and undirected, where its vertex set is $V (G)$ and edge set is $E (G)$ . The order of a graph $G$ is $| V (G) |$ and the size of a graph $G$ is $| E (G) |$ . The distance $d (a, b)$ between the vertices $a$ , $b \in V (G)$ is the length of a shortest path between them. If $d (c, a) \neq d (c, b)$ , then the vertex $c \in V (G)$ is said to resolve two vertices $a$ and $b$ of $V (G)$ . Suppose that $N = {n_{1}, n_{2}, \dots, n_{k}} \subseteq V (G)$ is an ordered set and $m$ is a vertex of $V (G)$ , then the representation $r (m, N)$ of $m$ with respect to $N$ is the k-tuple $(d (m, n_{1}), d (m, n_{2}), \dots, d (m, n_{k}))$ . If different vertices of $G$ have different representations with respect to $N$ , then the set $N$ is said to be a resolving set of $G$ . The metric basis of $G$ is basically a resolving set having minimum cardinality. The cardinality of metric basis is represented by $\dim (G)$ , and is called metric dimension of $G .$

In [1], Slater introduced the idea of resolving sets and also in [2], Harary and Melter introduced this concept individually. Different applications of this idea has been introduced in the fields like network discovery and verification [3], robot navigation [4] and chemistry.

The introduction of doubly resolving sets is given by Caceres et al. (see [5]) by presenting its connection with metric dimension of the cartesian product $G G$ of the graph $G$ . The doubly resolving sets create a valuable means for finding upper bounds on the metric dimension of graphs. The vertices $a$ and $b$ of the graph $G$ with order $| V (G) | \geq 2$ are supposed to doubly resolve vertices $u_{1}$ and $v_{1}$ of the graph $G$ if $d (u_{1}, a) - d (u_{1}, b) \neq d (v_{1}, a) - d (v_{1}, b) .$ A subset $D$ of vertices doubly resolves $G$ if every two vertices in $G$ are doubly resolved by some two vertices of $D$ . Precisely, in $G$ there do not exist any two different vertices having the same difference between their corresponding metric coordinates with respect to $D .$ A doubly resolving set with minimum cardinality is called the minimal doubly resolving set. The minimum cardinality of a doubly resolving set for $G$ is represented by $ψ (G) .$ In case of some convex polytopes, hamming and prism graphs, the minimal doubly resolving sets has been obtained in [6], [7] and [8] respectively.

Clearly, if $a$ and $b$ doubly resolve $u_{1}$ and $v_{1},$ then $d (u_{1}, a) - d (v_{1}, a) \neq 0$ or $d (u_{1}, b) - d (v_{1}, b) \neq 0,$ and thus $a$ or $b$ resolve $u_{1}$ and $v_{1},$ this shows that a doubly resolving set is also a resolving set, which implies $\dim (G) \leq ψ (G)$ for all graphs $G$ . Finding $ψ (G)$ and $\dim (G)$ are NP-hard problems proved in [9, 10].

The line graph $L (G)$ of a graph $G$ is defined as the graph whose vertices are the edges of $G$ , with two adjacent vertices if the corresponding edges have one vertex common in $G$ . In mathematics, the metric properties of line graphs have been studied to a great extent (see [11, 12, 13, 14, 15, 16]) and in chemistry literature, its significant applications have been proved (see [17, 18, 19, 20, 21, 22, 23]). In [24], the edge version of metric dimension has been introduced, which is defined as:

Definition 1.

The edge distance $d_{E} (f, g)$ between two edges $f, g \in E (G)$ is the length of a shortest path between vertices $f$ and $g$ in the line graph $L (G) .$
If $d_{E} (e, f) \neq d_{E} (e, g)$ , then the edge $e \in E (G)$ is said to edge resolve two edges $f$ and $g$ of $E (G)$ .
Suppose that $N_{E} = {f_{1}, f_{2}, \dots, f_{k}} \subseteq E (G)$ is an ordered set and $e$ is an edge of $E (G)$ . Then the edge version of representation $r_{E} (e, N_{E})$ of $e$ with respect to $N_{E}$ is the k-tuple $(d_{E} (e, f_{1}), d_{E} (e, f_{2}), \dots, d_{E} (e, f_{k}))$ .
If different edges of $G$ have different edge version of representations with respect to $N_{E}$ , then the set $N_{E}$ is said to be an edge version of resolving set of $G$ .
The edge version of metric basis of $G$ is basically an edge version of resolving set having minimum cardinality. The cardinality of edge version of metric basis is represented by $\dim_{E} (G)$ , and is called edge version of metric dimension of $G .$

The following theorems in [24] are important for us.

Theorem 1. Let $S_{n}$ be the family of $n$ -sunlet graph then $\dim_{E} (S_{n}) = {\begin{cases} 2, & i f n is even; \\ 3, & i f n is odd. \end{cases}$

Theorem 2. Let $Y_{n}$ be the family of prism graph then $\dim_{E} (Y_{n}) = 3$ for $n \geq 3.$

In this article, we proposed minimal edge version of doubly resolving sets of a graph $G$ , based on edge distances of graph $G$ as follows:

Definition 2.

The edges $f$ and $g$ of the graph $G$ with size $| E (G) | \geq 2$ are supposed to edge doubly resolve edges $f_{1}$ and $f_{2}$ of the graph $G$ if $d_{E} (f_{1}, f) - d_{E} (f_{1}, g) \neq d_{E} (f_{2}, f) - d_{E} (f_{2}, g)$ .
Let $D_{E} = {f_{1}, f_{2}, \dots, f_{k}}$ be an ordered set of the edges of $G$ . Then if any two edges $e \neq f \in E (G)$ are edge doubly resolved by some two edges of set $D_{E}$ then the set $D_{E} \subseteq E (G)$ is said to be an edge version of doubly resolving set of $G$ . The minimum cardinality of an edge version of doubly resolving set of $G$ is represented by $ψ_{E} (G) .$

Note that every edge version of a doubly resolving set is an edge version of a resolving set, which implies $\dim_{E} (G) \leq ψ_{E} (G)$ for all graphs $G$ .

2. The Edge Version of Doubly Resolving Sets for Family of $N$ -Sunlet Graph $S_{n}$

The family of $n$ -sunlet graph $S_{n}$ is obtained by joining $n$ pendant edges to a cycle graph $C_{n}$ (see Figure 1).

For our purpose, we label the inner edges of $S_{n}$ by { $e_{i}$ : $\forall$ $0 \leq i \leq n - 1$ } and the pendent edges by { $f_{i}$ : $\forall$ $0 \leq i \leq n - 1$ } as shown in Figure 1.

As motivated by Theorem 1, we obtain $ψ_{E} (S_{n}) \geq {\begin{cases} 2, & i f n is even; \\ 3, & i f n is odd. \end{cases}$

Furthermore, we will show that $ψ_{E} (S_{n}) = 3$ for $n \geq 4.$
In order to calculate the edge distances for family of $n$ -sunlet graphs $S_{n}$ , consider the line graph $L (S_{n})$ as shown in Figure 2.

Figure 2. $L (S_{n})$ of n-sunlet Graph $S_{n}$

Define

S_{i} (e_{0}) = {e \in E (S_{n}) : d (e_{0}, e) = i}

. For

ψ_{E} (S_{n})

with

n \geq 4,

we can locate the sets

S_{i} (e_{0})

that are represented in the Table 1. It is clearly observed from Figure 2 that

S_{i} (e_{0}) = \emptyset

when

i \geq k + 1

for

n = 2 k,

and

S_{i} (e_{0}) = \emptyset

when

i \geq k + 2

for

n = 2 k + 1

. From the above mentioned sets

S_{i} (e_{0}),

it is clear that they can be utilized to define the edge distances between two arbitrary edges of

E (S_{n})

in the subsequent way.

Table 1: $S_{i} (e_{0})$ for $S_{n}$
$n$	$i$	$S_{i} (e_{0})$
	$1 \leq i \leq k$	{ $f_{i - 1}$ , $e_{i}$ , $f_{n - i}$ , $e_{n - i}$ }
$2 k (k \geq 2)$	$k$	${f_{k - 1}, f_{k}, e_{k}}$
$2 k + 1 (k \geq 2)$	$k$	${f_{k - 1}, e_{k}, f_{k + 1}, e_{k + 1}}$
	$k + 1$	${f_{k}}$

The symmetry in Figure 2 shows that $d_{E} (e_{i}, e_{j}) = d_{E} (e_{0}, e_{| j - i |})$ for $0 \leq | j - i | \leq n - 1.$ If $n = 2 k$ , where $k \geq 2,$ we have

$d_{E} (f_{i}, f_{j}) = {\begin{cases} d_{E} (e_{0}, f_{| j - i |}) - 1, & i f | j - i | = 0; \\ d_{E} (e_{0}, f_{| j - i |}), & i f 1 \leq | j - i | < k; \\ d_{E} (e_{0}, f_{| j - i |}) + 1, & i f k \leq | j - i | \leq n - 1, \end{cases}$

$d_{E} (e_{i}, f_{j}) = {\begin{cases} d_{E} (e_{0}, f_{| j - i |}), & i f 0 \leq | j - i | \leq n - 1 for i \leq j; \\ d_{E} (e_{0}, f_{| j - i |}) - 1, & i f 1 \leq | j - i | < k for i > j; \\ d_{E} (e_{0}, f_{| j - i |}), & i f | j - i | = k for i > j; \\ d_{E} (e_{0}, f_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1 for i > j . \end{cases}$

If $n = 2 k + 1$ where $k \geq 2,$ we have

$d_{E} (f_{i}, f_{j}) = {\begin{cases} d_{E} (e_{0}, f_{| j - i |}) - 1, & i f | j - i | = 0; \\ d_{E} (e_{0}, f_{| j - i |}), & i f 1 \leq | j - i | \leq k; \\ d_{E} (e_{0}, f_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1, \end{cases}$

$d_{E} (e_{i}, f_{j}) = {\begin{cases} d_{E} (e_{0}, f_{| j - i |}), & i f 0 \leq | j - i | \leq n - 1 for i \leq j; \\ d_{E} (e_{0}, f_{| j - i |}) - 1, & i f 1 \leq | j - i | \leq k for i > j; \\ d_{E} (e_{0}, f_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1 for i > j . \end{cases}$

As a result, if we know the edge distance $d_{E} (e_{0}, e)$ for any $e \in E (S_{n})$ , then one can recreate the edge distances between any two edges from $E (S_{n}) .$

Lemma 1. $ψ_{E} (S_{n}) > 2$ , for $n = 2 k$ , $k \geq 2.$

Proof. As we know that for $n = 2 k$ , $ψ_{E} (S_{n}) \geq 2.$ So it is necessary to prove that each of the subset $D_{E}$ of edge set $E (S_{n})$ such that $| D_{E} | = 2$ is not an edge version of doubly resolving set for $S_{n} .$ In Table 2, seven possible types of the set $D_{E}$ are presented and for each of them the resultant non-edge doubly resolved pair of edges from edge set $E (S_{n})$ is found. To verify, let us take an example, the edges $e_{k}, e_{k + 1}$ are not edge doubly resolved by any two edges of the set ${e_{0}, e_{i}; k < i \leq n - 1}$ . Obviously, for $k < i \leq n - 1$ , we have $d_{E} (e_{0}, e_{k}) = d_{E} (e_{0}, e_{| k - 0 |}) = k$ , $d_{E} (e_{0}, e_{k + 1}) = d_{E} (e_{0}, e_{| k + 1 - 0 |}) = k - 1$ , $d_{E} (e_{i}, e_{k}) = d_{E} (e_{0}, e_{| k - i |}) = i - k$ and $d_{E} (e_{i}, e_{k + 1}) = d_{E} (e_{0}, e_{| k + 1 - i |}) = i - k - 1$ . So, $d_{E} (e_{0}, e_{k}) - d_{E} (e_{0}, e_{k + 1}) = d_{E} (e_{i}, e_{k}) - d_{E} (e_{i}, e_{k + 1}) = 1,$ that is, ${e_{0}, e_{i}; k < i \leq n - 1}$ is not an edge version of doubly resolving set of $S_{n}$ . Using this procedure we can verify all other non-edge doubly resolved pairs of edges for all other possible types of $D_{E}$ from Table 2.

Table 2: Non-edge Doubly Resolved Pairs of $S_{n}$ for $n = 2 k,$ $k \geq 2$
$D_{E}$	Non-edge doubly resolved pairs
${e_{0}, e_{i}}$ , $0 < i < k$	${e_{0}, e_{n - 1}}$
${e_{0}, e_{i}}$ , $k < i \leq n - 1$	${e_{k}, e_{k + 1}}$
${e_{0}, f_{i}}$ , $0 \leq i < k$	${e_{0}, f_{n - 1}}$
${e_{0}, f_{i}}$ , $k \leq i \leq n - 1$	${e_{0}, f_{0}}$
${f_{0}, f_{i}}$ , $1 \leq i < k$	${e_{k}, f_{k}}$
${f_{0}, f_{k}}$	${e_{0}, e_{1}}$
${f_{0}, f_{i}}$ , $k < i \leq n - 1$	${e_{1}, f_{1}}$

Lemma 2. $ψ_{E} (S_{n}) = 3,$ for $n = 2 k$ , $k \geq 2.$

Proof. The Table 3 demonstrate that edge version of representations of $S_{n}$ in relation to the set $D_{E}^{*} = {e_{0}, e_{1}, e_{k}}$ in a different manner.

Table 3: Vectors of Edge Metric Coordinates for $S_{n},$ $n = 2 k,$ $k \geq 2$
$i$	$S_{i} (e_{0})$	$D_{E}^{*} = {e_{0}, e_{1}, e_{k}}$
$0$	$e_{0}$	$(0, 1, k)$
$1 \leq i < k$	$f_{i - 1}$	$(i, i - 1, k + 1 - i)$
	$e_{i}$	$(i, i - 1, k - i)$
	$f_{n - i}$	$(i, i + 1, k + 1 - i)$
	$e_{n - i}$	$(i, i + 1, k - i)$
$i = k$	$f_{k - 1}$	$(k, k - 1, 1)$
	$f_{k}$	$(k, k, 1)$
	$e_{k}$	$(k, k - 1, 0)$

Now from Table 3, as $e_{0} \in D_{E}^{*}$ , so the first edge version of metric coordinate of the vector of $e_{0} \in S_{i} (e_{0})$ is equal to $0$ . For each $i \in {1, 2, 3, \dots, k}$ , one can easily check that there are no two edges $h_{1}, h_{2} \in S_{i} (e_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = 0$ . Also, for each $i, j \in {1, 2, 3, \dots, k}, i \neq j$ , there are no two edges $h_{1} \in S_{i} (e_{0})$ and $h_{2} \in S_{j} (e_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = i - j$ . In this manner, the set $D_{E}^{*} = {e_{0}, e_{1}, e_{k}}$ is the minimal edge version of doubly resolving set for $S_{n}$ with $n = 2 k$ , $k \geq 2$ and hence Lemma 2 holds.

Lemma 3. $ψ_{E} (S_{n}) = 3$ , for $n = 2 k + 1$ , $k \geq 2.$

Proof. The Table 4 demonstrate that the edge version of representations of $S_{n}$ in relation to the set $D_{E}^{*} = {e_{0}, e_{1}, e_{k + 1}}$ in a different way.

Table 4: Vectors of Edge Metric Coordinates for $S_{n},$ $n = 2 k + 1,$ $k \geq 2$
$i$	$S_{i} (e_{0})$	$D_{E}^{*} = {e_{0}, e_{1}, e_{k + 1}}$
$0$	$e_{0}$	$(o, 1, k)$
$1 \leq i < k$	$f_{i - 1}$	$(i, i - 1, k + 2 - i)$
	$e_{i}$	$(i, i - 1, k + 1 - i)$
	$f_{n - i}$	$(i, i + 1, k + 1 - i)$
	$e_{n - 1}$	$(i, i + 1, k - i)$
$i = k$	$f_{k - 1}$	$(k, k - 1, 2)$
	$e_{k}$	$(k, k - 1, 1)$
	$f_{k + 1}$	$(k, k + 1, 1)$
	$e_{k + 1}$	$(k, k, 0)$
$i = k + 1$	$f_{k}$	$(k + 1, k, 1)$

Now from Table 4, as $e_{0} \in D_{E}^{*}$ , so the first edge version of metric coordinate of the vector of $e_{0} \in S_{i} (e_{0})$ is equal to $0$ . Similarly for each $i \in {1, 2, 3, \dots, k + 1}$ , one can easily find that there are no two edges $h_{1}, h_{2} \in S_{i} (e_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = 0$ . Likewise, for every $i, j \in {1, 2, 3, \dots, k + 1}, i \neq j$ , there are no two edges $h_{1} \in S_{i} (e_{0})$ and $h_{2} \in S_{j} (e_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = i - j$ . Like so, the set $D_{E}^{*} = {e_{0}, e_{1}, e_{k + 1}}$ is the minimal edge version of doubly resolving set for $S_{n}$ with $n = 2 k + 1$ , $k \geq 2$ and consequently Lemma 3 holds.

It is displayed from the whole technique that $ψ_{E} (S_{n}) = 3$ , for $n \geq 4$ . We state the resulting main theorem by using Lemma 2 and Lemma 3 as mentioned below;

Theorem 3. Let $S_{n}$ be the $n$ -sunlet graph for $n \geq 4.$ Then $ψ_{E} (S_{n}) = 3.$

3. The Edge Version of Doubly Resolving Sets for Family of Prism Graph $Y_{n}$

A family of prism graph $Y_{n}$ is a cartesian product graph $C_{n} \times P_{2}$ , where $C_{n}$ is a cycle graph of order $n$ and $P_{2}$ is a path of order $2$ (see Figure 3).

The family of prism graph $Y_{n}$ consists of $4$ -sided faces and $n$ -sided faces. For our purpose, we label the inner cycle edges of $Y_{n}$ by { $e_{i}$ : $0 \leq i \leq n - 1$ }, middle edges by { $f_{i}$ : $0 \leq i \leq n - 1$ } and the outer cycle edges by { $g_{i}$ : $1 \leq i \leq n - 1$ } as shown in Figure 3.

As motivated by Theorem 1, we obtain $ψ_{E} (Y_{n}) \geq 3$ . Furthermore, we will show that $ψ_{E} (Y_{n}) = 3$ for $n \geq 6.$

In order to calculate the edge distances for family of prism graphs $Y_{n}$ , consider the line graph $L (Y_{n})$ as shown in Figure 4.

Figure 4. $L (Y_{n})$ of Prism Graph $Y_{n}$

Define $S_{i} (f_{0}) = {f \in E (Y_{n}) : d_{E} (f_{0}, f) = i}$ . For $ψ_{E} (Y_{n})$ with $n \geq 6,$ we can locate the sets $S_{i} (f_{0})$ that are represented in the Table 5. It is clearly observed from Figure 4 that $S_{i} (f_{0}) = \emptyset$ for $i \geq k + 2.$ From the above mentioned sets $S_{i} (f_{0}),$ it is clear that they can be utilized to define the edge distance between two arbitrary edges of $E (Y_{n})$ in the subsequent way.

Table 5: $S_{i} (f_{0})$ for $Y_{n}$
$n$	$i$	$S_{i} (f_{0})$
	1	${e_{0}, g_{0}, e_{n - 1}, g_{n - 1}}$
	2 $\leq i \leq k$	${f_{i - 1}, e_{i - 1}, g_{i - 1}, f_{n + 1 - i}, e_{n - i}, g_{n - i}$ }
$2 k (k \geq 3)$	$k + 1$	${f_{k}}$
$2 k + 1 (k \geq 3)$	$k + 1$	${f_{k}, e_{k}, g_{k}, f_{k + 1}}$

The symmetry in Figure 4 shows that $d_{E} (f_{i}, f_{j}) = d_{E} (f_{0}, f_{| j - i |})$ for $0 \leq | j - i | \leq n - 1.$ If $n = 2 k$ , where $k \geq 3,$ we have

$d_{E} (e_{i}, e_{j}) = d_{E} (g_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}) - 1, & i f 0 \leq | j - i | < k; \\ d_{E} (f_{0}, e_{| j - i |}), & i f k \leq | j - i | \leq n - 1, \end{cases}$

$d_{E} (f_{i}, e_{j}) = d_{E} (f_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}), & i f 0 \leq | j - i | \leq n - 1, for i \leq j; \\ d_{E} (f_{0}, e_{| j - i |}) - 1, & i f 1 \leq | j - i | < k, for i > j; \\ d_{E} (f_{0}, e_{| j - i |}), & i f | j - i | = k, for i > j; \\ d_{E} (f_{0}, e_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1, for i > j, \end{cases}$ $d_{E} (e_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}) + 1, & i f | j - i | = 0; \\ d_{E} (f_{0}, e_{| j - i |}), & i f 1 \leq | j - i | < k; \\ d_{E} (f_{0}, e_{| j - i |}) + 1, & i f k \leq | j - i | \leq n - 1. \end{cases}$ If $n = 2 k + 1$ where $k \geq 3,$ we have $d_{E} (e_{i}, e_{j}) = d_{E} (g_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}) - 1, & i f 0 \leq | j - i | \leq k; \\ d_{E} (f_{0}, e_{| j - i |}), & i f k < | j - i | \leq n - 1, \end{cases}$ $d_{E} (f_{i}, e_{j}) = d_{E} (f_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}), & i f 0 \leq | j - i | \leq n - 1 for i \leq j; \\ d_{E} (f_{0}, e_{| j - i |}) - 1, & i f 1 \leq | j - i | \leq k for i > j; \\ d_{E} (f_{0}, e_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1 for i > j, \end{cases}$ $d_{E} (e_{i}, g_{j}) = {\begin{cases} d_{E} (f_{0}, e_{| j - i |}) + 1, & i f | j - i | = 0; \\ d_{E} (f_{0}, e_{| j - i |}), & i f 1 \leq | j - i | \leq k; \\ d_{E} (f_{0}, e_{| j - i |}) + 1, & i f k < | j - i | \leq n - 1. \end{cases}$ As a result, if we know the edge distance $d_{E} (f_{0}, f)$ for any $f \in E (Y_{n})$ then one can recreate the edge distances between any two edges from $E (Y_{n}) .$

Lemma 4. $ψ_{E} (Y_{n}) = 3,$ for $n = 2 k$ , $k \geq 3.$

Proof. The Table 6 demonstrate that edge version of representations of $Y_{n}$ in relation to the set $D_{E}^{*} = {e_{0}, e_{k - 1}, f_{k + 1}}$ in a different manner.

Now from Table 6, as $e_{0} \in D_{E}^{*}$ , so the first edge version of metric coordinate of the vector of $f_{0} \in S_{i} (f_{0})$ is equal to $1$ . For each $i \in {1, 2, 3, \dots, k + 1}$ , one can easily check that there are no two edges $h_{1}, h_{2} \in S_{i} (f_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = 0$ . Also, for each $i, j \in {1, 2, 3, \dots, k + 1}, i \neq j$ , there are no two edges $h_{1} \in S_{i} (f_{0})$ and $h_{2} \in S_{j} (f_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = i - j$ . In this manner, the set $D_{E}^{*} = {e_{0}, e_{k - 1}, f_{k + 1}}$ is the minimal edge version of doubly resolving set for $Y_{n}$ with $n = 2 k$ , $k \geq 3$ and hence Lemma 4 holds.

Lemma 5. $ψ_{E} (Y_{n}) = 3$ , for $n = 2 k + 1$ , $k \geq 3.$

Proof. The Table 7 demonstrate that the edge version of representations of $Y_{n}$ in relation to the set $D_{E}^{*} = {e_{0}, e_{k}, g_{k + 2}}$ in a different way.

Table 7: Vectors of Edge Metric Coordinates for $Y_{n},$ $n = 2 k + 1,$ $k \geq 3$
$i$	$S_{i} (f_{0})$	$D_{E}^{*} = {e_{0}, e_{k}, g_{k + 2}}$
$0$	$f_{0}$	$(1, k + 1, k - 1)$
$1$	$e_{0}$	$(0, k, k)$
	$g_{0}$	$(2, k + 1, k - 1)$
	$e_{n - 1}$	$(1, k, k - 1)$
	$g_{n - 1}$	$(2, k + 1, k - 2)$
$2$	$f_{1}$	$(1, k, k)$
	$e_{1}$	$(1, k - 1, k + 1)$
	$g_{1}$	$(2, k, k)$
	$f_{n - 1}$	$(2, k, k - 2)$
	$e_{n - 2}$	$= {\begin{cases} (2, 2, 2), & i f k = 3; \\ (2, k - i, k - 2), & i f k < 3. \end{cases}$
	$g_{n - 2}$	$(3, k, k - 3)$
$3 \leq i \leq k$	$f_{i - 1}$	$(i - 1, k + 2 - i, k + 4 - i)$
	$e_{i - 1}$	$(i - 1, k + 1 - i, k + 4 - i)$
	$g_{i - 1}$	$(i, k + 2 - i, k + 3 - i)$
	$f_{n + 1 - i}$	$= {\begin{cases} (k, 2, 1), & i f i = k; \\ (i, k + 2 - i, k - i), & i f i + 1 \leq k \end{cases}$
	$e_{n - i}$	$= {\begin{cases} (k, 1, 2), & i f i = k; \\ (i, 2, 2), & i f i + 1 = k; \\ (i, k + 1 - i, k - i), & i f i + 1 < k \end{cases}$
	$g_{n - i}$	$= {\begin{cases} (k + 1, 2, 1), & i f i = k; \\ (i + 1, k + 2 - i, k - 1 - i), & i f i + 1 \leq k \end{cases}$
$i = k + 1$	$f_{k}$	$(k, 1, 3)$
	$e_{k}$	$(k, 0, 3)$
	$g_{k}$	$(k + 1, 2, 2)$
	$f_{k + 1}$	$(k + 1, 1, 2)$

Now from Table 7, as $e_{0} \in D_{E}^{*}$ , so the first edge version of metric coordinate of the vector of $f_{0} \in S_{i} (f_{0})$ is equal to $1$ . Similarly for each $i \in {1, 2, 3, \dots, k + 1}$ , one can easily find that here are no two edges $h_{1}, h_{2} \in S_{i} (f_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = 0$ . Likewise, for every $i, j \in {1, 2, 3, \dots, k + 1}, i \neq j$ , there are no two edges $h_{1} \in S_{i} (f_{0})$ and $h_{2} \in S_{j} (f_{0})$ such that $r_{E} (h_{1}, D_{E}^{*}) - r_{E} (h_{2}, D_{E}^{*}) = i - j$ . Like so, the set $D_{E}^{*} = {e_{0}, e_{k}, g_{k + 2}}$ is the minimal edge version of doubly resolving set for $Y_{n}$ with $n = 2 k + 1$ , $k \geq 3$ and consequently Lemma 5 holds.

It is displayed from the whole technique that $ψ_{E} (Y_{n}) = 3$ , for $n \geq 6$ . We state the resulting main theorem by using Lemma 4 and Lemma 5 as mentioned below;

Theorem 4. Let $Y_{n}$ be the prism graph for $n \geq 6.$ Then $ψ_{E} (Y_{n}) = 3.$

Conclusion

In this article, we computed the minimal edge version of doubly resolving sets and its cardinality $ψ_{E} (G)$ by considering $G$ as a family of $n$ -sunlet graph $S_{n}$ and prism graph $Y_{n}$ . In case of $n$ -sunlet graphs, the graph is interesting to consider in the sense that its edge version of metric dimension $\dim_{E} (S_{n})$ is dependent on the parity of $n$ for both even and odd cases. The cardinality $ψ_{E} (S_{n})$ of minimal edge version of doubly resolving set of $n$ -sunlet graph $S_{n}$ is independent from the parity of $n$ . In the case of prism graph $Y_{n}$ , the edge version of metric dimension $\dim_{E} (Y_{n})$ and the cardinality $ψ_{E} (Y_{n})$ of its minimal edge version of doubly resolving set are same for every $n \geq 6.$

Problem 1. Compute edge version of doubly resolving sets for some generalized petersen graphs.

Acknowledgment

The authors would like to express their honest appreciation to the referees for their valuable comments, which led to a improved manuscript.

References:

Slater, P.J., 1975. Leaves of trees. Congr. Numer, 14(549-559), p.37.
Harary, F. and Melter, R.A., 1976. On the metric dimension of a graph. Ars Combin, 2(191-195), p.1.
Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal’ak, M. and Ram, L.S., 2006. Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12), pp.2168-2181.
Liu, K. and Abu-Ghazaleh, N., 2006, August. Virtual coordinates with backtracking for void traversal in geographic routing. In International Conference on Ad-Hoc Networks and Wireless (pp. 46-59). Berlin, Heidelberg: Springer Berlin Heidelberg.
Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C. and Wood, D.R., 2007. On the metric dimension of cartesian products of graphs. SIAM Journal on Discrete Mathematics, 21(2), pp.423-441.
Kratica, J., Kovačević-Vujčić, V., Čangalović, M. and Stojanović, M., 2012. Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Applied Mathematics and Computation, 218(19), pp.9790-9801.
Kratica, J., Kovačević-Vujčić, V., Čangalović, M. and Stojanović, M., 2012. Minimal doubly resolving sets and the strong metric dimension of Hamming graphs. Applicable Analysis and Discrete Mathematics, pp.63-71.
Čangalović, M., Kratica, J., Kovačević-Vujčić, V. and Stojanović, M., 2013. Minimal doubly resolving sets of prism graphs. Optimization, 62(8), pp.1037-1043.
Khuller, S., Raghavachari, B. and Rosenfeld, A., 1996. Landmarks in graphs. Discrete Applied Mathematics, 70(3), pp.217-229.
Kratica, J., Čangalović, M. and Kovačević-Vujčić, V., 2009. Computing minimal doubly resolving sets of graphs. Computers & Operations Research, 36(7), pp.2149-2159.
Buckley, F., 1981. Mean distance in line graphs, Congr. Numer., 32, pp.153-162.
Gutman, I., 1996. Distance of line graphs. Graph Theory Notes NY, 31, pp.49-52.
Gutman, I. and Pavlovic, L., 1997. More on distance of line graphs. Graph Theory Notes NY, 33, pp.14-18.
Liu, J.B., Nadeem, M.F., Siddiqui, H.M.A. and Nazir, W., 2019. Computing metric dimension of certain families of Toeplitz graphs. IEEE Access, 7, pp.126734-126741.
Ramane, H.S. and Gutman, I., 2010. Counterexamples for properties of line graphs of graphs of diameter two. Kragujevac Journal of Mathematics, 34(34), pp.147-150.
Ramane, H.S., Ganagi, A.B. and Gutman, I., 2012. On a conjecture on the diameter of line graphs of graphs of diameter two. Kragujevac Journal of Mathematics, 36(1), pp.59-62.
Gutman, I. and Estrada, E., 1996. Topological indices based on the line graph of the molecular graph. Journal of Chemical Information and Computer Sciences, 36(3), pp.541-543.
Gutman, I. and Tomović, Ž., 2000. On the application of line graphs in quantitative structure-property studies. Journal of the Serbian Chemical Society, 65(8), pp.577-580.
Gutman, I., 2010. Edge versions of topological indices. Novel Molecular Structure Descriptors-Theory and Applications II, Univ. Kragujevac, Kragujevac, 3.
Liu, J.B., Ali, B., Malik, M.A., Siddiqui, H.M.A. and Imran, M., 2019. Reformulated Zagreb indices of some derived graphs. Mathematics, 7(4), p.366.
Liu, J.B., Kashif, A., Rashid, T. and Javaid, M., 2019. Fractional metric dimension of generalized Jahangir graph. Mathematics, 7(1), p.100.
Liu, J.B., Munir, M., Yousaf, A., Naseem, A. and Ayub, K., 2019. Distance and adjacency energies of multi-level wheel networks. Mathematics, 7(1), p.43.
Liu, J.B., Shafiq, M.K., Ali, H., Naseem, A., Maryam, N. and Asghar, S.S., 2019. Topological indices of m th chain silicate graphs. Mathematics, 7(1), p.42.
Nasir, R., Zafar, S. and Zahid, Z., 2018. Edge metric dimension of graphs. Ars Combinatoria, 147, pp.143-156.

[1] Slater, P.J., 1975. Leaves of trees. Congr. Numer, 14(549-559), p.37.

[2] Harary, F. and Melter, R.A., 1976. On the metric dimension of a graph. Ars Combin, 2(191-195), p.1.

[3] Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal’ak, M. and Ram, L.S., 2006. Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12), pp.2168-2181.

[4] Liu, K. and Abu-Ghazaleh, N., 2006, August. Virtual coordinates with backtracking for void traversal in geographic routing. In International Conference on Ad-Hoc Networks and Wireless (pp. 46-59). Berlin, Heidelberg: Springer Berlin Heidelberg.

[5] Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C. and Wood, D.R., 2007. On the metric dimension of cartesian products of graphs. SIAM Journal on Discrete Mathematics, 21(2), pp.423-441.

[6] Kratica, J., Kovačević-Vujčić, V., Čangalović, M. and Stojanović, M., 2012. Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Applied Mathematics and Computation, 218(19), pp.9790-9801.

[7] Kratica, J., Kovačević-Vujčić, V., Čangalović, M. and Stojanović, M., 2012. Minimal doubly resolving sets and the strong metric dimension of Hamming graphs. Applicable Analysis and Discrete Mathematics, pp.63-71.

[8] Čangalović, M., Kratica, J., Kovačević-Vujčić, V. and Stojanović, M., 2013. Minimal doubly resolving sets of prism graphs. Optimization, 62(8), pp.1037-1043.

[9] Khuller, S., Raghavachari, B. and Rosenfeld, A., 1996. Landmarks in graphs. Discrete Applied Mathematics, 70(3), pp.217-229.

[10] Kratica, J., Čangalović, M. and Kovačević-Vujčić, V., 2009. Computing minimal doubly resolving sets of graphs. Computers & Operations Research, 36(7), pp.2149-2159.

[11] Buckley, F., 1981. Mean distance in line graphs, Congr. Numer., 32, pp.153-162.

[12] Gutman, I., 1996. Distance of line graphs. Graph Theory Notes NY, 31, pp.49-52.

[13] Gutman, I. and Pavlovic, L., 1997. More on distance of line graphs. Graph Theory Notes NY, 33, pp.14-18.

[14] Liu, J.B., Nadeem, M.F., Siddiqui, H.M.A. and Nazir, W., 2019. Computing metric dimension of certain families of Toeplitz graphs. IEEE Access, 7, pp.126734-126741.

[15] Ramane, H.S. and Gutman, I., 2010. Counterexamples for properties of line graphs of graphs of diameter two. Kragujevac Journal of Mathematics, 34(34), pp.147-150.

[16] Ramane, H.S., Ganagi, A.B. and Gutman, I., 2012. On a conjecture on the diameter of line graphs of graphs of diameter two. Kragujevac Journal of Mathematics, 36(1), pp.59-62.

[17] Gutman, I. and Estrada, E., 1996. Topological indices based on the line graph of the molecular graph. Journal of Chemical Information and Computer Sciences, 36(3), pp.541-543.

[18] Gutman, I. and Tomović, Ž., 2000. On the application of line graphs in quantitative structure-property studies. Journal of the Serbian Chemical Society, 65(8), pp.577-580.

[19] Gutman, I., 2010. Edge versions of topological indices. Novel Molecular Structure Descriptors-Theory and Applications II, Univ. Kragujevac, Kragujevac, 3.

[20] Liu, J.B., Ali, B., Malik, M.A., Siddiqui, H.M.A. and Imran, M., 2019. Reformulated Zagreb indices of some derived graphs. Mathematics, 7(4), p.366.

[21] Liu, J.B., Kashif, A., Rashid, T. and Javaid, M., 2019. Fractional metric dimension of generalized Jahangir graph. Mathematics, 7(1), p.100.

[22] Liu, J.B., Munir, M., Yousaf, A., Naseem, A. and Ayub, K., 2019. Distance and adjacency energies of multi-level wheel networks. Mathematics, 7(1), p.43.

[23] Liu, J.B., Shafiq, M.K., Ali, H., Naseem, A., Maryam, N. and Asghar, S.S., 2019. Topological indices of m th chain silicate graphs. Mathematics, 7(1), p.42.

[24] Nasir, R., Zafar, S. and Zahid, Z., 2018. Edge metric dimension of graphs. Ars Combinatoria, 147, pp.143-156.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing