Fault-tolerant edge metric dimension of certain families of graphs

1.   Introduction and preliminaries

Suppose that $G$ is connected, simple and undirected graph having edge set $E(G)$ and vertex set $V(G)$, respectively. The order of graph $G$ is $|V(G)|$ and size of graph $G$ is $|E(G)|$. Moreover, $\Delta(G)$ and $\delta(G)$ represent the maximum and minimum degree of graph $G$ respectively. Let $W = \{v_1, v_2, \ldots, v_k\}$ be an ordered set of $V(G)$ and let $u$ be a vertex of $G$. The representation $r(u\mid W)$ of $u$ with respect to $W$ is the k-tuple $(d(u, v_1), d(u, v_2), \ldots, d(u, v_k))$. If distinct vertices of $G$ have distinct representation with respect to $W$, then $W$ is called metric generator for $G$. A metric generator of minimum cardinality is metric basis for $G$, and its cardinality is called metric dimension of $G$, denoted by $\dim(G)$ (see ^[1]). A metric generator $\acute{W}$ for $G$ is called fault-tolerant metric generator if $\acute{W} \setminus \{v\}$ is also a metric generator, for each $v \in \acute{W}$. The fault-tolerant metric dimension of $G$ is the minimum cardinality of this set $\acute{W}$ and is denoted by $fdim(G)$ (see ^[2]).

Let $d(x, e)$ denotes distance between edge $e$ and vertex $x$, defined as $d(x, e) = \min \{d(x, a),$ $d(x, b)\}$, where $e = ab$ (see ^[3]). A vertex $x$ distinguishes two edges $e_1$ and $e_2$, if $d(e_1, x)\neq d(e_2, x)$. Let $W_E = \{w_1, w_2, \ldots, w_k\}$ be an ordered set of vertices of $G$ and let $e$ be an edge of $G$. The representation $r(e\mid W_E)$ of $e$ with respect to $W_E$ is the k-tuple $(d(e, w_1), d(e, w_2), \ldots, d(e, w_k))$. If distinct edges of $G$ have distinct representation with respect to $W_E$, then $W_E$ is called edge metric generator for $G$ (see ^[3]). An edge metric generator of minimum cardinality is an edge metric basis for $G$, and its cardinality is called edge metric dimension of $G$, denoted by $\text{edim}(G)$ ^[4,5,6,7].

Slater proposed the idea of metric dimension to find the location of intruder in a network (see ^[1,8]). The proposed idea was further extended by Melter and Harary in ^[9]. Metric dimension is important in robot navigation, chemistry, problems of image processing and pattern recognition etc. (see ^{[10,11,12,13,14,15]}). The use of metric dimension of graphs was also observed in games like mastermind and coin weighing (see ^[16]).

Kelenc in ^[3] extended the idea of metric dimension to edge metric dimension and make a comparison between them. He also discussed some useful results for paths $P_n$, cycles $C_n$, complete graphs $K_n$ and wheel graphs. In ^[8], Zubrilina classified the graphs on $n$ vertices for which edge metric dimension is $n-1$. In ^[17], Kratica computed the edge metric dimension of generalized petersen graphs $GP(n, k)$ for $k = 1$ and $2$ while for the other values of $k$ the lower bound is given. In ^[18], Ahsan computed the edge metric dimension of convex polytopes related graphs ^[19,20,21].

In $2008$, Hernando, Slater, Mora and Wood introduced the new idea of fault-tolerant metric dimension in ^[2]. Further in $2017$, Voronov calculated the fault-tolerant metric dimension of the king's graph (see in ^[22]). In 2018, Raza et al. computed the fault-tolerant metric dimension of generalized convex polytopes ^[23]. Recently in $2019$, Liu, Munir, Ali, Hussain and Ahmed have computed the fault-tolerant metric dimension of wheel related graphs like gear graphs ^[24]. Basak has computed the fault-tolerant metric dimension of circulant graphs ^[25].

A framework where failure of any single unit, another chain of units not containing the defective unit can substitute the initially utilized chain is called fault-tolerant self-stable framework. These graphs can tolerate the failure of one part (vertex) keeping consistent execution (see ^[24,26]). For this purpose we propose the concept of fault-tolerant edge metric dimension. Let $\acute{W}_E$ be edge metric generator of graph $G$, then $\acute{W}_E$ is called fault-tolerant edge metric generator of $G$ if $\acute{W}_E \setminus \{v \}$ is also an edge metric generator of graph $G$ for each $v \in \acute{W}_E$. A fault-tolerant edge metric generator of minimum cardinality is a fault-tolerant edge metric basis for graph $G$, and its cardinality is called fault-tolerant edge metric dimension of $G$, we are denoting it by $fedim(G)$ ^[27,28]. In this concept, we will extend the work of edge metric dimension to fault-tolerant edge metric dimension.

The lemmas given below are very helpful for calculating the fault-tolerant edge metric dimension of graphs:

Lemma 1.1. ^[3] For any $n\geq 2$, $\mathit{\text{edim}}(P_n) = \dim(P_n) = 1$, $\mathit{\text{edim}}(C_n) = \dim(C_n) = 2$, $\mathit{\text{edim}}(K_n) = \dim(K_n) = n-1$. Moreover, $\mathit{\text{edim}}(G) = 1$ if and only if $G$ is path.

Lemma 1.2. ^[3] For a connected graph $G$, $\mathit{\text{edim}}(G) \geq log_2(\triangle(G))$.

Lemma 1.3. ^[3] For a connected graph $G$ of order $n$, $edim(G) \geq 1+ \lceil\log_2 \delta(G) \rceil$.

From the definition of fault-tolerant edge metric dimension, it can be seen that

Lemma 1.4. For a connected graph $G$,

1. $fedim(G) \geq 1 + edim(G)$.

2. $2 \leq fedim(G) \leq n$.

The rest of paper is structured as follows: In the second section, we will study the fault-tolerant edge metric dimension of family of path, cycle and complete graphs. In third section, we will investigate the fault-tolerant edge metric dimension of family of cycle with chord graphs $C_n^m$. In fourth section, fault-tolerant edge metric dimension of family of tadpole graphs $G_{n}^l$ will be determined. In last section, we will compute the fault-tolerant edge metric dimension of family of kayak paddle graphs $G_{n, m}^l$.

2.   Fault-tolerant edge metric dimension of family of path, cycle and complete graphs

In this section, we will investigate the fault-tolerant edge metric dimension of family of paths, cycles and complete graphs. The family $P_n$ have $V(P_n) = \{u_1, u_2, \ldots, u_n\}$ and $E(P_n) = \{u_i u_{i+1}: 1\leq i\leq n-1 \}$. The family $P_n$ for $n = 10$ is shown in Figure 1. The following theorem tells us the edge metric dimension of $P_n$.

Figure 1.  Path graph $P_{10}$.

DownLoad: Full-Size Img PowerPoint

Theorem 2.1. ^[3] For any integer $n\geq 2$, $edim(P_n) = 1$.

Now, we will compute the fault-tolerant edge metric dimension of $P_n$.

Theorem 2.2. For any integer $n\geq 2$, $fedim(P_n) = 2$.

Proof. In order to compute fault-tolerant edge metric dimension of $P_n$, we have $\acute{W}_E = \{u_1, u_n\} \ \subset V(P_n)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $P_n$. For this, we give representations of each edge of $P_n$.

$r(u_iu_{i+1}|\acute{W}_E) = (i-1, n-i-1)$, where $1 \leq i \leq n-1$.

We see that there are no two tuples having the same representations. This shows that fault-tolerant edge metric dimension of $P_n$ is less than or equal to $2$. Since by Lemma 1.4, $P_n$ has fault-tolerant edge metric dimension greater than or equal to $2$. Hence fault-tolerant edge metric dimension is equal to $2$.

The family $C_n$ have $V(C_n) = \{u_1, u_2, \ldots, u_n\}$ and $E(C_n) = \{u_i u_{i+1}: 1\leq i\leq n-1 \}\cup \{ u_n u_1\}$. The family $C_n$ for $n = 15$ is shown in Figure 2. The following theorem tells us the edge metric dimension of $C_n$.

Figure 2.  Cycle graph $C_{15}$.

DownLoad: Full-Size Img PowerPoint

Theorem 2.3. ^[3] For any integer $n\geq 3$, $edim(C_n) = 2$.

Now, we will compute the fault-tolerant edge metric dimension of $C_n$.

Theorem 2.4. For any integer $n\geq 3$, $fedim(C_n) = 3$.

Proof. In order to compute fault-tolerant edge metric dimension of $C_n$, we have the following cases.

Case (i). $n$ is odd. Take $\acute{W}_E = \{u_1, u_2, u_3\} \ \subset V(C_n)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n$. For this, we give representations of each edge of $C_n$.

$r(u_n u_1|\acute{W}_E) = \ (0, 1, 2)$.

Case (ii). $n$ is even. Take $\acute{W}_E = \{u_1, u_2, u_3\} \ \subset V(C_n)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n$. For this, we give representations of each edge of $C_n$.

$r(u_n u_1|\acute{W}_E) = \ (0, 1, 2)$.

We see that there are no two tuples having the same representations. This shows that fault-tolerant edge metric dimension of $C_n$ is less than or equal to $3$. Since by Lemma 1.4, $C_n$ has fault-tolerant edge metric dimension greater than or equal to $3$. Hence fault-tolerant edge metric dimension of $C_n$ is equal to $3$.

Theorem 2.5. For any integer $n\geq 2$, $fedim(K_n) = n$.

Proof. The proof is straight forward from Lemma 1.1 and Lemma 1.4.

3.   Fault-tolerant edge metric dimension of family of cycle with chord graphs $C_n^m$

In this section, we will investigate the fault-tolerant edge metric dimension of family of cycle with chord graphs $C_n^m$. The family $C_n^m$ have $V(C_n^m) = \{v_1, v_2, \ldots, v_n\}$ and $E(C_n^m) = \{v_iv_{i+1}: 1\leq i\leq n-1 \} \cup \{ v_n v_1, v_1 v_m\}$. It suffices to consider $2 < m \leq \lfloor \frac{n}{2} \rfloor$. The family $C_n^m$ for $n = 20$ and $m = 9$ is shown in Figure 3. The following theorem tells us the edge metric dimension of $C_n^m$.

Figure 3.  Cycle with Chord graph $C_{20}^9$.

DownLoad: Full-Size Img PowerPoint

Theorem 3.1. ^[29] For all $n\geq 4$, $edim(C_n^m) = 2$.

Now, we will compute the fault-tolerant edge metric dimension of $C_n^m$.

Theorem 3.2. For all $n\geq 4$, $fedim(C_n^m) = 3$.

Proof. In order to compute fault-tolerant edge metric dimension of $C_n^m$, we have the following cases.

Case (i). Both $n$ and $m$ are even. Let $\acute{W}_E = \{v_2, v_{\frac{m}{2}+1}, v_{m+1}\} \ \subset V(C_n^m)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n^m$. For this, we give representations of each edge of $C_n^m$.

$r(v_n v_1|\acute{W}_E) = \ (1, \frac{m}{2}, 2)$ and $r(v_1 v_m|\acute{W}_E) = \ (1, \frac{m}{2}-1, 1)$.

Case (ii). $n$ is odd and $m$ is even. Let $\acute{W}_E = \{ v_2, v_{\frac{m}{2}+1}, v_{m+1} \} \ \subset V(C_n^m)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n^m$. For this, we give representations of each edge of $C_n^m$.

$r(v_n v_1|\acute{W}_E) = \ (1, \frac{m}{2}, 2)$ and $r(v_1 v_m|\acute{W}_E) = \ (1, \frac{m}{2}-1, 1)$.

Case (iii). $n$ is even and $m$ is odd. Let $\acute{W}_E = \{ v_2, v_{ \frac{m+1}{2}+1}, v_{\frac{n}{2} + \frac{m+1}{2}} \} \ \subset V(C_n^m)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n^m$. For this, we give representations of each edge of $C_n^m$.

$r(v_n v_1|\acute{W}_E) = \ (1, \frac{m-1}{2}, m-2)$ and $r(v_1 v_m|\acute{W}_E) = \ (1, \frac{m-1}{2}-1, m-1)$.

Case (iv). Both $n$ and $m$ are odd. Let $\acute{W}_E = \{ v_{\frac{m+1}{2}}, v_{m+1}, v_n \} \ \subset V(C_n^m)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $C_n^m$. For this, we give representations of each edge of $C_n^m$.

$r(v_n v_1|\acute{W}_E) = \ (\frac{m-1}{2}, 2, 0)$ and $r(v_1 v_m|\acute{W}_E) = \ (\frac{m-1}{2}, 1, 1)$.

We see that there are no two tuples having the same representations in all the four cases. This shows that fault-tolerant edge metric dimension of $C_{n}^m$ is less than or equal to $3$. Since by Lemma 1.4, $C_{n}^m$ is not a path so fault-tolerant edge metric dimension of $C_{n}^m$ is greater than or equal to $3$. Hence fault-tolerant edge metric dimension of $C_{n}^m$ is $3$.

4.   Fault-tolerant edge metric dimension of family of tadpole graphs $G_{n}^l$

In this section, we will compute the fault-tolerant edge metric dimension of family of tadpole graphs $G_{n}^l$. The family $G_{n}^l$ have $V(G_{n}^l) = \{v_1, v_2, \ldots, v_n, u_1, u_2, \ldots, u_{l} \}$ and $E(G_{n}^l) = \{v_i v_{i+1} : 1\leq i \leq n-1 \} \cup \{ u_s u_{s+1}, : 1\leq s \leq l-1 \} \cup \{v_n u_1, u_1v_1\}$. The graph $G_{n}^l$ for $n = 9$ and $l = 7$ is shown in Figure 4. The following theorem tells us the edge metric dimension of $G_{n}^l$.

Figure 4.  Tadpole graph $G_9^7$.

DownLoad: Full-Size Img PowerPoint

Theorem 4.1. ^[29] For all $n\geq 2$, $l \geq 3$, $edim(G_{n}^l) = 2$.

Now, we will compute the fault-tolerant edge metric dimension of $G_{n}^l$.

Theorem 4.2. For all $n \geq 2$, $l \geq 3$, $fedim(G_{n}^l) = 3$.

Proof. In order to compute fault-tolerant edge metric dimension of $G_{n}^l$, we have the following cases.

Case (i). $n$ is odd. Let $\acute{W}_E = \{v_1, v_n, u_m\} \ \subset V(G_{n}^l)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $G_{n}^l$. For this, we give representations of each edge of $G_{n}^l$.

$r(u_iu_{i+1}|\acute{W}_E) = (i, i, m-i-1)$ where $1 \leq i \leq m-1,$

$r(v_{n}u_{1}|\acute{W}_E) = \ (1, 0, m-1)$ and $r(u_{1}v_{1}|\acute{W}_E) = \ (0, 1, m-1)$.

Case (ii). $n$ is even. Let $\acute{W}_E = \{v_1, v_n, u_m\} \ \subset V(G_{n}^l)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $G_{n}^l$. For this, we give representations of each edge of $G_{n}^l$.

$r(u_i u_{i+1}|\acute{W}_E) = (i, i, m-i-1)$ where $1 \leq i \leq m-1,$

$r(v_{n}u_{1}|\acute{W}_E) = \ (1, 0, m-1)$ and $r(u_{1}v_{1}|\acute{W}_E) = \ (0, 1, m-1)$.

We see that there are no two tuples having the same representations. This shows that fault-tolerant edge metric dimension of $G_{n}^l$ is less than or equal to $3$ and now we try to show that fault-tolerant edge metric dimension of $G_{n}^l$ is greater than or equal to $3$. Since by Lemma 1.4, $G_{n}^l$ is not a path so fault-tolerant edge metric dimension of $G_{n}^l$ is greater than or equal to $3$. Hence fault-tolerant edge metric dimension of $G_{n}^l$ is equal to $3$.

5.   Fault-tolerant edge metric dimension of family of kayak paddle graphs $G_{n, m}^l$

In this section, we will compute the edge metric dimension of family of kayak paddle graphs $G_{n, m}^l$. The family $G_{n, m}^l$ have $V(G_{n, m}^l) = \{u_1, u_2, \ldots, u_{m}, v_1, v_2, \ldots, v_n, w_1, w_2, \ldots, w_l \}$ and $E(G_{n, m}^l) = \{v_i v_{i+1} : 1\leq i \leq n-1\} \cup \{w_jw_{j+1}: 1\leq j \leq l-1\} \cup \{u_s u_{s+1}: 1\leq s \leq m-1 \} \cup \{v_{n}w_{1}, w_{1}v_{1}, w_l u_1, u_m w_l \}$. The family $G_{n, m}^l$ for $n = 8$, $m = 5$ and $l = 4$ is shown in Figure 5. The following theorem tells us the edge metric dimension of $G_{n, m}^l$.

Figure 5.  Kayak Paddle graph $G_{8, 5}^4$.

DownLoad: Full-Size Img PowerPoint

Theorem 5.1. ^[29] For every $n\geq 2$, $m\geq 2$ and $l\geq 4$, $edim(G_{n, m}^l) = 2$.

Now, we will compute the fault-tolerant edge metric dimension of $G_{n, m}^l$.

Theorem 5.2. For $n \geq 2$, $m \geq 2$ and $l \geq 4$, $fedim(G_{n, m}^l) = 4$.

Proof. In order to compute fault-tolerant edge metric dimension of $G_{n, m}^l$, we have the following cases.

Case (i). $n$ is odd and $m$ is even. Let $\acute{W}_E = \{v_1, v_2, u_1, u_2 \} \ \subset V(G_{n, m}^l)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $G_{n, m}^l$. For this, we give representations of each edge of $G_{n, m}^l$.

$r(w_i w_{i+1}|\acute{W}_E) = (i, i+1, l-i, l-i+1)$ where $1 \leq i \leq l-1,$

$r(v_{n}w_{1}|\acute{W}_E) = \ (1, 2, l, l+1)$, $r(w_{1}v_{1}|\acute{W}_E) = \ (0, 1, l, l+1)$, $r(w_{l}u_{1}|\acute{W}_E) = \ (l, l+1, 0, 1)$ and $r(u_{m}w_{l}|\acute{W}_E) = \ (l, l+1, 1, 2)$.

Case (ii). Both $n$ and $m$ are even. Let $\acute{W}_E = \{v_1, v_2, u_1, u_2 \} \ \subset V(G_{n, m}^l)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $G_{n, m}^l$. For this, we give representations of each edge of $G_{n, m}^l$.

$r(w_i w_{i+1}|\acute{W}_E) = (i, i+1, l-i, l-i+1)$ where $1 \leq i \leq l-1,$

$r(v_{n}w_{1}|\acute{W}_E) = \ (1, 2, l, l+1)$, $r(w_{1}v_{1}|\acute{W}_E) = \ (0, 1, l, l+1)$, $r(w_{l}u_{1}|\acute{W}_E) = \ (l, l+1, 0, 1)$ and $r(u_{m}w_{l}|\acute{W}_E) = \ (l, l+1, 1, 2)$.

Case (iii). Both $n$ and $m$ are odd. Let $\acute{W}_E = \{v_1, v_2, u_1, u_2 \} \ \subset V(G_{n, m}^l)$, we have to show that $\acute{W}_E$ is a fault-tolerant edge metric generator of $G_{n, m}^l$. For this, we give representations of each edge of $G_{n, m}^l$.

$r(w_i w_{i+1}|\acute{W}_E) = (i, i+1, l-i, l-i+1)$ where $1 \leq i \leq l-1,$

$r(v_{n}w_{1}|\acute{W}_E) = \ (1, 2, l, l+1)$, $r(w_{1}v_{1}|\acute{W}_E) = \ (0, 1, l, l+1)$, $r(w_{l}u_{1}|\acute{W}_E) = \ (l, l+1, 0, 1)$ and $r(u_{m}w_{l}|\acute{W}_E) = \ (l, l+1, 1, 2)$.

We see that there are no two tuples having the same representations. This shows that fault-tolerant edge metric dimension of $G_{n, m}^l$ is less than or equal to $4$ and now we try to show that fault-tolerant edge metric dimension of $G_{n, m}^l$ is grater than or equal to $4$.

For this purpose, we have to show that there is no fault-tolerant edge metric generator having cardinality $3$, we suppose on contrary that fault-tolerant edge metric dimension of $G_{n, m}^l$ is $3$ and let $\acute{W}_E = \{v_i, v_j, v_k \}$. Then the Table 1 shows all order pairs of edges $(e, f)$ for which $r(e|\acute{W}_E) = r(f|\acute{W}_E)$.

Table 1.  $(e, f)$ for which $r(e|\acute{W}_E) = r(f|\acute{W}_E)$.

Conditions on $i, j \text{ and } k$	(e, f)
$1 \leq i, j, k \leq n$	$(u_1 w_l, u_m w_l)$
$1 \leq i, j \leq n, 1 \leq k \leq l$	$(u_1 w_l, u_m w_l)$
$1 \leq i \leq n \text{ and } 1 \leq j, k \leq l$	$(u_1 w_l, u_m w_l)$
$1 \leq i, j, k \leq l$	$(u_1 w_l, u_m w_l)$
$1 \leq i \leq n, 1 \leq j \leq l \text{ and } 1 \leq k \leq m$
$\text{ If we take }\acute{W}_E\setminus \{v_k\}$	$(u_1 w_l, u_m w_l)$
$1 \leq i, j \leq n, \text{ and } 1 \leq k \leq m$
$\text{ If we take }\acute{W}_E\setminus \{v_k\}$	$(w_1 w_2, w_1 v_1) \text{ or } (w_1 w_2, w_1 v_n)$

---

 | Show Table

DownLoad: CSV

In all possibilities, we conclude that there is no fault-tolerant edge metric generator of $3$ vertices. Hence fault-tolerant edge metric dimension of $G_{n, m}^l$ is $4$.

6.   Conclusions

In this paper, we have computed the fault-tolerant edge metric dimension of some planar graphs path, cycle, complete, cycle with chord, tadpole and kayak paddle. It is observed that the fault-tolerant edge metric dimension of these graphs is constant and does not depend on the number of vertices. It is concluded that the fault-tolerant edge metric dimension of families of path graphs is two, the fault-tolerant edge metric dimension of families of cycle graphs, cycle with chord graphs, tadpole graphs is three and the fault-tolerant edge metric dimension of kayak paddle graphs is found to be four. Here we end with an open problem.

Open Problem

Characterize all families of graphs for which difference of fault-tolerant metric dimension and edge metric dimension is one.

Acknowledgment

Authors are thankful to the reviewers for their valuable comments.

Conflict of interest

The authors declare that no competing interests exist.