1 Introduction

All graphs in this paper are finite, simple and connected. For a graph G, the vertex set and edge set are denoted by V(G) and E(G), respectively. The length of a shortest path between vertices u, v is their distance and denoted by d(u, v). For a vertex \(v\in V(G)\), N(v) is the set of all vertices in G that are adjacent to v. The maximum distance between two vertices in G is the diameter of G and denoted by \(\mathrm{diam}(G)\). A unicyclic graph is a graph with exactly one cycle. A set \(S\subseteq V(G)\) is an independent set if no two vertices in S are adjacent to each other. The notations \((v_1,v_2,\ldots , v_n)\) and \((v_1,v_2,\ldots ,v_n,v_1)\) are used for a path of order n, \(P_n\), and a cycle of order n, \(C_n\), respectively.

Two vertices u, v in a graph G are resolved by a vertex \(x\in V(G)\) if \(d(v,x)\ne d(u,x).\) A set W of vertices of the graph G is a resolving set for G if every two distinct vertices of G are resolved by some vertex of W. A resolving set for G with minimum cardinality is called a basis of G, and its cardinality is called the metric dimension of G and denoted by \(\dim (G)\).

Slater [18] introduced the concepts of resolving sets and metric dimension of graphs. He found the application of these ideas in US Sonar and Coast Guard Loran stations. Harary and Melter rediscovered these concepts in [9]. Resolving sets have several applications in diverse areas such as coin weighing problems [17], network discovery and verification [3], robot navigation [11], mastermind game [5], problems of pattern recognition and image processing [16], and combinatorial search and optimization [17]. For more results about resolving sets and metric dimension, see [2, 4, 5, 7, 10].

During the study of the metric dimension of the Cartesian product of graphs, Caceres et al. [5] defined the concept of doubly resolving sets in graphs. Two vertices u, v in a graph G are doubly resolved by \(x,y\in V(G)\) if

$$\begin{aligned} d(v,x)-d(u,x)\ne d(v,y)-d(u,y). \end{aligned}$$

A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W. Every graph with at least two vertices has a doubly resolving set. The doubly basis of the graph G is a doubly resolving set for G with minimum cardinality. The doubly resolving number of graph G, \(\psi (G)\), is the cardinality of a basis in G.

Caceres et al. [5] obtained doubly resolving number of trees, cycles and complete graphs. In [12], it was proved that the problem of finding doubly bases is NP-hard. Doubly resolving number of Prism graphs and Hamming graphs is computed in [6] and [13], respectively. For more results about doubly resolving sets in graphs, see [1, 5, 12, 14].

Caceres et al. [5] obtained an upper bound for the metric dimension of Cartesian product of graphs G and H in terms of \(\psi (H)\) and \(\dim (G)\). They also obtained a lower bound for the metric dimension of the Cartesian product of a graph G with itself in terms of \(\psi (G)\). Hence, computing doubly resolving number of graphs is useful for computing metric dimension of Cartesian product of graphs. Moreover, studying doubly resolving sets is interesting by itself. It is clear that for each graph of order at least 2, we have \(\psi (G)\ge 2\). Cáseres et al. found the following upper bound for \(\psi (G)\).

Lemma 1.1

[5] For every graph G with \(n\ge 3\) vertices, we have \(\psi (G)\le n-1\).

Also, through the following three lemmas, they found the doubly resolving number of complete graphs, paths and cycles.

Lemma 1.2

[5] For all \(n\ge 2\), we have \(\psi (K_n)=\max \{n-1,2\}\).

Lemma 1.3

[5] For each \(n\ge 2\), \(\psi (P_n)=2\).

Lemma 1.4

[5] Let \(C_n\) be a cycle of order n. Then,

$$\begin{aligned} \psi (C_n)=\left\{ \begin{array}{ll} 2 &{} \mathrm{if~}n~\mathrm{is~odd}, \\ 3 &{} \mathrm{if~}n~\mathrm{is~even}. \end{array}\right. \end{aligned}$$

Chartrand et al. in [7] proved that if G is a complete bipartite graph of order n, then \(\dim (G)=n-2\). They also obtained the following results for metric dimension of graphs.

Theorem 1.5

[7] Let f(n, d) be the least positive integer k, for which \(k + d^k\ge n\). If G is a graph of order \(n\ge 2\) and diameter d, then \(f(n,d)\le \dim (G)\le n-d\).

Theorem 1.6

[7] A graph G of order \(n\ge 2\) has metric dimension \(n-1\) if and only if G is the complete graph \(K_n\).

Motivated by these results, in this paper we investigate doubly resolving sets for graphs. In Sect. 2, some properties of doubly resolving bases of graphs are presented, an upper bound for \(\psi (G)\) in terms of diameter and order of G is obtained and the doubly resolving number of complete bipartite graphs is computed. In Sect. 3, all n-vertex graphs G with \(\psi (G)=n-1\) are determined. In Sect. 4, doubly resolving sets of unicyclic graphs are investigated and it is proved that the difference between the number of leaves and doubly resolving number of a unicyclic graph is at most 2.

2 Some results on doubly resolving sets

In this section, we present some results about doubly resolving sets of graphs. We obtain the doubly resolving number of some famous families of graphs. An important upper bound for doubly resolving number of graphs is obtained in terms of order and diameter of the graph.

By the following lemma, to check whether a given set \(W\subseteq V(G)\) is a doubly resolving set, it does not need to consider the pair of vertices that both of them are in W.

Lemma 2.1

Let S be a subset of size at least 2 of V(G). If \(x,y\in S\), then x, y are doubly resolved by \(x,y\in S\). Also, if \(a\in S\) and \(b\notin S\) are two vertices in G that are not doubly resolved by any pair of vertices in S, then for each \(s\in S\) there exists a shortest path between b and s that contains a.

Proof

Let \(x,y\in S\). Then, \(d(x,x)-d(y,x)=-d(x,y)\ne d(x,y)=d(x,y)-d(y,y).\) That is x, y are doubly resolved by x, y. Now, let \(a\in S\), \(b\in V(G)\setminus S\) and a, b are not doubly resolved by any pair of vertices in S. For each \(s\in S\), we have \(d(a,s)-d(b,s)=d(a,a)-d(b,a)\), which implies \(d(b,s)=d(b,a)+d(a,s)\). If P and Q are shortest paths between b, a and a, s, respectively, then \(P\cup Q\) is a path between b, s with length d(b, s). Therefore, \(P\cup Q\) is a shortest path between b, s that contains a. \(\square \)

Two distinct vertices u, v are said to be twins if \(N(v)\backslash \{u\}=N(u)\backslash \{v\}\). It is clear that if u, v are twin vertices in G, then for every vertex \(x\in V(G)\setminus \{u,v\}\), \(d(u,x)=d(v,x)\).

Proposition 2.2

Suppose that u, v are twins in a graph G and W is a doubly resolving set for G. Then, at least one of the vertices u and v is in W. Moreover, if \(u\in W\) and \(v\notin W\), then \((W\setminus \{u\})\cup \{v\}\) is also a doubly resolving set for G.

Proof

Let u, v be twins, W be a doubly resolving set and \(u,v\notin W\). Then, for each \(a,b\in W\),

$$\begin{aligned} d(u,a)-d(v,a)=0=d(u,b)-d(v,b). \end{aligned}$$

This contradiction implies that W must contain at least one of u or v. Now, let W be a doubly resolving set for G such that \(u\in W\) and \(v\notin W\). If \((W\setminus \{u\})\cup \{v\}\) is not a doubly resolving set for G, then there are vertices \(x,y\in V(G)\) and \(w\in W\) such that x, y are doubly resolved by u, w and are not doubly resolved by v, w. But

$$\begin{aligned} d(x,v)-d(y,v)=d(x,u)-d(y,u)\ne d(x,w)-d(y,w). \end{aligned}$$

This means \((W\setminus \{u\})\cup \{v\}\) is a doubly resolving set for G. \(\square \)

One of the well-known families of graphs is the family of complete bipartite graphs. By the next lemma, we compute the doubly resolving number of complete bipartite graphs.

Lemma 2.3

Let \(K_{r,s}\) be a complete bipartite graph of order \(n\ge 3\) and \(r\le s\). Then,

$$\begin{aligned} \psi (K_{r,s})=\left\{ \begin{array}{ll} n-1 &{} ~~~~ \mathrm{if~}r\le 2, \\ n-2 &{} ~~~~ \mathrm{if~}r>2. \end{array}\right. \end{aligned}$$

Proof

Suppose that \(K_{r,s}\) be a complete bipartite graph with partite sets X, Y such that \(|X|=r\) and \(|Y|=s\). Since \(n\ge 3\) and \(r\le s\), we have \(s\ge 2\). Let W be a doubly resolving set for \(K_{r,s}\). One of the following three cases can be arisen.

Case 1. \(r=1\). If \(s=2\), then by Lemma 1.3, \(\psi (K_{1,2})=2=n-1\). Let \(s\ge 3\). Then, all vertices in Y are twins and by Proposition 2.2, \(|W\cap Y|\ge s-1\). Hence, \(|W|\ge n-2\). If \(|W|= n-2\), then there exists a vertex \(y_0\in Y\setminus W\). Now, for each \(w\in W\), \(d(y_0,w)-d(x_0,w)=1\), where \(X=\{x_0\}\). That means W is not a doubly resolving set. This contradiction yields \(\psi (K_{1,s})=s=n-1\).

Case 2. \(r=2\). In this case, all vertices in X are twins, also all vertices in Y are twins. Hence, by Proposition 2.2, \(|W\cap Y|\ge s-1\) and \(|W\cap X|\ge 1\). Therefore, \(|W|\ge n-2\). If \(|W|= n-2\), then \( X\cap W=\{x_1\}\) and there exists a vertex \(y_0\in Y\setminus W\). Note that for each \(y\in W\cap Y\), we have \(d(y_0,y)-d(x_1,y)=2-1=1\) and \(d(y_0,x_1)-d(x_1,x_1)=1-0=1\), which is impossible. Therefore, \(\psi (K_{2,s})=s+1=n-1\).

Case 3. \(r\ge 3\). In this case, all vertices in X are twins, also all vertices in Y are twins. Hence, by Proposition 2.2, \(|W\cap Y|\ge s-1\) and \(|W\cap X|\ge r-1\). Therefore, \(|W|\ge n-2\). Let W be a set of vertices of size \(n-2\) such that \(|W\cap Y|= s-1\) and \(|W\cap X|= r-1\). Consider \(a,b\in V(K_{r,s})\). If \(a,b\in Y\), then by Lemma 2.1 we can assume that \(a\in W\) and \(b\notin W\). Since \(s\ge 3\), there exists a vertex \(a\ne w\in W\cap Y\) and we have \(d(a,a)-d(b,a)=-2\) and \(d(a,w)-d(b,w)=0\). Hence, a, b are doubly resolved by a, w. If \(a,b\in X\), by a same argument we deduce that a, b are doubly resolved by a pair of vertices in W. Now, let \(a\in X\) and \(b\in Y\). Since r, s are at least 3, there exist vertices \(x\in W\cap X\setminus \{a\}\) and \(y\in W\cap Y\setminus \{b\}\). Note that

$$\begin{aligned} d(a,x)-d(b,x)=2-1\ne 1-2=d(a,y)-d(b,y). \end{aligned}$$

Therefore, W is a doubly resolving set for \(K_{r,s}\) and \(\psi (K_{r,s})=n-2\). \(\square \)

Through the following theorem, we obtain an upper bound for \(\psi (G)\) in terms of order and diameter of the graph G.

Theorem 2.4

If G is a graph with diameter d and order \(n\ge 2\), then \(\psi (G)\le n-d+1\).

Proof

If \(d=1\) , then \(G=K_n\) and by Lemma 1.2, \(\psi (K_n)\le n-d+1\). Now, let \(d\ge 2\), \(d(v_0,v_d)=d\) and \(P=(v_0,v_1,\ldots ,v_d)\) be a shortest path between \(v_0\) and \(v_d\) in G. We claim that \(S=V(G)\setminus \{v_1,v_2,\ldots ,v_{d-1}\}\) is a doubly resolving set for G. Otherwise, there exist different vertices \(x,y\in V(G)\) that are not doubly resolved by vertices in S. By Lemma 2.1 one of the following cases can happen.

Case 1. \(x,y\notin S\). Since \(V(G)\setminus S=\{v_1,v_2,\ldots ,v_{d-1}\}\), there exist different \(i,j\in \{1,2,\ldots ,d-1\}\) such that \(x=v_i\) and \(y=v_j\). Hence, we have

$$\begin{aligned}&d(x,v_0)-d(y,v_0)=d(v_i,v_0)-d(v_j,v_0)=i-j\ne \\&j-i=d(v_i,v_d)-d(v_j,v_d)=d(x,v_d)-d(y,v_d). \end{aligned}$$

Therefore, \(v_0\) and \(v_d\) doubly resolve x and y, a contradiction.

Case 2. \(x=v_i\in V(G)\setminus S\) and \(y\in S\). Since \(v_i,y\) are not doubly resolved by \(y,v_0\), we have

$$\begin{aligned} d(y,y)-d(v_i,y)=d(y,v_0)-d(v_i,v_0) \Rightarrow d(v_0,y)=d(v_i,v_0)-d(v_i,y). \end{aligned}$$

Also \(y,v_i\) are not doubly resolved by \(y,v_d\) and so

$$\begin{aligned} d(y,y)-d(v_i,y)=d(y,v_d)-d(v_i,v_d) \Rightarrow d(y,v_d)=d(v_i,v_d)-d(v_i,y). \end{aligned}$$

Hence,

$$\begin{aligned}&d(v_0,v_d)\le d(v_0,y)+d(y,v_d)=d(v_i,v_0)\\&\quad -d(v_i,y)+d(v_i,v_d)-d(v_i,y)=d(v_0,v_d)-2d(v_i,y). \end{aligned}$$

It concludes that \( d(v_0,v_d)\le d(v_0,v_d)-2d(x,y)\), which is a contradiction.

These contradictions imply that S is a doubly resolving set for G and \(\psi (G)\le |S|=n-d+1\). \(\square \)

By Lemma 1.3 for every \(n\ge 2\), \(\psi (P_n)=2=n-\mathrm{diam}(P_n)+1\). Therefore, the bound in Theorem 2.4 is sharp.

3 Graphs of order n and doubly resolving number \(n-1\)

The aim of this section is to determine all n-vertex graphs G with \(\psi (G)=n-1\). To do this we need to compute doubly resolving number of some graphs.

Let G and H be two graphs with disjoint vertex sets. The join of G and H, denoted by \(G\vee H\), is the graph with vertex set \(V(G)\cup V(H)\) and edge set \(E(G)\cup E(H)\cup \{uv|\, u\in V(G),v\in V(H)\}\). To find all graphs G of order n with the property \(\psi (G)=n-1\), we need to compute \(\psi (K_2\vee \overline{K_n}).\)

Lemma 3.1

If \(\overline{K_n}\) is the complement graph of \(K_n\), then \(\psi (K_2\vee \overline{K_n})=n+1.\)

Proof

Let \(K_2\vee \overline{K_n}=G\), \(X=V(K_2)\) and \(Y=V(K_n)\). If \(n=1\), then \(G=C_3\) and \(\psi (G)=2=n+1\). Now consider \(n\ge 2\). Clearly all vertices in X are twins, also all vertices in Y are twins. Let W be a doubly resolving set for G. By Proposition 2.2, \(|W\cap X|\ge 1\) and \(|W\cap Y|\ge n-1\). Thus \(|W|\ge n\). If \(|W|=n\), then \( X\cap W=\{x_1\}\) and there exists a vertex \(y_0\in Y\setminus W\). Note that for each \(y\in W\cap Y\), we have \(d(y_0,y)-d(x_1,y)=2-1=1\) and \(d(y_0,x_1)-d(x_1,x_1)=1-0=1\). That is \(y_0,x_1\) are not doubly resolved by any pair of vertices in W, a contradiction. Therefore, \(\psi (G)=|W|=n+1\). \(\square \)

First, we find all graphs G of order n, maximum degree \(n-1\) and \(\psi (G)=n-1\).

Proposition 3.2

Let G be a graph of order \(n\ge 3\) and maximum degree \(\Delta \). If \(\psi (G)=\Delta =n-1\), then G is \(K_n, K_{1,n-1},\) or \(K_2\vee \overline{K_{n-2}}\).

Proof

By Theorem 2.4, it follows that \(\mathrm diam(G)\le 2\). Suppose that x is a vertex of degree \(n-1\) and I is a maximum independent subset of N(x). If \(I=N(x)\), then \(G=K_{1,n-1}\) and if \(|I|=1\), then \(G=K_n\) . Hence, assume that \(2\le |I|\le n-2\). This implies that there exists a vertex \(y\in N(x)\setminus I\). We claim that y is adjacent to all vertices in I. By definition of I, y has a neighbour in I, say a. Since \(\psi (G)=n-1\), the set \(S=V(G)\setminus \{x,y\}\) is not a doubly resolving set for G. If there exists a vertex \(b\in I\) that is not adjacent to y, then

$$\begin{aligned} d(x,a)-d(y,a)=1-1\ne 1-2=d(x,b)-d(y,b). \end{aligned}$$

This means x, y are doubly resolved by \(a,b\in S\). Note that \(2\le |I|\le |S|\), thus for each \(v\in S\), there exists \(v\ne u\in S\) and we have

$$\begin{aligned} d(x,u)-d(v,u)=1-d(v,u)\ne 1=d(x,v)=d(x,v)-d(v,v). \end{aligned}$$

Therefore, for every \(v\in S\), x, v are doubly resolved by some pair of vertices in S. Since S is not a doubly resolving set, Lemma 2.1 implies that there exists a vertex \(s\in S\) such that y, s are not doubly resolved by any pair of vertices in S. Hence,

$$\begin{aligned} d(y,s)=d(y,s)-d(s,s)=d(y,a)-d(s,a)=1-d(s,a). \end{aligned}$$

But \(d(y,s)\ge 1\) and \(d(s,a)\ge 0\) imply \(d(s,a)=0\) and \(s=a\). Note that \(\mathrm diam(G)\le 2\), yields

$$\begin{aligned} d(a,b)-d(y,b)=2-2\ne 0-1=d(a,a)-d(y,a). \end{aligned}$$

This contradiction means that y is adjacent to b. Therefore, y is adjacent to all vertices in I. Since y is an arbitrary vertex in \(N(x)\setminus I\), the above argument implies that all vertices in I are adjacent to all vertices in \(N(x)\setminus I\). We claim that \(N(x)\setminus I=\{y\}\). Suppose on the contrary that \(|N(x)\setminus I|\ge 2\). Let \(S=V(G)\setminus \{a,x\}\), where \(a \in I\) is neighbour of y as before, and \(c\in I\cap S\). We have

$$\begin{aligned} d(a,c)-d(x,c)=2-1\ne 1-1=d(a,y)-d(x,y), \end{aligned}$$

and so a, x are doubly resolved by \(c,y\in S\). Also

$$\begin{aligned} d(x,y)-d(y,y)=1\ne 0=d(x,c)-d(y,c) \end{aligned}$$

and for each \(y\ne p\in S\) we have

$$\begin{aligned} d(x,y)-d(p,y)\ne 1=d(x,p)-d(p,p). \end{aligned}$$

Therefore, for every \(p\in S\), vertices x, p are doubly resolved by some vertices in S. Since S is not a doubly resolving set, there exists a vertex \(s\in S\) such that s, a are not doubly resolved by any pair of vertices in S. If \(s\in I\cap S\), then

$$\begin{aligned} d(s,y)-d(a,y)=1-1\ne -2=d(s,s)-d(a,s), \end{aligned}$$

which is impossible. Thus, \(s\in N(x)\setminus I\). Let \(s\ne y'\in N(x)\setminus I\), this implies \(d(a,y')-d(s,y')=1-d(s,y')\le 0\) and \(d(a,s)-d(s,s)=1\). That means a, s are doubly resolved by \(s,y'\in S\). This contradiction leads us to \(N(x)\setminus I=\{y\}\). Therefore, \(|I|=n-2\) and \(G=K_2\vee \overline{K_{n-2}}\). \(\square \)

The next theorem determines all graphs G of order n and \(\psi (G)=n-1\).

Theorem 3.3

Let G be a graph of order \(n\ge 3\). Then \(\psi (G)=n-1\) if and only if G is \(K_n, K_{1,n-1},K_{2,n-2},\) or \(K_2\vee \overline{K_{n-2}}\).

Proof

By Lemmas 1.2, 2.3 and 3.1 the doubly resolving number of each of the graphs mentioned in the statement of the theorem is \(n-1\).

For the converse, assume that G is a graph of order \(n\ge 3\) such that \(\psi (G)=n-1\). By Theorem 2.4, it follows that \(\mathrm diam(G)\le 2\). Let \(\Delta \) be the maximum degree in G. Since G is connected and has at least 3 vertices, we have \(\Delta \ge 2\).

If \(\Delta =2\), then G is a path \(P_n\) or a cycle \(C_n\). If \(G=P_n\), then by Lemma 1.3, \(n=3\) and \(G=P_3=K_{1,2}\). In the case \(G=C_n\), Lemma 1.4 implies that \(n\in \{3,4\}\) and \(G=C_3=K_3\) or \(G=C_4=K_{2,2}\).

Now, let \(\Delta \ge 3\). If \(\Delta =n-1\), then by Proposition 3.2, G is \(K_n, K_{1,n-1},\) or \(K_2\vee \overline{K_{n-2}}\). If \(3\le \Delta \le n-2\), then let x be a vertex of degree \(\Delta \) and y be a non-adjacent vertex to x. Since \(\mathrm diam(G)\le 2\), vertices x, y have a common neighbour, say a. \(\Delta \ge 3\) implies x has at least two more neighbours, say b and c. Clearly, \(S=V(G)\setminus \{a,x\}\) is not a doubly resolving set for G. But a, x are doubly resolved by y, b because

$$\begin{aligned} d(a,y)-d(x,y)=1-2=-1<0\le d(a,b)-1= d(a,b)-d(x,b). \end{aligned}$$

Also for each \(s\in S\), vertices x, s are doubly resolved by some pair of vertices in S. To see this, we must consider two cases \(s=c\) or \(s\ne c\). If \(s=c\), then \(d(c,c)-d(x,c)=-d(x,c)=-1\) and \(d(c,b)-d(x,b)=d(c,b)-1\ge 0\). If \(s\ne c\), then \(d(s,s)-d(x,s)=-d(x,s)<0\) and \(d(s,c)-d(x,c)=d(s,c)-1\ge 0\). Since S is not a doubly resolving set for G, there exists a vertex \(s\in S\) such that a, s are not doubly resolved by any pair of vertices in S. Let us suppose that \(s\ne y\). Then

$$\begin{aligned} 1\le d(a,s)=d(a,s)-d(s,s)=d(a,y)-d(s,y)=1-d(s,y). \end{aligned}$$

This contradiction means \(s=y\). Note that \(1=d(a,y)-d(y,y)=d(a,c)-d(y,c).\) Hence, \(d(a,c)=2\) and \(d(y,c)=1\). Since c is an arbitrary neighbour of x, we deduce that \(N(y)=N(x)\) and N(x) is an independent set. We claim that \(V(G)=N(x)\cup \{x,y\}\). Suppose on the contrary that there exists a vertex \( y'\in V(G)\setminus (N(x)\cup \{x,y\})\). By argument similar to the above, we have \(N(y')=N(x)\). Since \(\psi (G)=n-1\), the set \(S=V(G)\setminus \{y',c\}\) can not be a doubly resolving set for G. But \(y',c\) are doubly resolved by y, b. If \(s\in S\cap N(x)\), then

$$\begin{aligned} d(c,s)-d(s,s)=2\ne 0=d(c,x)-d(s,x). \end{aligned}$$

For \(s\in S\setminus N(x)\), let \(s\ne s'\in S\setminus N(x)\). Hence,

$$\begin{aligned} d(c,s')-d(s,s')=1-2\ne 1=d(c,s)-d(s,s). \end{aligned}$$

Therefore, for every \(s\in S\), vertices c, s are doubly resolved by some pair of vertices in S. In the same way for every \(s\in S\), vertices \(y',s\) are doubly resolved by some pair of vertices in S. This means S is a doubly resolving set for G, which is a contradiction. Thus, \(V(G)=N(x)\cup \{x,y\}\), \(N(x)=N(y)\) is an independent set, and x is not adjacent to y. Therefore, \(G=K_{2,n-2}\). \(\square \)

4 Doubly resolving number of unicyclic graphs

In this section, we investigate doubly resolving sets in unicyclic graph. A unicyclic graph is a graph that has exactly one cycle. Chen and Wang [8] designed a polynomial time algorithms for the problem of finding doubly bases in unicyclic graphs. Also, Lu et al. [15] proved that unicyclic graphs with minimum degree 2 admit a doubly resolving set of size at most 3. Both of these papers deal with the problem algorithmically. In this paper, we prove that the number of leaves of unicyclic graphs is a lower bound for the doubly resolving number. Also, the doubly resolving number in these graphs is at most the number of leaves plus 2. In addition, both of these bounds are attainable. If G is a unicyclic graph, C(G) indicates the unique cycle of G. For each vertex \(x\in V(C(G))\) of degree at least 3, we define

$$\begin{aligned} V(x)=\{v\in V(G)\setminus V(C(G))|\forall y\in V(C(G))\setminus \{x\}, d(v,x)< d(v,y)\}, \end{aligned}$$

and T(x) as the induced subgraph \(\langle \{x\}\cup V(x)\rangle \) of G. Clearly T(x) is a tree. A leaf in a graph is a vertex of degree 1. We use the notations L(G) and l(G) for the set of all leaves in the graph G and its cardinality, respectively. Caceres et al. [5] proved the following lemma for doubly bases of trees.

Lemma 4.1

[5] The set of leaves is the unique doubly resolving basis for a tree.

By the same proof, we can see that each resolving set of a graph contains all leaves. The following lemma prepares a lower bound for doubly resolving number in terms of the number of leaves in a graph.

Lemma 4.2

Let v be a vertex of degree 1 in a graph G. Then, v belongs to all doubly basis of G, and

$$\begin{aligned} \psi (G)\ge l(G). \end{aligned}$$

Proof

Let B be a doubly basis of G and u be the neighbour of v. If \(v\notin B\), then for every \(x,y\in B\), we have \(d(v,x)-d(u,x)=1=d(v,y)-d(u,y)\). This contradiction implies that \(v\in B\). Therefore, \(\psi (G)\ge l(G).\) \(\square \)

Proposition 4.3

Let G be a unicyclic graph and W be a doubly resolving set for C(G). If every vertex of W is of degree at least 3, then L(G) is a doubly basis of G.

Proof

Let \(r,s\in V(G)\), we need to consider the following three cases.

Case 1. \(r,s\in V(C(G))\). Since W is a doubly resolving set for C(G), there are vertices \(x,y\in W\) that r, s are doubly resolved by x, y. Let \(x_1\in V(x)\) and \(y_1\in V(y)\) be leaves. Then

$$\begin{aligned} d(r,x_1)-d(s,x_1)= & {} d(r,x)+d(x,x_1)-(d(s,x)+d(x,x_1))=\\= & {} d(r,x)-d(s,x)\ne d(r,y)-d(s,y)=\\= & {} d(r,y)+d(y,y_1)-(d(s,y)+d(y,y_1))=\\= & {} d(r,y_1)-d(s,y_1). \end{aligned}$$

Therefore, r, s are doubly resolved by leaves \(x_1,y_1\).

Case 2. \(r\in V(C(G))\) and \(s\notin V(C(G))\). Let \(s\in V(t)\) for some \(t\in V(C(G))\). Hence, there are vertices \(x,y\in W\) such that r, t are doubly resolved by x, y. There are two possibilities, \(t\in \{x,y\}\) or \(t\notin \{x,y\}\). If \(t\in \{x,y\}\), say \(t=x\), then let \(y_1\) be a leaf in V(y) and \(x_1\) be a leaf in V(x) such that s is a vertex in the shortest path between x and \(x_1\). Hence, \(d(x,x_1)=d(x,s)+d(s,x_1)\). If r, s are not resolved by \(x_1,y_1\), then

$$\begin{aligned}&d(r,x)+d(x,s)\\&\quad = (d(r,x)+d(x,s)+d(s,x_1))-d(s,x_1)=d(r,x_1)-d(s,x_1)=\\&\quad = d(r,y_1)-d(s,y_1)=d(r,y)+d(y,y_1)-(d(s,y)+d(y,y_1))=\\&\quad = d(r,y)-d(s,y)=d(r,y)-(d(s,x)+d(x,y)). \end{aligned}$$

Hence, \(d(r,x)+d(x,y)=d(r,y)-2d(x,s)\). But we know that \(d(r,y)\le d(r,x)+d(x,y)\) satisfies for all three vertices \(x,y,r\in V(G)\). Therefore,

$$\begin{aligned} d(r,y)\le d(r,x)+d(x,y)=d(r,y)-2d(s,x)\le d(r,y)-2, \end{aligned}$$

which is impossible. Thus r, s are doubly resolved by \(x_1,y_1\). If \(t\notin \{x,y\}\), let \(x_1\) be a leaf in V(x) and \(y_1\) be a leaf in V(y). Then

$$\begin{aligned} d(r,x_1)-d(s,x_1)= & {} d(r,x)+d(x,x_1)-(d(s,t)+d(t,x)+d(x,x_1))=\\= & {} d(r,x)\!-\!(d(s,t)\!+\!d(t,x))\!\ne \! d(r,y)\!-\!(d(s,t)\!+\!d(t,y))=\\= & {} d(r,y)+d(y,y_1)-(d(s,t)+d(t,y)+d(y,y_1))=\\= & {} d(r,y_1)-d(s,y_1). \end{aligned}$$

Therefore, r, s are doubly resolved by leaves \(x_1,y_1\).

Case 3. \(r,s\notin V(C(G))\). Let \(r\in V(y)\) and \(s\in V(x)\) for some \(x,y\in V(C(G))\). If \(x\ne y\), let \(x_1\in V(x)\) be a leaf such that s is in the shortest path between x and \(x_1\) and \(y_1\in V(y)\) be a leaf such that r is in the shortest path between y and \(y_1\). Thus,

$$\begin{aligned} d(r,x_1)-d(s,x_1)=d(r,y)+d(y,x)+d(x,s)+d(s,x_1)-d(s,x_1)>0, \end{aligned}$$

and

$$\begin{aligned} d(r,y_1)-d(s,y_1)=d(r,y_1)-(d(s,x)+d(x,y)+d(y,r)+d(r,y_1))<0. \end{aligned}$$

Therefore, r, s are doubly resolved by \(x_1,y_1\). If \(x=y\), then by Lemma 4.1 leaves of T(x) is a basis for T(x). Let u, t be two leaves of T(x) that doubly resolve r, s. If \(x\notin \{u,t\}\), then u, t are leaves of G. If \(x\in \{u,t\}\), say \(x=t\), then let \(t\ne y_1\in V(G)\setminus V(x)\) be a leaf of G. Thus

$$\begin{aligned}&d(r,y_1)-d(s,y_1)=d(r,x)+d(x,y_1)-(d(s,x)+d(x,y_1))\\&\quad =d(r,x)-d(s,x)\ne d(r,t)-d(s,t). \end{aligned}$$

Therefore, r, s are doubly resolved by x, t and the result follows. \(\square \)

Corollary 4.4

Let G be a unicyclic graph and W be a doubly resolving set for C(G). If U is the set of all vertices of degree 2 in W, then \(L(G)\cup U\) is a doubly resolving set for G.

Proof

Let \(U=\{u_1,u_2,\ldots ,u_t\}\). We construct the graph \(G'\) by adding leaves \(v_i;1\le i\le t\), to the graph G such that for each \(i;1\le i\le t\), \(v_i\) is adjacent to \(u_i\). By Proposition 4.3, \(L(G')\) is a doubly basis of \(G'\). Note that \(L(G')=L(G)\cup \{v_1,v_2\ldots ,v_t\}\). Let x, y be two vertices in G. Then, for every i, \(d(x,v_i)-d(y,v_i)=d(x,u_i)-d(y,u_i)\). Therefore, \(L(G)\cup U\) is a doubly resolving set for G. \(\square \)

The next theorem obtains an upper bound for the doubly resolving number of unicyclic graphs.

Theorem 4.5

Let G be a unicyclic graph that is not a cycle. If C(G) is of order m, then

$$\begin{aligned} l(G)\le \psi (G)\le \left\{ \begin{array}{ll} l(G)+1 &{} ~~~~ \mathrm{if~}m\mathrm{~is~ odd}, \\ l(G)+2 &{} ~~~~ \mathrm{if~}m\mathrm{~is ~ even}. \end{array}\right. \end{aligned}$$

Proof

Let \(C(G)=(v_1,v_2,\ldots ,v_m,v_1)\). If m is odd by lemma 1.4, \(\psi (C(G))=2\). Let \(\{v_i,v_j\}\) be a doubly basis of C(G). Since G is not a cycle, at least one of the vertices in C(G) is of degree 3. By relabeling vertices of C(G), we can assume that \(v_i\) is of degree at least 3. Hence, by Corollary 4.4, \(W=L(G)\cup \{v_j\}\) is a doubly resolving set for G if \(v_j\) is of order 2, and \(W = L(G)\) if \(v_j\) is of order 3. Therefore, \(l(G)\le \psi (G)\le l(G)+1\). If m is even by lemma 1.4, \(l(G)\le \psi (C(G))=3\). The same argument implies that \(\psi (G)\le l(G)+2\). \(\square \)

The following corollary explains some conditions that imply \(\psi (G)=l(G)\).

Corollary 4.6

Let G be a unicyclic graph that is not a cycle and B be a doubly basis of C(G). If all vertices of B are of degree at least 3, then \(\psi (G)=l(G)\).

Proof

Let U be as in Corollary 4.4. Then, by Corollary 4.4, \(L(G)\cup U\) is a doubly resolving set for G. Note that \(U=\emptyset \). Hence, \(\psi (G)\le l(G)\). Therefore, Theorem 4.5 implies that \(\psi (G)=l(G)\). \(\square \)