On the metric dimension, the upper dimension and the resolving number of graphs

Discrete Applied Mathematics On the metric dimension, the upper dimension and the resolving number of graphs Delia Garijo∗, Antonio González, Alberto Márquez Dept. de Matemática Aplicada I, Universidad de Sevilla, Spain Keywords: Resolving set Metric dimension Upper dimension Resolving number abstract This paper deals with three resolving parameters: the metric dimension, the upper dimension and the resolving number. We first answer a question raised by Chartrand and Zhang asking for a characterization of the graphs with equal metric dimension and resolving number. We also solve in the affirmative a conjecture posed by Chartrand, Poisson and Zhang about the realization of the metric dimension and the upper dimension. Finally, we prove that no integer a≥4 is realizable as the resolving number of an infinite family of graphs. 1. Introduction In this paper, we study resolving sets for finite simple connected graphs. They were introduced in the 1970s independently by Slater [9], and Harary and Melter [5]. The usefulness of these sets comes from their multiple applications in several areas, among them: coin weighing problems, network discovery and verification, robot navigation, strategies for Mastermind game and pharmaceutical chemistry (we refer the reader to [1] for a number of references on this topic). Resolving sets are formally defined as follows. Let G=(V(G), E(G)) be a finite simple connected graph of order n= |V(G)|. The distance d(u, v) between two vertices u, v ∈V(G)is the length of a shortest u–vpath in G. A vertex u∈V(G)resolves a pair {x,y} ⊂ V(G)if d(u,x)= d(u,y). A set of vertices S⊆V(G)is a resolving set of Gif every pair of vertices of Gis resolved by some vertex of S. A resolving set S of minimum size is a metric basis, and |S|is the metric dimension of G, denoted by dim(G). Our aim is not only to deal with metric bases and metric dimension but also with two other resolving parameters defined by Chartrand et al. [3], namely the upper dimension and the resolving number, that give an insight of how large the set of resolving sets of a graph is. A resolving set Sof Gis minimal if no proper subset of Sis a resolving set. An upper basis is a minimal resolving set containing the maximum number of vertices. The upper dimension dim+(G)is the size of an upper basis. The resolving number res(G)is the minimum ksuch that every k-subset of V(G)is a resolving set of G. For instance, dim+(Pn)=res(Pn)= 2,dim+(Cn)=2 and res(Cn)=3 where Pnand Cndenote, respectively, a path of order n≥4 and a cycle of even order n≥4 [3]. Clearly, every (n−1)-subset of V(G)is a resolving set and every resolving set contains a minimal resolving set. Hence, 1≤dim(G)≤dim+(G)≤res(G)≤n−1. ∗Corresponding author. Tel.: +34 954552795; fax: +34 954556683. E-mail addresses: [email protected] (D. Garijo), [email protected] (A. González), [email protected] (A. Márquez). D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 1441 When dim(G)=res(G)=k, the graph Gis called randomly k-dimensional, i.e., every k-subset of V(G)is a metric basis and so Ghas the maximum number of metric bases of a fixed size k. Chartrand and Zhang [4] posed the problem of characterizing the randomly k-dimensional graphs. They solved the case k≤2, obtaining the complete graphs K1and K2(for k=1) and odd cycles (for k=2), and leaving open the main following question. Problem 1.1 ([4]).Are there randomly k-dimensional graphs other than complete graphs and odd cycles? Concerning the three parameters, Chartrand et al. [3] investigated different questions related to graph realization. In particular, they proved that every pair a,bof integers with 2 ≤a≤bis realizable as the metric dimension and the resolving number, respectively, of some connected graph G. It was also shown the analogous result for dim(G)=dim+(G)=aand res(G)=b. Moreover, the authors proved that every pair among the three parameters can differ by an arbitrarily large number. Finally, it was remarked that there were reasons to believe that every pair a,bof integers with 2 ≤a≤bis realizable as the metric dimension and the upper dimension, respectively, of some connected graph. Thus, they proposed the following conjecture. Conjecture 1.2 ([3]).For every pair a,b of integers with 2≤a≤b, there exists a connected graph G with dim(G)=a and dim+(G)=b. In this paper, we solve Problem 1.1 (Theorem 2.5) and settle in the affirmative Conjecture 1.2 (Theorem 3.5). We also show that, unlike the metric dimension and the upper dimension, no integer a≥4 is realizable as the resolving number of an infinite family of graphs (Theorem 3.7). 2. Randomly k-dimensional graphs In this section, we characterize the randomly k-dimensional graphs. While preparing this paper, we have learnt of [6], where the authors prove the same result. Here we present an alternative, shorter proof. We start with some technical lemmas needed for the case k=3. Denote by Pλ(G)the λ-subsets of V(G)and let Ni(u)be the set of vertices at distance ifrom u∈V(G). For {u, v},{x,y} ∈ P2(G)we say that the pair {u, v}resolves the pair {x,y}if either uor vresolves it. In general, T∈Pλ(G)resolves a pair {x,y}if there is a vertex in Tthat resolves it. Lemma 2.1. Let G be a randomly 3-dimensional graph. Then, the following statements hold. (a) For every pair {u, v} ∈ P2(G)there exist unique pairs {x,y},{r,s} ∈ P2(G)such that {x,y}is not resolved by {u, v}, and {u, v}is not resolved by {r,s}. (b) Every vertex u ∈V(G)satisfies  1≤i≤ecc(u)|Ni(u)| 2=n−1 (1) where by convention 1 2=0, and ecc(u)denotes the eccentricity of u, i.e., the maximum distance from u to any other vertex. Proof. To prove Statement (a), consider a graph Gverifying that dim(G)=res(G)=3. For every pair P= {u, v} ∈ P2(G), consider the set SP= {{x,y} | Pdoes not resolve {x,y}} ⊂ P2(G). Since dim(G)=3 then SPis non-empty. Moreover, SP∩SP′= ∅ whenever P= P′. Indeed, suppose on the contrary that there is a pair {x,y}resolved by neither P= {u, v}nor P′= {u′, v′}, and assume that u, v = u′. Then the set {u, v, u′}is not a metric basis, which is a contradiction. Therefore, SP∩SP′= ∅. Thus, |SP| = 1 for every P∈P2(G). This proves that for every pair {u, v}there is a unique pair {x,y}such that {u, v}does not resolve {x,y}. Further, the map ϕ:P2(G)→P2(G) given by ϕ(P)=SPis well-defined and injective (where by abuse of notation, we consider SP∈P2(G)). Then ϕis a bijection and so there is a unique pair {r,s}which does not resolve {u, v}. Hence, Statement (a) follows. Consider now the set Suof non-resolved pairs by a vertex u∈V(G). As a consequence of Statement (a) we have |Su| = n−1 (it suffices to consider the n−1 distinct pairs {u, v}with v∈V(G)\ {u}). On the other hand, a pair {x,y} ∈ Suif and only if x,y∈Ni(u)for i=d(x,u)=d(y,u). Hence, |Su| =  1≤i≤ecc(u)|Ni(u)| 2 which proves Statement (b).  Given u∈V(G), consider the partition P(u)= {Ni(u)|0≤i≤ecc(u)}of V(G)into classes (where N0(u)= {u}). Lemma 2.1(b) says that there is a compensation between vertices of V(G)\ {u}and pairs of vertices located in the same class of P(u). For instance, classes of size at least 4 always contribute to Eq. (1) with more pairs than vertices (6 pairs and 1442 D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 4 vertices in case of size 4) and so they have to be compensated with classes of size at most 2 whose contribution is bigger in terms of vertices than in pairs. Note that classes of size 3 which contribute with 3 pairs, are self-compensated. Therefore, we have the following lemma. Lemma 2.2. Let u ∈V(G)and let P(u)= {Ni(u)|0≤i≤ecc(u)}be a partition of V (G)into classes with N0(u)= {u}. Then, the following statements hold. (a) If P(u)contains a class of size at least 4then it contains at least two classes of size at most 2different than N0(u). (b) If P(u)contains a class of size at most 2different than N0(u)then it contains a class of size at least 4. The following straightforward observation will be useful for the proofs of this paper. Observation 2.3 ([8]).Let u, v, w ∈V(G)such that {v, w} ∈ E(G)and d(u, v) =d. Then, d(u, w) ∈ {d−1,d,d+1}. Lemmas 2.1 and 2.2 are the key tools to avoid the case analysis in the characterization of the randomly 3-dimensional graphs. Proposition 2.4. If a graph G is randomly 3-dimensional then G is the complete graph on 4vertices. Proof. First, observe that Gdoes not contain vertices of degree 1 (Lemma 1 of [7]). Indeed, if a vertex uhas a unique neighbour v, then the pair {u, v}is resolved by every vertex of G, which contradicts Lemma 2.1(a). Claim 1. The degree of every vertex of G is at most 3. Proof of Claim 1. Suppose on the contrary that there is a vertex u∈V(G)of degree at least 4, and let u1,u2,u3,u4∈N1(u). By Lemma 2.1(a), each set Aij = {v∈V(G)|d(v, ui)=d(v, uj)}with 1 ≤i<j≤4 contains exactly two vertices of G. Let v∈V(G)such that d(u, v) =d. By Observation 2.3,d(v, ui)∈ {d−1,d,d+1}and so the set {d(v, ui)|1≤i≤4}has at most 3 elements which implies that vbelongs to at least one of the six sets Aij. Hence, n≤7 since u∈Aij for all i,j. Consider now the partition P(u)in which N1(u)is a class of size at least 4. By Lemma 2.2(a), there are at least two classes of size at most 2 different than N0(u). Further, n≤7 and so there are exactly three classes of size 1 in P(u)(one being N0(u)) which implies that the furthest vertex from uhas degree 1; a contradiction. Therefore, every vertex of Ghas degree at most 3.  Claim 2. n∈ {4,7,10}. Proof of Claim 2. Since dim(G)=3, then Gis neither a path nor a cycle and so there is a vertex u∈V(G)of degree 3 with neighbours, say u1,u2,u3. Arguing as in the proof of Claim 1, defining the analogous sets Aij but for the vertices u,u1,u2,u3, we have n≤10 since every set contains exactly two vertices of G,ubelongs to three of them, and every vertex of Gbelongs to at least one of the six sets. The sets {u}and {u1,u2,u3}are the classes N0(u)and N1(u), respectively, in the partition P(u). If this partition does not contain more classes, then n=4. Otherwise, by Lemma 2.2, there are three possibilities for P(u): (1) one class of size 4 and two classes of size 1 (plus N0(u)and N1(u)); (2) N0(u)and three classes of size 3 (one being N1(u)); (2) N0(u)and two classes of size 3 (one being N1(u)). This gives n=10 or n=7.  Claim 3. There is no vertex of degree 2. Proof of Claim 3. Suppose on the contrary that there is a vertex u∈V(G)of degree 2. Then, |N1(u)| = 2. By Lemma 2.2, P(u)contains a class of size at least 4 and another class of size at most 2 different than N0(u). Since n≤10, we have the following two possibilities for P(u): (1) one class of size 4, two classes of size 1 (one being N0(u)) and one class of size 2; (2) one class of size 4, one class of size 1 (being N0(u)) and two classes of size 2. This gives, respectively, n=8 and n=9 contradicting Claim 2. The three previous claims prove that a graph Gof order nsatisfying dim(G)=res(G)=3 is 3-regular and n∈ {4,7,10}. Clearly, n= 7 since there is no 3-regular graph with 7 vertices. Consider now two vertices u, v ∈V(G)such that d(u, v) =d(G), where d(G)denotes the diameter of G, and let N1(u)= {u1,u2,u3}. By Observation 2.3, the distance from vto every vertex of the set {u,u1,u2,u3}is either d(G)or d(G)−1. Hence, vbelongs to at least two of the six sets Aij as defined in the proof of Claim 2. By Lemma 2.1(a), each set contains exactly two vertices of Gand ubelongs to three of them. This gives n<10 and so n=4, which implies that Gis isomorphic to the complete graph K4(the only 3-regular graph on 4 vertices).  Now, we reach the desired characterization that solves Problem 1.1. Theorem 2.5. A graph G is randomly k-dimensional if and only if G is a complete graph or an odd cycle. D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 1443 Proof. If Gis isomorphic to a complete graph or an odd cycle, it is straightforward to prove that Gis randomly k-dimensional. Suppose now that Gis a graph of order nsatisfying dim(G)=res(G)=k. As was said before the case k≤2 was proved in [4], obtaining the complete graphs K1and K2(for k=1) and odd cycles (for k=2). Moreover, Proposition 2.4 proves the result for k=3 and so we can assume k≥4. Arguing as in the proof of Lemma 2.1(a) we have that for every T∈Pk−1(G), the non-empty set ST= {{x,y} | Tdoes not resolve {x,y}} ⊂ P2(G) verifies that ST∩ST′= ∅ whenever T= T′. Therefore |Pk−1(G)|≤|P2(G)|, i.e., n k−1≤n 2H⇒ k∈ {1,2,3,n−1,n,n+1}. Hence, k=n−1 since 4 ≤k=dim(G)≤n−1. This implies that Gis isomorphic to the complete graph Kn, which is the only graph of order nwith metric dimension n−1 [2].  3. Realization 3.1. The metric dimension and the upper dimension This subsection is devoted to settle in the affirmative Conjecture 1.2. In order to do this, we compute the upper dimension of two families of graphs for which the metric dimension is easily obtained. These graphs are constructed from the grid graphs attaching at the origin either a triangle or a number of pendant vertices. We start with some notation and technical lemmas. Let Gℓbe the grid graph of order ℓ×ℓwith ℓ≥2, whose vertex set is the Cartesian product [0, ℓ −1]×[0, ℓ −1]and distances given by d((x1,x2), (y1,y2)) = |x1−y1|+|x2−y2|. We shall use (x1,x2)to indicate the coordinates of a vertex x∈V(Gℓ)(analogously, y=(y1,y2), z=(z1,z2), etc.). The following sets of vertices are called quadrants of x ∈V(Gℓ): Q1(x)= {y∈V(Gℓ)|y1≥x1,y2≥x2},Q2(x)= {y∈V(Gℓ)|y1≤x1,y2≥x2}, Q3(x)= {y∈V(Gℓ)|y1≤x1,y2≤x2},Q4(x)= {y∈V(Gℓ)|y1≥x1,y2≤x2}, and the sets Di= {x∈V(Gℓ)|x1+x2=i}with 0 ≤i≤2ℓ−2 are the diagonals of Gℓ(see Fig. 1(a)). A pair of vertices {x,y}is said to be a diagonal pair if x,y∈Difor some i. Note that a quadrant Qi(x)might be equal to {x}and there is a total order <iin each diagonal Di(or simply ‘‘<’’ when no confusion can arise) given by x<iy⇐⇒ x1<y1. In the sequel we shall assume, without loss of generality, that the order of the two elements of a diagonal pair {x,y}is x<y(analogously, r<sfor {r,s}or t<zfor {t,z}). Let R(x,y)be the set of vertices of Gℓthat resolve the pair {x,y} ⊂ V(Gℓ), and let Sbe a resolving set of Gℓ. Note that the set R(x,y)∩Sis non-empty for every pair {x,y}. Lemma 3.1. Let {x,y}be a diagonal pair such that d(x,y)=2. Then, R(x,y)=Q2(x)∪Q4(y). Proof. For every vertex u∈Q2(x), there is a shortest u−ypath going through xand so d(u,y)=d(u,x)+d(x,y)= d(u,x)+2. Thus, uresolves {x,y}(analogous for u∈Q4(y)). Let u∈V(Gℓ)\(Q2(x)∪Q4(y)), z=(x1,y2)and ˜ z=(y1,x2). Clearly, there are two shortest paths P1and P2joining u to xand uto y, respectively, such that either z∈P1,P2or ˜ z∈P1,P2(see Fig. 1(b)). Since z,˜ zdo not resolve the pair {x,y} then u∈ R(x,y). Given a resolving set Sof Gℓ, a pair {x,y}is said to be S-unique if there is a unique vertex u∈Sresolving {x,y}, i.e., R(x,y)∩S= {u}. The vertex uand the pair {x,y}are said to be associated to each other. The following observation is straightforward. Observation 3.2. Let S be a resolving set of Gℓ, and let {x,y}be an S-unique pair with associated vertex u. If there is a pair {r,s} such that R(r,s)⊆R(x,y)then {r,s}is S-unique with associated vertex u. Note that necessarily u ∈R(r,s). Lemma 3.3. Let S be a resolving set of Gℓ, and let {x,y}={(x1,x2), (y1,y2)}be an S-unique diagonal pair with associated vertex u such that d(x,y) > 2. Then, there exist exactly y1−x1S-unique diagonal pairs {r,s}with associated vertex u and d(r,s)=2. 1444 D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 Fig. 1. (a) Quadrants of xand a diagonal Di, (b) the shadowed region illustrates Q2(x)∪Q4(y), and the dotted edges form the paths P1and P2. Fig. 2. (a) All the vertices in the shadowed region plus the two squared vertices do not resolve the pair {x,y}, (b) the shadowed region illustrates R(x,y). Proof. A similar argument as in the proof of Lemma 3.1, considering z=(x1,y2)and ˜ z=(y1,x2), gives that every vertex u∈Q3(z)∪Q1(˜ z)does not resolve the pair {x,y}. Clearly, the vertices (x1+j,y2+j)with 0 <j<y1−x1do not resolve the pair {x,y}either (see Fig. 2(a)). Thus, the expression of R(x,y)in this case is R(x,y)=V(Gℓ)\(Q3(z)∪Q1(˜ z)∪ {(x1+j,y2+j)|0<j<y1−x1}). This set can also be expressed as follows: R(x,y)= 0≤j<y1−x1 R(rj,sj) where rj=(x1+j,y2+j+1), sj=(x1+j+1,y2+j)and d(rj,sj)=2 (see Fig. 2(b)). Since R(rj,sj)⊆R(x,y),Observation 3.2 proves the result.  Two diagonal pairs {x,y},{r,s}such that d(x,y)=d(r,s)=2 are said to be in the same row if x2=r2and y2=s2. Analogously, they are in the same column if x1=r1and y1=s1. Lemma 3.4. Let S be a resolving set of Gℓ, and let {x,y}be an S-unique diagonal pair with associated vertex u such that d(x,y)=2. If there exist two S-unique diagonal pairs {r,s},{t,z}in the same row (column) than {x,y}with associated vertices, respectively, vand wand u = v, w, then v=w. Proof. Suppose that the pairs {r,s},{t,z}are in the same row (analogous for columns) than {x,y}, i.e., x2=r2=t2and y2=s2=z2. Assume also that x1<r1<t1. Clearly, R(r,s)⊂(R(x,y)∪R(t,z)) and so v=wsince v= u. Now, we reach our main result in this subsection which settles in the affirmative Conjecture 1.2. Theorem 3.5. For every pair a,b of integers with 2≤a≤b, there exists a connected graph G with dim(G)=a and dim+(G)=b. Proof. Let Hℓbe the graph obtained from Gℓwith ℓ≥2, by attaching a triangle at vertex (0,0), i.e., V(Hℓ)=V(Gℓ)∪ {α, β} and E(Hℓ)=E(Gℓ)∪ {{α, β},{α, (0,0)},{β, (0,0)}} (see Fig. 3(a)). Observe that distances in Hℓbehave as in Gℓ, except for the new vertices αand βfor which d(α, x)=d(β, x)=x1+x2+1 for every x=(x1,x2)∈V(Gℓ). Thus, the previous lemmas can be applied to the graph Hℓ. Claim A. dim(Hℓ)=2and dim+(Hℓ)=2ℓ−2. D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 1445 Fig. 3. (a) A minimal resolving set of Hℓof size 2ℓ−2, (b) a minimal resolving set of Hℓ,mof size m+2ℓ−4. Proof of Claim A. It is well-known that dim(Gℓ)=2 the set {(0,0), (ℓ −1,0)}being a metric basis (see for instance [8]). This set can be adapted to a metric basis of Hℓby considering {α, (ℓ −1,0)}. Hence, dim(Hℓ)=2. To prove that dim+(Hℓ)≥2ℓ−2 one can easily check that the set S= {(x1,x2)|1≤x1≤ℓ−2,x2∈ {x1,x1+1}} ∪ {(0,1), α} is a resolving set of Hℓof size 2ℓ−2. Moreover, Sis minimal because removing either a vertex (x1,x1)or (x1,x1+1)from Sgives that either the pair {(x1,x1), (x1−1,x1+1)}or the pair {(x1,x1+1), (x1+1,x1)}is not resolved by any element of S. Clearly, (0,1)and αcannot be removed from S.Fig. 3(a) illustrates this minimal resolving set. We next prove that dim+(Hℓ)≤2ℓ−2. Let Sbe a minimal resolving set of Hℓ. Consider the pair {α, β}which is only resolved by either αor β. Without loss of generality, we assume that α∈Sand β∈ S. Since Sis minimal, every vertex u∈Shas an associated S-unique pair, say p(u). Observe that {β, (0,0)}is not an S-unique pair (every vertex of Gℓresolves it) and so there is no vertex u∈Sso that p(u)= {β, (0,0)}. Also note that αresolves all the non-diagonal pairs of Gℓ. Hence, every vertex u∈S\ {α}has an associated S-unique diagonal pair p(u). Moreover, by Lemma 3.3, we can assume that the elements of p(u)are at distance 2 from each other. Let us consider all these S-unique pairs. By Lemma 3.4, for all pairs of the same row (or column), there are at most two distinct vertices associated to these pairs. Moreover, we claim that there is at most one such vertex in the first row (and the first column). Indeed, by Lemma 3.1 we have R((0,1), (1,0)) =Q2((0,1)) ∪Q4((1,0)) = {(0,x2)|1≤x2≤ ℓ−1}∪{(x1,0)|1≤x1≤ℓ−1}. Suppose that there is a vertex v∈S∩Q2((0,1)) (analogous for v∈S∩Q4((1,0)) by symmetry). Since all the pairs in the same row as {(0,1), (1,0)}are resolved by vand Sis minimal, then there is no other vertex of Sassociated to pairs in such row. Hence, in total, since there are ℓ−1 rows (and columns), there are at most 2(ℓ −2)+1S-unique pairs that can be associated to the vertices of S\ {α}, and thus |S\ {α}| = |S| − 1≤2(ℓ −2)+1.  Consider now the graph Hℓ,mobtained from Gℓwith ℓ≥3 by attaching a set of m≥2 pendant vertices {α1, . . . , αm}at (0,0)(see Fig. 3(b)). Claim B. dim(Hℓ,m)=m+1and dim+(Hℓ,m)=m+2ℓ−4. Proof of Claim B. As was said before, the set {(0,0), (ℓ−1,0)}is a metric basis of Gℓ[8]. Thus, it can be easily checked that the set {α1, . . . , αm, (ℓ −1,0)}is a resolving set of Hℓ,m, which gives dim(Hℓ,m)≤m+1. To prove that dim(Hℓ,m)≥m+1, it suffices to show that |S| ≥ m+1 for every metric basis S. A metric basis Smust contain all the pendant vertices but at most one. Suppose that {α1, . . . , αm−1} ⊂ Sand αm∈ S(if {α1, . . . , αm} ⊂ S, the result clearly follows). Since no pendant vertex resolves the pair {(0,1), (1,0)}, then there is a vertex, say u∈R((0,1), (1,0)) =Q2((0,1)) ∪Q4((1,0)). Without loss of generality, suppose that u∈Q2((0,1)). Then the pair {αm, (1,0)}is not resolved by any vertex in the set {α1, . . . , αm−1,u}and so |S| ≥ m+1. Therefore, dim(Hℓ,m)=m+1. Mimicking the proof of Claim A, only replacing αby α1, . . . , αm−1and βby αm(compare Fig. 3(a) and (b)) it is proved that dim+(Hℓ,m)=m+2ℓ−4.  Claims A and Bgive a connected graph Gwith dim(G)=aand dim+(G)=bwhenever a=2 and bis even (G∼ =Hℓfor ℓ=(b+2)/2) or a>2 and b−ais odd (G∼ =Hℓ,mfor ℓ=2+(b−a+1)/2 and m=a−1). In order to obtain the graph Gin the remaining cases, we modify slightly the graphs Hℓand Hℓ,mby removing the set of vertices {(x1,x2)|x1=ℓ−1}. Denote by ˜ Hℓand ˜ Hℓ,mthe resulting graphs. Note that a (ℓ −1)×ℓgrid, say ˜ Gℓ, plays now the role of Gℓbut all the tools developed above can also be applied in this case. Hence, one can follow the proofs of Claims A and Bto compute the metric dimension and the upper dimension of ˜ Hℓand ˜ Hℓ,m. There are only three changes: 1. Take the set {(0,0), (ℓ −2,0)}as a metric basis of ˜ Gℓ. 2. Remove the vertex (ℓ −2, ℓ −1)from Sobtaining a minimal resolving set of size 2ℓ−3 (for ˜ Hℓ) or 2ℓ+m−5 (for ˜ Hℓ,m). 1446 D. Garijo et al. / Discrete Applied Mathematics 161 (2013) 1440–1447 3. Apply the column version of Lemma 3.4 to get |S\ {α}| ≤ 2(ℓ −2)or |S\ {α1, . . . , αm−1}| ≤ 2(ℓ −2)which directly gives |S| ≤ 2ℓ−3 (for ˜ Hℓ) or |S| ≤ 2ℓ+m−5 (for ˜ Hℓ,m). Thus, we have that dim(˜ Hℓ)=2, dim+(˜ Hℓ)=2ℓ−3,dim(˜ Hℓ,m)=m+1 and dim+(˜ Hℓ,m)=m+2ℓ−5. Therefore, we obtain a graph Gwith dim(G)=aand dim+(G)=bwhenever a=2 and bis odd (G∼ =˜ Hℓfor ℓ=2+(b−1)/2) or a>2 and b−ais even (G∼ =˜ Hℓ,mfor ℓ=3+(b−a)/2 and m=a−1).  3.2. The resolving number In Section 3.1, we have proved that every pair a,bof integers with 2 ≤a≤bis realizable as the metric dimension and the upper dimension, respectively, of a certain graph. Modifying slightly the above constructions, one can easily prove that every pair a,bis realizable as the metric dimension and the upper dimension, respectively, of an infinite family of graphs. It suffices to replace the vertex (0,0)in Gℓby a path of arbitrary length. If the resulting graph plays the role of Gℓin the study developed in the previous subsection, then the values of the metric dimension and the upper dimension are preserved. Theorem 3.7 below says that no integer a≥4 is realizable as the resolving number of an infinite family of graphs (note that the path P2is the only graph with resolving number 1 but there are infinite families of graphs with resolving number 2 and 3, concretely, odd cycles and paths for a=2 and even cycles for a=3). In order to prove this result, we first relate the resolving number to the diameter of a graph, which is of independent interest. Proposition 3.6. Let G be a graph with diameter d(G)and resolving number res(G)≥3. If G is not an even cycle, then d(G)≤3res(G)−5. Proof. Let us denote r=res(G). Suppose on the contrary that d(G) > 3r−5. Then, we can assume that there are two vertices u, v ∈V(G)such that d(u, v) =3r−4=3(r−1)−1. Consider a shortest u–vpath P= {u=u1,u2,...,u3(r−1)=v|ui is adjacent to ui+1}, and suppose that there is a vertex w∈ Padjacent to some vertex uiwith i= 1,3(r−1)(otherwise it can be easily checked that {u1,...,ur}is not a resolving set). Clearly, every vertex uj∈Pdoes not resolve either {w, ui−1}or {w, ui}or {w, ui+1}. Indeed, assume i≤j(analogous for i>j). By Observation 2.3,ujdoes not resolve at least one pair among those formed by the vertices ui−1,ui,ui+1, w. Moreover, the pairs {ui−1,ui},{ui−1,ui+1}and {ui,ui+1}are all resolved by uj, since Pis a shortest path. Thus, one pair among {w, ui−1},{w, ui},{w, ui+1}is not resolved by uj. Consider now the sets A= {uj∈P|d(uj, w) =d(uj,ui−1)},B= {uj∈P|d(uj, w) =d(uj,ui)}and C= {uj∈ P|d(uj, w) =d(uj,ui+1)}. By the argument above, A∪B∪C=P. Furthermore, |P| = 3(r−1)and |A|,|B|,|C| ≤ r−1 (since these sets are not resolving sets of G) and so |A|=|B|=|C| = r−1. This implies that A,Band Care pairwise disjoint but ui∈A∩C; a contradiction.  Observe that when res(G)≤2 or Gis an even cycle, the bound of Proposition 3.6 does not hold. It suffices to consider the path P2(for res(G)=1), an odd cycle of length at least 5 (for res(G)=2) and an even cycle of length at least 6 (for res(G)=3). Theorem 3.7. For every integer a ≥4, the set of graphs with resolving number a is finite. Proof. A graph Gof order n, diameter d(G)and metric dimension dim(G)satisfies the following relation [8]: n≤d(G)dim(G)+dim(G). Since dim(G)≤res(G)then n≤d(G)res(G)+res(G). By Proposition 3.6, we obtain n≤(3res(G)−5)res(G)+res(G)=(3a−5)a+a. This upper bound for ndepends only on the value of aand so the result follows.  4. Concluding remarks and open questions In this paper, we have settled in the affirmative a conjecture posed by Chartrand et al. [3] claiming that every pair a,b of integers with 2 ≤a≤bis realizable as the metric dimension and the upper dimension, respectively, of some connected graph. We have also shown that, surprisingly, the set of graphs with given resolving number a≥4 is always finite, and we have characterized the randomly k-dimensional graphs, avoiding the brute force case analysis. It would be interesting to study the realization of triples a,b,cof integers as the metric dimension, the upper dimension and the resolving number, respectively, of some connected graph. Also, the question of bounding the size of the set of graphs (may be restricting to specific families) with given resolving number aremains open. It would be also interesting to provide a polynomial upper bound on nin terms of the resolving number since we believe that the exponential upper bound given in the proof of Theorem 3.7 is not tight. 1447 Acknowledgements We thank two anonymous referees for their many useful suggestions and comments, which helped to improve the paper substantially. The first and second authors were partially supported by JA-FQM164. The third author was partially supported by the ESF EUROCORES programme EuroGIGA ComPoSe IP04 MICINN Project EUI-EURC-2011-4306, and JA-FQM164. References [1] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, D.R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math. 21 (2) (2007) 423–441. [2] G. Chartrand, Linda Eroh, Mark A. Johnson, Ortrud R. Ollermann, Resolvavility in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113. [3] G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000) 19–28. [4] G. Chartrand, P. Zhang, On the chromatic dimension of a graph, Congr. Numer. 145 (2000) 97–108. [5] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195. [6] M. Jannesari, B. Omoomi, Characterization of randomly k-dimensional graphs, 2011. arxiv.org/abs/1103.3570v1. [7] M. Jannesari, B. Omoomi, On randomly k-dimensional graphs, Appl. Math. Lett. 24 (2011) 1625–1629. [8] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. [9] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.