The effect of vertex and edge deletion on the edge metric dimension of graphs

Abstract

Let $G=(V(G),E(G))$ be a connected graph. A set of vertices $S\subseteq V(G)$ is an edge metric generator of G if any pair of edges in G can be distinguished by their distance to a vertex in S. The edge metric dimension edim(G) is the minimum cardinality of an edge metric generator of G. In this paper, we first give a sharp bound on $edim(G-e)-edim(G)$ for a connected graph G and any edge $e\in E(G)$. On the other hand, we show that the value of $edim(G)-edim(G-e)$ is unbounded for some graph G and some edge $e\in E(G)$. However, for a unicyclic graph H, we obtain that $edim(H)-edim(H-e)\le 1$, where e is an edge of the unique cycle in H. And this conclusion generalizes the result on the edge metric dimension of unicyclic graphs given by Knor et al. Finally, we construct graphs G and H such that both $edim(G)-edim(G-u)$ and $edim(H-v)-edim(H)$ can be arbitrarily large, where $u\in V(G)$ and $v\in V(H)$.

1 Introduction

Throughout this paper, all graphs considered are finite, simple and undirected. We follow the notation and terminology of Bondy and Murty (2008) and Diestel (2005). The concept of metric dimension was introduced independently by Harary and Melter (1976) and Slater (1975) . Let $G=(V(G),E(G))$ be a connected graph and $\overline{G}$ be its complement graph. For any pair of vertices $x,y\in V(G)$, the distance between x and y, which is denoted by $d_G(x,y)$, is the length of a shortest $x-y$ path in G. A $x-y$ path with length $d_G(x,y)$ in G is a $x-y$ geodesic. A vertex $v\in V(G)$ is said to distinguish vertices u and w if $d_G(u,v)\ne d_G(w,v)$. A vertex set $S\subseteq V(G)$ is a metric generator of G if any pair of vertices in G can be distinguished by some element of S. The minimum cardinality of a metric generator is the metric dimension of G, denoted by dim(G). In Harary and Melter (1976), Harary and Melter determined the exact values of the metric dimension for trees, grid graphs and characterized graphs with small metric dimension. In addition, they obtained an approximation algorithm for the metric dimension problem. Since then, it has been studied in various directions by numerous researchers. For more details we refer to Beaudou et al. (2018); Cáceres et al. (2007); Jiang and Polyanskii (2019); Tillquist et al. (Tillquist et al.).

Nowadays there exist some different kinds of metric generators in graphs, but there are still quite a lot of other points of view which are still not completely taken into account while describing a graph throughout these metric generators. Inspired by this, (Kelenc et al. 2018) recently proposed the concept of an edge metric generator of a graph. For any $v\in V(G)$, $e=xy\in E(G)$, the distance between them is defined as $d_G(e,v)=\min \{d_G(x,v),d_G(y,v)\}$. For two edges $e_1,e_2\in E(G)$, if $d_G(e_1,v)\ne d_G(e_2,v)$, then we say the vertex v distinguishes $e_1$ and $e_2$. A set of vertices $S\subseteq V(G)$ is an edge metric generator of G if any pair of edges can be distinguished by some element of S. The minimum cardinality of an edge metric generator of G is the edge metric dimension of G and is denoted by edim(G). Additionally, an edge metric basis of G is an edge metric generator with cardinality edim(G). In Kelenc et al. (2018), they proved that the problem of determining the edge metric dimension of a connected graph is NP-hard. In Kelenc et al. (2018); Wei et al. (2020); Zubrilina (2018); Geneson (2020); Zhu et al. (2019), the authors characterized the graphs G of order n with $edim(G)=n-1,n-2~\text {or}~2$. (Peterin and Yero 2020) investigated the edge metric dimension of the join, lexicographic and corona product of graphs. For more results and details, we refer to Beaudou et al. (2018); Zhu et al. (2019); Zubrilina (2018); Peterin and Yero (2020); Knor et al. (2021); Geneson (2020); Wei et al. (2020); Jiang and Polyanskii (2019); Cáceres et al. (2007); Kuziak and Yero (Kuziak and Yero).

For any graph G, both the exact values of dim(G) and edim(G) and their computational complexity attract the attention of researchers. In addition, researchers also focus on the relationships between dim(G), edim(G) and some other graph parameters such as diameter, zero forcing number and so on. Furthermore, researchers pay attention to the effects of different graph operations on dim(G) and edim(G). Particularly, the question as to the effect of the deletion of a vertex or of an edge on dim(G) was raised as a fundamental question in graph theory by Chartrand and (Chartrand and Zhang 2003) and further studied by Eroh et al. (2015). Inspired by their idea, we focus on the question how edim(G) will change after vertex or edge deletion. Recently, (Knor et al. 2021) and (Zubrilina 2018) showed that both $\frac{edim(G)}{dim(G)}$ and $\frac{dim(G)}{edim(G)}$ are not bounded for some certain graph G, which in a sense implies that the properties of dim(G) and edim(G) may be much different. In this paper, we characterize the difference between the edge metric dimension of the original graph and the resulting graph after vertex or edge deletion. Additionally, (Knor et al. 2021) determined the edge metric dimension of some unicyclic graphs in a certain class and our result on the edge metric dimension of any unicyclic graphs generalizes it.

This paper is organized as follows. In Sect. 2, we first prove that $edim(G-e)-edim(G)\le 2$ for any connected graph G and any edge $e\in E(G)$, and this bound is sharp for some certain graphs. Then we show that the value of $edim(G)-edim(G-e)$ is unbounded for some graph G and some edge $e\in E(G)$. However, for a unicyclic graph H and $e\in E(C)$, we conclude that $edim(H)-edim(H-e)\le 1$, where C is the unique induced cycle of H. In Sect. 3, we prove that there exist two graphs G and H such that both $edim(G)-edim(G-u)$ and $edim(H-v)-edim(H)$ can be arbitrarily large, where $u\in V(G)$ and $v\in V(H)$.

2 The effect of edge deletion on edge metric dimention of graphs

In this section, we focus on how the edge metric dimension of a graph changes upon deletion of an edge. Before giving our main results, we need the following definitions. Let $T=(V(T),E(T))$ be a tree and $v\in V(T)$. Define the equivalence relation $R_v$ in the following way: for every two edges $e,f\in E(T)$, $eR_vf$ if and only if there is a path in T including both e and f but does not have v as an internal vertex. We call the subgraphs induced by the edges of the equivalence classes of E(T) the bridges of T relative to v. Furthermore, if a bridge at v in T is a path, then the bridge is a leg at v and we denote the number of legs at v in T by $\ell _{T}(v)$.

Proposition 2.1

Kelenc et al. (2018) Let $T=(V(T),E(T))$ be a tree. If T is not a path, then $edim(T)=\sum \limits _{\begin{array}{c} v\in V(T)\\ \ell _{T}(v)>1 \end{array}}(\ell _{T}(v)-1)$.

Now our first result can be stated as follows.

Theorem 2.2

For any graph G and any edge $e\in E(G)$, $edim(G-e)-edim(G)\le 2$. Moreover, this bound is sharp for certain graphs.

Proof

Note that $edim(G)=edim(G_1)+\dots +edim(G_m)$, where $G_1,\dots ,G_m$ are all the connected components of G. Next we assume that G is connected. Let S be an edge metric basis of G and $e=uv$. If S is also an edge metric generator of $G-e$, then $edim(G-e)\le edim(G)$. Otherwise, set $S'=S\cup \{u,v\}$ and we will show that $S'$ is an edge metric generator of $G-e$.

If $G-e$ has two components, denoted by $G_1$ and $G_2$, then $edim(G-e)=edim(G_1)+edim(G_2)$. Without loss of generality, we may assume that $u\in V(G_1)$ and $v\in V(G_2)$. For any pair of edges $e_1,e_2\in E(G_1)$, if there exists $w\in V(G_2)\cap S$ such that $d_G(e_1,w)\ne d_G(e_2,w)$, then $d_G(e_1,u)\ne d_G(e_2,u)$ since $d_G(e_1,w)=d_G(e_1,u)+d_G(u,w)$ and $d_G(e_2,w)=d_G(e_2,u)+d_G(u,w)$. That is to say, $d_{G_1}(e_1,u)\ne d_{G_1}(e_2,u)$. This implies that $edim(G_1)\le |(S\cap V(G_1))\cup \{u\}|$. With similar analysis, we can obtain that $edim(G_2)\le |(S\cap V(G_2))\cup \{v\}|$. Therefore $edim(G-e)\le |S'|\le edim(G)+2$.

Now we suppose that $G-e$ is connected. Take any pair of edges $e_1=ab,e_2=xy\in E(G-e)$ that are unable to be distinguished by any element of S. Since S is an edge metric generator of G but not of $G-e$, there exists $z\in S$ such that $d_G(e_1,z)\ne d_G(e_2,z)$ and $d_{G-e}(e_1,z)=d_{G-e}(e_2,z)$. We will complete the proof in the following two cases.

Case I For one of the edges $e_1$ and $e_2$, say $e_2$ , the distance to z is not changed after removing the edge e. That means $d_{G-e}(e_2,z)=d_G(e_2,z)$ and $d_{G-e}(e_1,z)>d_G(e_1,z)$. Thus $d_G(e_2,z)>d_G(e_1,z)$. We may assume that $d_G(e_1,z)=d_G(a,z)$ and $d_G(e_2,z)=d_G(x,z)$. It follows that $d_G(x,z)>d_G(a,z)$.

Since $d_{G-e}(e_1,z)>d_G(e_1,z)=d_G(a,z)$, then $d_{G-e}(a,z)>d_G(a,z)$. This implies that the edge e lies on every $z-a$ geodesic in G. Notice that if a geodesic in G from z to a traverses the edge e in the order u, v, then each geodesic in G from z to a traverses e in the order u, v. Without loss of generality, we may assume that every geodesic in G from z to a traverses the edge e in the order u, v. Thus we have $d_G(z,a)=d_G(z,v)+d_G(v,a)$. Now we will show that $e_1,e_2$ can be distinguished by v in $G-e$.

First we show that $d_{G-e}(e_1,v)<d_{G-e}(v,x)$. Since $d_G(z,v)+d_G(v,x)\ge d_G(z,x)>d_G(z,a)=d_G(z,v)+d_G(v,a)$, that is to say, $d_G(v,x)>d_G(v,a)$. It follows that $d_{G-e}(v,x)\ge d_G(v,x)>d_G(v,a)=d_{G-e}(v,a)$. If $d_{G-e}(e_1,v)=d_{G-e}(v,a)$, then we have $d_{G-e}(e_1,v)<d_{G-e}(v,x)$. If $d_{G-e}(e_1,v)<d_{G-e}(v,a)$, then $d_{G-e}(v,a)>d_{G-e}(v,b)$ and $d_G(z,v)+d_{G-e}(v,a)>d_G(z,v)+d_{G-e}(v,b)$. Since $d_{G-e}(v,a)=d_{G}(v,a)$ and $d_{G-e}(v,b)\ge d_{G}(v,b)$, $d_G(z,a)>d_G(z,v)+d_{G}(v,b)\ge d_G(z,b)$, which contradicts to the assumption that $d_G(z,a)\le d_G(z,b)$.

Now we prove $d_{G-e}(e_1,v)<d_{G-e}(v,y)$, i.e., $d_{G-e}(v,a)<d_{G-e}(v,y)$. Suppose that $d_{G-e}(v,a)\ge d_{G-e}(v,y)$. We can get $d_G(z,v)+d_{G-e}(v,a)\ge d_G(z,v)+d_{G-e}(v,y)$. Since $d_{G-e}(v,a)=d_{G}(v,a)$ and $d_{G-e}(v,y)\ge d_{G}(v,y)$, we have $d_G(z,v)+d_{G}(v,a)\ge d_G(z,v)+d_{G}(v,y)\ge d_G(z,y)\ge d_G(z,x)$. That is to say, $d_G(z,a)\ge d_G(z,x)$, which contradicts to $d_G(z,a)<d_G(z,x)$. As a result, $d_{G-e}(v,a)<d_{G-e}(v,y)$ and it follows that $d_{G-e}(e_1,v)<d_{G-e}(v,y)$. Therefore, $d_{G-e}(e_1,v)$ $<d_{G-e}(e_2,v)$ since $d_{G-e}(e_2,v)=\min \{d_{G-e}(v,x),d_{G-e}(v,y)\}$. This implies that $e_1,e_2$ can be distinguished by v. Thus $S'=S\cup \{u,v\}$ is an edge metric generator of $G-e$ and then $edim(G-e)\le edim(G)+2$.

Case II For both $e_1$ and $e_2$, the distances to z are increased after removing the edge e, that is to say, $d_{G-e}(e_1,z)>d_G(e_1,z)$ and $d_{G-e}(e_2,z)>d_G(e_2,z)$. Without loss of generality, we may assume that $d_G(e_1,z)=d_G(z,a)$ and $d_G(e_2,z)=d_G(z,x)$. It follows that $d_{G-e}(z,a)>d_{G}(z,a)$ and $d_{G-e}(z,x)>d_{G}(z,x)$. This implies that the edge e lies on every $z-a$ and every $z-x$ geodesic in G. Here we may assume that every geodesic in G from z to a traverses the edge e in the order u, v. Thus we know that every geodesic in G from z to x traverses the edge e also in the order u, v, since otherwise we can find a shorter path than its geodesic from z to x. As a result, $d_G(z,v)+d_G(v,a)=d_G(z,a)=d_G(e_1,z)$ and $d_G(z,v)+d_G(v,x)=d_G(z,x)=d_G(e_2,z)$.

Without loss of generality, we may assume that $d_G(e_1,z)>d_G(e_2,z)$ and hence $d_G(v,a)$ $>d_G(v,x)$. We claim that the vertex v distinguishes the edges $e_1$ and $e_2$. Indeed, since there exist $v-a$ and $v-x$ geodesic in G that does not contain the edge e, $d_{G-e}(v,a)=d_G(v,a)$ and $d_{G-e}(v,x)=d_G(v,x)$. Therefore we have $d_{G-e}(v,a)>d_{G-e}(v,x)$. On the other hand, $d_G(z,v)+d_G(v,b)\ge d_G(z,b)\ge d_G(z,a)=d_G(z,v)+d_G(v,a)$, that is to say, $d_G(v,b)\ge d_G(v,a)$. It follows that $d_{G-e}(v,b)\ge d_{G}(v,b)\ge d_G(v,a)=d_{G-e}(v,a)>d_{G-e}(v,x)$. So we have $d_{G-e}(e_1,v)>d_{G-e}(v,x)\ge d_{G-e}(e_2,v)$, which implies that the edges $e_1$, $e_2$ can be distinguished by v in $G-e$. Therefore $S'=S\cup \{u,v\}$ is an edge metric generator of $G-e$ and thus $edim(G-e)\le edim(G)+2$, as desired. $\square$

Fig. 1

The graph $G_{2k+1}^{p,q,r}$

Finally, we show the sharpness of the bound by proving that $edim(G_{2k+1}^{p,q,r}-e)=edim(G_{2k+1}^{p,q,r})+2$, where the graph $G_{2k+1}^{p,q,r}$ is depicted in Figure 1. Let $C_{2k+1}=u_1u_2\dots u_{2k+1}$ be an odd cycle of length $2k+1$, where $k\ge 3$. Attach p, q, r pendant vertices to $u_2,u_k,u_{2k}$ respectively, where $p,q,r\ge 2$. Denote the new graph as $G_{2k+1}^{p,q,r}$. It is easy to verify that $S_1=\{v_2,\dots ,v_p,w_2,\dots ,w_q,x_2,\dots ,x_r\}$ is an edge metric basis of $G_{2k+1}^{p,q,r}$ and thus $edim(G_{2k+1}^{p,q,r})=p+q+r-3$. And by Proposition 2.1, we have $edim(G_{2k+1}^{p,q,r}-e)=(\ell _{G_{2k+1}^{p,q,r}-e}(u_2)-1) +(\ell _{G_{2k+1}^{p,q,r}-e}(u_{k})-1)+(\ell _{G_{2k+1}^{p,q,r}-e}(u_{2k})-1) =p+q+r-1.$ So we arrive at $edim(G_{2k+1}^{p,q,r}-e)-edim(G_{2k+1}^{p,q,r})=2$ and thus we complete the proof.

Let k be a positive integer. Let $E_1,E_2,\dots ,E_k$ be cycles of length 9 and $S_1,S_2,\dots ,S_k$ be stars with center vertices $g_1,g_2,\dots ,g_k$ and pendent vertex sets $\{h_1,c_1,d_1\},\{h_2,c_2,d_2\}, \dots ,\{h_k,c_k,d_k\}$. Let $G_k=(V(G_k),E(G_k))$, depicted in Figure 2, where $V(G_k)=V(E_1)\cup \dots \cup V(E_k)\cup V(S_1)\cup \dots \cup V(S_k)\cup \{w_1,\dots ,w_k\}\cup \{A,B\}$ and $E(G_k)=E(E_1)\cup \dots \cup E(E_k)\cup E(S_1)\cup \dots \cup E(S_k)\cup \{e,u_iA,c_iw_i,d_iw_i,w_iB,v_ih_i:i\in [k]\}$.

Fig. 2

The graphs $G_k$ and $G_k-e$

Theorem 2.3

Let $G_k$ be the graph depicted in Figure 2. For any positive integer k, $edim(G_k)-edim(G_k-e)=k-1$.

Proof

Let S be an edge metric generator of $G_k$ and $S'$ be an edge metric generator of $G_k-e$. Note that, for $1\le i\le k$, $|S\cap \{c_i,d_i\}|\ge 1$ since $g_ic_i,g_id_i$ are unable to be distinguished by any element of $V(G)\setminus \{c_i,d_i\}$. Similarly, $|S'\cap \{c_i,d_i\}|\ge 1$. Without loss of generality, we may assume that $\{c_1,c_2,\dots ,c_k\}\subseteq S\cap S'$. Set $S_0=\{c_1,c_2,\dots ,c_k\}$.

First we will show that $edim(G_k)=2k$. For $1\le i,j\le k$, $d_{G_k}(c_j,u_ia_i)=d_{G_k}(c_j,u_ib_i)=4$ and then $u_ia_i,u_ib_i$ are unable to be distinguished by any element of $S_0$. Simultaneously, $d_{G_k}(d_j,u_ia_i)=d_{G_k}(d_j,u_ib_i)=4$, $d_{G_k}(w_j,u_ia_i)=d_{G_k}(w_j,u_ib_i)=3$, $d_{G_k}(A,u_ia_i)=d_{G_k}(A,u_ib_i)=1$, $d_{G_k}(B,u_ia_i)=d_{G_k}(B,u_ib_i)=2$ and $d_{G_k}(g_j,u_ia_i)=d_{G_k}(g_j,u_ib_i)=5$. If there exists some i such that $(V(E_i)\cup \{h_i\})\cap S=\emptyset$, then $u_ia_i,u_ib_i$ are unable to be distinguished by any element of S, which contradicts that S is an edge metric generator of $G_k$. Therefore, we have $|(V(E_i)\cup \{h_i\})\cap S|\ge 1$ for $1\le i\le k$, which implies that $edim(G_k)\ge 2k$. On the other hand, $S_1=S_0\cup \{a_1,a_2,\dots ,a_k\}$ is an edge metric generator of $G_k$. Indeed, for any edges $e_1=mn,e_2=st\in E(G_k)$ such that $\{m,n,s,t\}\cap S_1\ne \emptyset$ and $\{m,n\}\cap \{s,t\}=\emptyset$, then $e_1,e_2$ can be distinguished by any element of $\{m,n,s,t\}\cap S_1$; for any edges $e_1=mn,e_2=mt\in E(G_k)$ such that $n\in \{m,n,t\}\cap S_1$ or $t\in \{m,n,t\}\cap S_1$, then $e_1,e_2$ can be distinguished by n or t; if $e_1=a_ip_i$, $e_2=a_iu_i\ (1\le i\le k)$, then $d_{G_k}(c_i,e_1)=5$ and $d_{G_k}(c_i,e_2)=4$; if $e_1=c_ig_i$, $e_2=c_iw_i\ (1\le i\le k)$, then $d_{G_k}(a_i,e_1)=5$ and $d_{G_k}(a_i,e_2)=4$. Now we focus on the edges whose end vertices are both in $V(G)\setminus S_1$. For edges $e_1=Bw_i$, $e_2=Bw_j\ (1\le i\ne j\le k)$, we have $d_{G_k}(c_i,e_1)=1$ and $d_{G_k}(c_i,e_2)=2$. For edges $e_1=Au_i$, $e_2=Au_j\ (1\le i\ne j\le k)$, we have $d_{G_k}(a_i,e_1)=1$ and $d_{G_k}(a_i,e_2)=2$. And if $e_1=e=AB$, $e_2=v_1h_1$, then $d_{G_k}(a_1,e_1)=2$ and $d_{G_k}(a_1,e_2)=3$. Next we will check that the edges which have the same distance to $a_i$ can be distinguished by $c_i$ or $a_j$, and also the edges which have the same distance to $c_i$ can be distinguished by $a_i$ or $c_j$, where $1\le i\ne j\le k$. Indeed, if $e_1=p_1x_1$, $e_2=u_1A$, $e_3=u_1b_1$, then $d_{G_k}(c_1,e_1)=4$, $d_{G_k}(c_1,e_2)=3$, $d_{G_k}(c_1,e_3)=4$, $d_{G_k}(a_2,e_1)=5$ and $d_{G_k}(a_2,e_3)=3$. For edges $e_1=x_1v_1$, $e_2=b_1q_1$, $e_3=e=AB$, we have $d_{G_k}(c_1,e_1)=3$, $d_{G_k}(c_1,e_2)=5$ and $d_{G_k}(c_1,e_3)=2$. For edges $e_1=v_1h_1$, $e_2=v_1y_1$, $e_3=q_1r_1$, we have $d_{G_k}(c_1,e_1)=2$, $d_{G_k}(c_1,e_2)=3$ and $d_{G_k}(c_1,e_3)=5$. For edges $e_1=g_1h_1$, $e_2=g_1d_1$, $e_3=d_1w_1$ and $e_4=Bw_1$, we have $d_{G_k}(c_2,e_1)=5$, $d_{G_k}(c_2,e_2)=4$, $d_{G_k}(c_2,e_3)=3$ and $d_{G_k}(c_2,e_4)=2$. And for other pair of edges, one can easily check that they can also be distinguished by some element of $S_1$, which implies that $S_1$ is indeed an edge metric generator of $G_k$. This means $edim(G_k)\le 2k$ and hence $edim(G_k)=2k$.

Next we will show that $edim(G_k-e)=k+1$. For $1\le i\ne j\le k$, $d_{G_k-e}(c_j,x_iv_i)=d_{G_k-e}(c_j,y_iv_i)=7$, $d_{G_k-e}(c_i,x_iv_i)=d_{G_k-e}(c_i,y_iv_i)=3$ and then $x_iv_i,y_iv_i$ are unable to be distinguished by any element of $S_0$. It follows that $edim(G_k-e)>|S_0|=k$, i.e., $edim(G_k-e)\ge k+1$. Set $S_2=S_0\cup \{A\}$. One can check that $S_2$ is an edge metric generator of $G_k-e$, which implies that $edim(G_k-e)\le k+1$ and thus $edim(G_k-e)=k+1$. Therefore, we have $edim(G_k)-edim(G_k-e)=k-1$ and the theorem holds. $\square$

In the rest of this section, we pay attention to the upper bound on $edim(G)-edim(G-e)$ for a unicyclic graph G.

Lemma 2.4

Let $P_n$ be a path of order n. If e is an edge of $\overline{P_n}$, then $edim(P_n+e)=edim(P_n)+1=2$.

Fig. 3

The graphs $P_n+e$.

Proof

It is easy to verify that the graph $P_n+e$ has one of the following three types (see Fig. 3).

If $P_n+e$ has type (I), then $P_n+e\cong C_n$ and so $edim(P_n+e)=2$.

When $P_n+e$ has type (II), we set $S=\{x_1,y_1\}$. We claim that S is an edge metric generator of $P_n+e$. Indeed, for any pair of edges $f_1,f_2\in P_n+e$, it is impossible that $d(f_1,x_1)=d(f_2,x_1)$ and $d(f_1,y_1)=d(f_2,y_1)$ hold simultaneously. Thus $edim(P_n+e)\le 2$. On the other side, any single vertex of $P_n+e$ is unable to distinguish all pairs of edges, which implies that $edim(P_n+e)\ge 2$. Consequently, $edim(P_n+e)=2$.

Finally we consider the case that $P_n+e$ has type (III). Set $Q=\{x_2,y_2\}$. We will show that Q is an edge metric generator of $P_n+e$. One can check that for any pair of edges $g_1,g_2\in P_n+e$, the equalities $d(g_1,x_2)=d(g_2,x_2)$ and $d(g_1,y_2)=d(g_2,y_2)$ are unable to hold at the same time. So we have $edim(P_n+e)\le 2$. Simultaneously, $edim(P_n+e)\ge 2$ since any single vertex is not an edge metric generator of $P_n+e$. As a result, $edim(P_n+e)=2$. $\square$

Theorem 2.5

Let T be a tree. If e is an edge of $\overline{T}$, then $edim(T+e)-edim(T)\le 1$.

Proof

By Lemma 2.4, we know that $edim(T+e)=edim(T)+1$ when T is a path. So we consider that T is a tree which is not a path. Obviously, $edim(T)\ge 2$. Denote the vertices of the unique cycle $C_k$ in $T+e$ as $u_1,u_2,\dots ,u_k$ and the component of $T+e-E(C_k)$ which contains $u_i$ as $T_i$. Let S be an edge metric basis of T and set $S_i=S\cap V(T_i)$ for $1\le i\le k$. Without loss of generality, we may assume $S_1\ne \emptyset$.

If $S_i=\emptyset$ for $2\le i\le k$, then $T-T_1$ is a path and thus $S\cup \{u_2\}$ or $S\cup \{u_k\}$ is an edge metric generator of $T+e$. Therefore, we have $edim(T+e)\le edim(T)+1$. On the other hand, if there exists some $i~(2\le i\le k)$ such that $S_i\ne \emptyset$, then we will complete the proof in two cases. If there exist $i,j\ (1\le i<j\le k)$ such that $S_i\ne \emptyset$, $S_j\ne \emptyset$ and $d_{T+e}(u_i,u_j)=\lfloor \frac{k}{2}\rfloor$, then take $x_0\in V(C_k)\setminus \{u_i,u_j\}$ and set $S'=S\cup \{x_0\}$. Otherwise, we will take $x_0=u_{\lfloor \frac{k}{2}\rfloor +1}$ and set $S'=S\cup \{x_0\}$.

Next we will show that $S'$ is an edge metric generator of $T+e$. Since the analyses of the two cases are similar, then we pay attention to the case that there exist $i,j\ (1\le i<j\le k)$ such that $S_i\ne \emptyset$, $S_j\ne \emptyset$ and $d_{T+e}(u_i,u_j)=\lfloor \frac{k}{2}\rfloor$. Set $S_0=\{x_0,x_i,x_j\}$, where $x_i\in S_i$, $x_j\in S_j$ and thus $S_0\subseteq S'$.

For any pair of edges $e_1,e_2\in T_{\ell }(1\le \ell \le k)$, there exists some $z\in S$ such that $d_T(e_1,z)\ne d_T(e_2,z)$. If $z\in V(T_{\ell })$, then $d_{T+e}(e_1,z)=d_T(e_1,z)$, $d_{T+e}(e_2,z)=d_T(e_2,z)$ and thus $d_{T+e}(e_1,z)\ne d_{T+e}(e_2,z)$. If $z\in V(C_k)$, then $d_{T+e}(e_1,z)=d_{T+e}(e_1,u_{\ell })+d_{T+e}(u_{\ell },z)$ and $d_{T+e}(e_2,z)=d_{T+e}(e_2,u_{\ell })+d_{T+e}(u_{\ell },z)$. Since $d_T(e_1,z)=d_{T}(e_1,u_{\ell })+d_{T}(u_{\ell },z)$, $d_T(e_2,z)=d_{T}(e_2,u_{\ell })+d_{T}(u_{\ell },z)$ and $d_{T}(e_1,u_{\ell })=d_{T+e}(e_1,u_{\ell })$, $d_{T}(e_2,u_{\ell })=d_{T+e}(e_2,u_{\ell })$, we come to the conclusion that $d_{T+e}(e_1,z)\ne d_{T+e}(e_2,z)$. For the case $z\in V(T_{\ell '})(\ell '\ne \ell )$, we have $d_{T+e}(e_1,z)=d_{T+e}(e_1,u_{\ell })+d_{T+e}(u_{\ell },u_{\ell '})+d_{T+e}(u_{\ell '},z)$ and $d_{T+e}(e_2,z)=d_{T+e}(e_2,u_{\ell })+d_{T+e}(u_{\ell },u_{\ell '})+d_{T+e}(u_{\ell '},z)$. Note that $d_T(e_1,z)=d_{T}(e_1,u_{\ell })+d_{T}(u_{\ell },u_{\ell '})+d_{T}(u_{\ell '},z)$, $d_T(e_2,z)=d_{T}(e_2,u_{\ell })+d_{T}(u_{\ell },u_{\ell '})+d_{T}(u_{\ell '},z)$ and $d_{T}(e_1,u_{\ell })=d_{T+e}(e_1,u_{\ell })$, $d_{T}(e_2,u_{\ell })=d_{T+e}(e_2,u_{\ell })$. It follows that $d_{T+e}(e_1,z)$ $\ne d_{T+e}(e_2,z)$.

Consider any two edges $f_1\in T_{\ell },f_2\in T_{\ell '}\ (1\le \ell \ne \ell '\le k)$. We denote the three segments of the cycle $C_k$ as $x_0C_ku_i$, $u_iC_ku_j$ and $u_jC_kx_0$. If $\{u_{\ell },u_{\ell '}\}\subseteq x_0C_ku_i$, without loss of generality, we may assume that $d_{T+e}(x_0,u_{\ell })<d_{T+e}(x_0,u_{\ell '})$ and thus $d_{T+e}(u_i,u_{\ell })>d_{T+e}(u_i,u_{\ell '})$. If further $d_{T+e}(f_1,x_0)=d_{T+e}(f_2,x_0)$, then $d_{T+e}(f_1,u_{\ell })>d_{T+e}(f_2,u_{\ell '})$. Since $d_{T+e}(f_1,x_i)=d_{T+e}(f_1,u_{\ell })+d_{T+e}(u_{\ell },u_i)+d_{T+e}(u_i,x_i)$ and $d_{T+e}(f_2,x_i)=d_{T+e}(f_2,u_{\ell '})+d_{T+e}(u_{\ell '},u_i)+d_{T+e}(u_i,x_i)$, we have $d_{T+e}(f_1,x_i)>d_{T+e}(f_2,x_i)$. Similarly, we can obtain that $f_1,f_2$ can be distinguished by some element of $S_0$ for $\{u_{\ell },u_{\ell '}\}\subseteq u_iC_ku_j$ or $\{u_{\ell },u_{\ell '}\}\subseteq u_jC_kx_0$. Now we consider the case $u_{\ell }\in x_0C_ku_i$ and $u_{\ell '}\in u_iC_ku_j$. If $d_{T+e}(f_1,u_{\ell })=d_{T+e}(f_2,u_{\ell '})$ and $d_{T+e}(u_{\ell },x_0)\ne d_{T+e}(u_{\ell '},x_0)$, then we have $d_{T+e}(f_1,x_0)\ne d_{T+e}(f_2,x_0)$ since $d_{T+e}(f_1,x_0)=d_{T+e}(f_1,u_{\ell })+d_{T+e}(u_{\ell },x_0)$, $d_{T+e}(f_2,x_0)=d_{T+e}(f_2,u_{\ell '})+d_{T+e}(u_{\ell '},x_0)$. For the case that $d_{T+e}(f_1,u_{\ell })=d_{T+e}(f_2,u_{\ell '})$ and $d_{T+e}(x_0,u_{\ell })=d_{T+e}(x_0,u_{\ell '})$, we have $d_{T+e}(f_1,x_j)>d_{T+e}(f_2,x_j)$ since $d_{T+e}(f_1,x_j)=d_{T+e}(f_1,u_{\ell })+d_{T+e}(u_{\ell },u_j)+d_{T+e}(u_j,x_j)$, $d_{T+e}(f_2,x_j)=d_{T+e}(f_2,u_{\ell '})+d_{T+e}(u_{\ell '},u_j)+d_{T+e}(u_j,x_j)$ and $d_{T+e}(u_{\ell },u_j)=d_{T+e}(u_{\ell },x_0)+d_{T+e}(x_0,x_j)>d_{T+e}(u_{\ell '},u_j)$. With similar analysis, for the cases $d_{T+e}(f_1,u_{\ell })>d_{T+e}(f_2,u_{\ell '})$, $d_{T+e}(u_i,u_{\ell })=d_{T+e}(u_i,u_{\ell '})$ and $d_{T+e}(f_1,u_{\ell })>d_{T+e}(f_2,u_{\ell '})$, $d_{T+e}(u_i,u_{\ell })>d_{T+e}(u_i,u_{\ell '})$, we have $d_{T+e}(f_1,x_i)>d_{T+e}(f_2,x_i)$. Meanwhile, if $d_{T+e}(f_1,u_{\ell })>d_{T+e}(f_2,u_{\ell '})$ and also $d_{T+e}(u_i,u_{\ell })<d_{T+e}(u_i,u_{\ell '})$, then $d_{T+e}(u_j,u_{\ell })>d_{T+e}(u_j,u_{\ell '})$ and thus $d_{T+e}(f_1,x_j)>d_{T+e}(f_2,x_j)$. Furthermore, we can similarly obtain that $f_1,f_2$ can be distinguished by some element of $S_0$ when $d_{T+e}(f_1,u_{\ell })<d_{T+e}(f_2,u_{\ell '})$. For the cases $u_{\ell }\in u_iC_ku_j$ and $u_{\ell '}\in u_jC_kx_0$ or $u_{\ell }\in u_jC_kx_0$ and $u_{\ell '}\in x_0C_ku_i$, the analysis is similar to that of $u_{\ell }\in x_0C_ku_i$ and $u_{\ell '}\in u_iC_ku_j$, so we omit the details here.

For any pair of edges $g_1,g_2$, if $g_1,g_2\in C_k$, then it is easy to check that $g_1,g_2$ can be distinguished by some element of $S_0$ and so we consider the case $g_1\in C_k$, $g_2\in T_{\ell }\ (1\le \ell \le k)$. If $g_1$ lies on one shortest path from w to $u_{\ell }$ in $T+e$, where $w\in S_0$, then $d_{T+e}(g_1,w)<d_{T+e}(g_2,w)$. Otherwise, we claim that $g_1,g_2$ can be distinguished by some element of $S_0$. Here we take the case $g_1\in u_jC_kx_0$ and $u_{\ell }\in u_iC_ku_j$ for example, and the other cases are similar. If $d_{T+e}(g_1,x_j)\ne d_{T+e}(g_2,x_j)$, then we finish the proof. Otherwise, $d_{T+e}(g_1,u_j)=d_{T+e}(g_2,u_j)=d_{T+e}(g_2,u_{\ell }) +d_{T+e}(u_{\ell },u_j)$ since $d_{T+e}(g_1,x_j)=d_{T+e}(g_1,u_j)+d_{T+e}(u_j,x_j)$ and $d_{T+e}(g_2,x_j)=d_{T+e}(g_2,u_j)+d_{T+e}(u_j,x_j)$. If $d_{T+e}(g_2,u_{\ell })\ne 0$, then we have $d_{T+e}(g_1,u_j)>d_{T+e}(u_{\ell },u_j)$ and thus $d_{T+e}(g_1,u_i)<d_{T+e}(u_{\ell },u_i)$. This implies that $d_{T+e}(g_1,x_i)<d_{T+e}(g_2,x_i)$. If $d_{T+e}(g_2,u_{\ell })=0$, then $d_{T+e}(g_1,u_j)=d_{T+e}(u_{\ell },u_j)$ and thus $d_{T+e}(g_1,x_0)<d_{T+e}(u_{\ell },x_0)=d_{T+e}(g_2,x_0)$. Therefore, $S'$ is an edge metric generator of $T+e$ and thus we complete the proof. $\square$

Fig. 4

The graph $T+e$.

Consequently, if G is a unicyclic graph and e is an edge on its unique cycle, then by Lemma 2.4 and Theorem 2.5, we have $edim(G)-edim(G-e)\le 1$.

In summary, we come to the following conclusion.

Theorem 2.6

There exist some graph G and some edge $e\in E(G)$ such that $edim(G)-edim(G-e)$ can be arbitrarily large. While for any unicyclic graph H, $edim(H)-edim(H-e)\le 1$, where e is an edge of the unique cycle in H.

3 The effect of vertex deletion on edge metric dimention of graphs

The join graph $G+H$ is the graph obtained from G and H by adding all possible edges between any vertex of G and any vertex of H. Obviously, the wheel graph $W_{1,n}$ is isomorphic to $C_n+K_1$ and we refer to the vertex of degree n in $W_{1,n}$ as its center vertex.

Proposition 3.1

Kelenc et al. (2018) If $W_{1,n}$ is a wheel graph, then

$$\begin{aligned} edim(W_{1,n})=\left\{ \begin{array}{crl} n &{} &{} if\ n=3,4;\\ n-1 &{} &{} if\ n\ge 5. \end{array} \right. \end{aligned}$$

Proposition 3.2

Kelenc et al. (2018) For any integer $n\ge 3$, $edim(C_{n})=2$.

From Propositions 3.1 and 3.2, we can obtain the following observation immediately.

Observation 3.3

Let $k\ge 2$ be an positive integer. If $v_0$ is the center vertex of the wheel graph $W_{1,k+3}$, then $edim(W_{1,k+3})-edim(W_{1,k+3}-v_0)=k$.

Let $k\ge 8$, $t\ge 24$ be positive integers and $P=u_1u_2\dots u_k$ be a path. For $1\le i\le k$, attach $t_i~(\ge 3)$ pendant vertices $v^i_1,v^i_2,\dots ,v^i_{t_i}$ to $u_i$ and denote the resulting graph by $H_{k,t}$, where $t=\sum \limits _{i=1}^{k}t_i$. Let $G_{k,t}$ be the graph with vertex set $V(H_{k,t})\cup \{v\}$ and edge set $E(H_{k,t})\cup \{vv^1_1,vv^2_1,\dots ,vv^k_1\}$ (see Fig. 5).

Fig. 5

The graph $G_{k,t}$.

Lemma 3.4

Let $k\ge 8$, $t\ge 24$ be positive integers. If $v\in V(G_{k,t})$ is the vertex as depicted in Figure 5, then $edim(G_{k,t}-v)-edim(G_{k,t})=k$.

Proof

Since $G_{k,t}-v$ is a tree, we have $edim(G_{k,t}-v)=t-k$ by Proposition 2.1. Next we will show that $edim(G_{k,t})=t-2k$, which implies that $edim(G_{k,t}-v)-edim(G_{k,t})=k$. Set $S=\{v^1_3,\dots ,v^1_{t_1}\}\cup \{v^2_3,\dots ,v^2_{t_2}\}\cup \dots \cup \{v^k_3,\dots ,v^k_{t_k}\}$. For any pair of edges $e=x_1y_1,f=x_2y_2\in E(G_{k,t})$, if $\{x_1,x_2,y_1,y_2\}\cap S\ne \emptyset$, then e, f can be distinguished by any element of $S\cap \{x_1,x_2,y_1,y_2\}$. Hence we can assume that $e,f\in \{u_iu_{i+1},vv^i_1,u_iv^i_1,u_iv^i_2:1\le i\le k\}$.

If $e=u_iu_{i+1},f=u_ju_{j+1}\ (i<j)$, then $d(e,v^i_3)=1$, $d(f,v^i_3)\ge 2$ and e, f can be distinguished by $v^i_3\in S$. If $e=vv^i_1,f=vv^j_1$, then $d(e,v^i_3)=2$, $d(f,v^i_3)=3$ and e, f can be distinguished by $v^i_3\in S$. For $e=u_iv^i_1,f=u_jv^j_1$, we have that e, f can be distinguished by $v^i_3\in S$ since $d(e,v^i_3)=1$ and $d(f,v^i_3)\ge 2$. And for $e=u_iv^i_2,f=u_jv^j_2$, one can easily verify that $d(e,v^i_3)=1$, $d(f,v^i_3)\ge 2$ and then e, f can be distinguished by $v^i_3\in S$.

For the case that $e=u_iu_{i+1},f=vv^i_1$, we have $d(e,v^i_3)=1$, $d(f,v^i_3)=2$ and e, f can be distinguished by $v^i_3\in S$. If $e=u_iu_{i+1},f=vv^j_1\ (i\ne j)$, then $d(e,v^i_3)=1$, $d(f,v^i_3)=3$ and e, f can be distinguished by $v^i_3\in S$. If $e=u_iu_{i+1},f=u_iv^i_1$ or $e=u_iu_{i+1},f=u_iv^i_2$, then $d(e,v^{i+1}_3)=1$, $d(f,v^{i+1}_3)=2$ and e, f can be distinguished by $v^{i+1}_3\in S$. For $e=u_iu_{i+1},f=u_jv^j_1(i\ne j)$ or $e=u_iu_{i+1},f=u_jv^j_2(i\ne j)$, we have that e, f can be distinguished by $v^i_3\in S$ since $d(e,v^i_3)=1$ and $d(f,v^i_3)\ge 2$.

Next we come to the case that $e=vv^i_1,f=u_iv^i_1$ or $e=vv^i_1,f=u_iv^i_2$. Obviously, $d(e,v^i_3)=2$, $d(f,v^i_3)=1$ and thus e, f can be distinguished by $v^i_3\in S$. If $e=vv^i_1,f=u_jv^j_1(i\ne j)$ or $e=vv^i_1,f=u_jv^j_2(i\ne j)$, then $d(e,v^j_3)=3$, $d(f,v^j_3)=1$ and e, f can be distinguished by $v^j_3\in S$. For $e=u_iv^i_1,f=u_iv^i_2$, we have $d(e,v^{i+4}_3)=4$, $d(f,v^{i+4}_3)=5$ for $i\le k-4$ and $d(e,v^{i-4}_3)=4$, $d(f,v^{i-4}_3)=5$ for $k-3\le i\le k$ and thus e, f can be distinguished by $v^{i+4}_3\in S$ (or $v^{i-4}_3\in S$). Finally, for $e=u_iv^i_1,f=u_jv^j_2(i\ne j)$, we obtain that e, f can be distinguished by $v^i_3\in S$ since $d(e,v^i_3)=1$, $d(f,v^i_3)\ge 2$.

Therefore, S is an edge metric generator of $G_{k,t}$ and thus $edim(G_{k,t})\le t-2k$. On the other hand, let W be an arbitrary edge metric generator of $G_{k,t}$. If there exist some $i\ (1\le i\le k)$ such that $|W\cap \{v^i_2,\dots ,v^i_{t_i}\}|<t_i-2$, then the edges $u_iv^i_a$ and $u_iv^i_b$ are unable to be distinguished by any element of W, where $v^i_a,v^i_b\in \{v^i_2,\dots ,v^i_{t_i}\}\backslash W$. We arrive at a contradiction and thus $edim(G_{k,t})\ge t-2k$. Therefore, $edim(G_{k,t})=t-2k$ and then $edim(G_{k,t}-v)-edim(G_{k,t})=k$, as desired. $\square$

From Observation 3.3 and Lemma 3.4, we arrive at the following conclusion.

Theorem 3.5

For any positive integer k, there exist graphs G and H such that both $edim(G)-edim(G-u)$ and $edim(H-v)-edim(H)$ can be at least k, where $u\in V(G)$ and $v\in V(H)$.

4 Concluding remarks

In this paper, we analyze what happens with the edge metric dimension if one edge or one vertex is deleted. For any graph G and any edge $e\in E(G)$, $edim(G-e)-edim(G)\le 2$. On the other hand, the value of $edim(G)-edim(G-e)$ is unbounded for some graph G and some edge $e\in E(G)$. However, for a unicyclic graph H, $edim(H)-edim(H-e)\le 1$, where e is an edge of the unique cycle in H. Additionally, the difference between the edge metric dimension of the original graph and the resulting graph after vertex deletion can be arbitrarily large. And as a future work, it’s interesting to think about whether it is possible to bound the corresponding difference between the edge metric dimension of the original graph and the resulting graph using the vertex degree.