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

Disc e e Applied Ma hema ics On he me ic dimension, he uppe dimension and he esol ing numbe o g aphs Delia Ga ijo∗, An onio González, Albe o Má quez Dep . de Ma emá ica Aplicada I, Uni e sidad de Se illa, Spain Keywo ds: Resol ing se Me ic dimension Uppe dimension Resol ing numbe abs ac This pape deals wi h h ee esol ing pa ame e s: he me ic dimension, he uppe dimen- sion and he esol ing numbe . We i s answe a ques ion aised by Cha and and Zhang asking o a cha ac e iza ion o he g aphs wi h equal me ic dimension and esol ing num- be . We also sol e in he a i ma i e a conjec u e posed by Cha and, Poisson and Zhang abou he ealiza ion o he me ic dimension and he uppe dimension. Finally, we p o e ha no in ege a≥4 is ealizable as he esol ing numbe o an in ini e amily o g aphs. 1. In oduc ion In his pape , we s udy esol ing se s o ini e simple connec ed g aphs. They we e in oduced in he 1970s independen ly by Sla e [9], and Ha a y and Mel e [5]. The use ulness o hese se s comes om hei mul iple applica ions in se e al a eas, among hem: coin weighing p oblems, ne wo k disco e y and e i ica ion, obo na iga ion, s a egies o Mas e mind game and pha maceu ical chemis y (we e e he eade o [1] o a numbe o e e ences on his opic). Resol ing se s a e o mally de ined as ollows. Le G=(V(G), E(G)) be a ini e simple connec ed g aph o o de n= |V(G)|. The dis ance d(u, ) be ween wo e ices u, ∈V(G)is he leng h o a sho es u– pa h in G. A e ex u∈V(G) esol es a pai {x,y} ⊂ V(G)i d(u,x)= d(u,y). A se o e ices S⊆V(G)is a esol ing se o Gi e e y pai o e ices o Gis esol ed by some e ex o S. A esol ing se S o minimum size is a me ic basis, and |S|is he me ic dimension o G, deno ed by dim(G). Ou aim is no only o deal wi h me ic bases and me ic dimension bu also wi h wo o he esol ing pa ame e s de ined by Cha and e al. [3], namely he uppe dimension and he esol ing numbe , ha gi e an insigh o how la ge he se o esol ing se s o a g aph is. A esol ing se So Gis minimal i no p ope subse o Sis a esol ing se . An uppe basis is a minimal esol ing se con aining he maximum numbe o e ices. The uppe dimension dim+(G)is he size o an uppe basis. The esol ing numbe es(G)is he minimum ksuch ha e e y k-subse o V(G)is a esol ing se o G. Fo ins ance, dim+(Pn)= es(Pn)= 2,dim+(Cn)=2 and es(Cn)=3 whe e Pnand Cndeno e, espec i ely, a pa h o o de n≥4 and a cycle o e en o de n≥4 [3]. Clea ly, e e y (n−1)-subse o V(G)is a esol ing se and e e y esol ing se con ains a minimal esol ing se . Hence, 1≤dim(G)≤dim+(G)≤ es(G)≤n−1. ∗Co esponding au ho . Tel.: +34 954552795; ax: +34 954556683. E-mail add esses: [email p o ec ed] (D. Ga ijo), [email p o ec ed] (A. González), [email p o ec ed] (A. Má quez). D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 1441 When dim(G)= es(G)=k, he g aph Gis called andomly k-dimensional, i.e., e e y k-subse o V(G)is a me ic basis and so Ghas he maximum numbe o me ic bases o a ixed size k. Cha and and Zhang [4] posed he p oblem o cha ac e izing he andomly k-dimensional g aphs. They sol ed he case k≤2, ob aining he comple e g aphs K1and K2( o k=1) and odd cycles ( o k=2), and lea ing open he main ollowing ques ion. P oblem 1.1 ([4]).A e he e andomly k-dimensional g aphs o he han comple e g aphs and odd cycles? Conce ning he h ee pa ame e s, Cha and e al. [3] in es iga ed di e en ques ions ela ed o g aph ealiza ion. In pa icula , hey p o ed ha e e y pai a,bo in ege s wi h 2 ≤a≤bis ealizable as he me ic dimension and he esol ing numbe , espec i ely, o some connec ed g aph G. I was also shown he analogous esul o dim(G)=dim+(G)=aand es(G)=b. Mo eo e , he au ho s p o ed ha e e y pai among he h ee pa ame e s can di e by an a bi a ily la ge numbe . Finally, i was ema ked ha he e we e easons o belie e ha e e y pai a,bo in ege s wi h 2 ≤a≤bis ealizable as he me ic dimension and he uppe dimension, espec i ely, o some connec ed g aph. Thus, hey p oposed he ollowing conjec u e. Conjec u e 1.2 ([3]).Fo e e y pai a,b o in ege s wi h 2≤a≤b, he e exis s a connec ed g aph G wi h dim(G)=a and dim+(G)=b. In his pape , we sol e P oblem 1.1 (Theo em 2.5) and se le in he a i ma i e Conjec u e 1.2 (Theo em 3.5). We also show ha , unlike he me ic dimension and he uppe dimension, no in ege a≥4 is ealizable as he esol ing numbe o an in ini e amily o g aphs (Theo em 3.7). 2. Randomly k-dimensional g aphs In his sec ion, we cha ac e ize he andomly k-dimensional g aphs. While p epa ing his pape , we ha e lea n o [6], whe e he au ho s p o e he same esul . He e we p esen an al e na i e, sho e p oo . We s a wi h some echnical lemmas needed o he case k=3. Deno e by Pλ(G) he λ-subse s o V(G)and le Ni(u)be he se o e ices a dis ance i om u∈V(G). Fo {u, },{x,y} ∈ P2(G)we say ha he pai {u, } esol es he pai {x,y}i ei he uo esol es i . In gene al, T∈Pλ(G) esol es a pai {x,y}i he e is a e ex in T ha esol es i . Lemma 2.1. Le G be a andomly 3-dimensional g aph. Then, he ollowing s a emen s hold. (a) Fo e e y pai {u, } ∈ P2(G) he e exis unique pai s {x,y},{ ,s} ∈ P2(G)such ha {x,y}is no esol ed by {u, }, and {u, }is no esol ed by { ,s}. (b) E e y e ex u ∈V(G)sa is ies  1≤i≤ecc(u)|Ni(u)| 2=n−1 (1) whe e by con en ion 1 2=0, and ecc(u)deno es he eccen ici y o u, i.e., he maximum dis ance om u o any o he e ex. P oo . To p o e S a emen (a), conside a g aph G e i ying ha dim(G)= es(G)=3. Fo e e y pai P= {u, } ∈ P2(G), conside he se SP= {{x,y} | Pdoes no esol e {x,y}} ⊂ P2(G). Since dim(G)=3 hen SPis non-emp y. Mo eo e , SP∩SP′= ∅ whene e P= P′. Indeed, suppose on he con a y ha he e is a pai {x,y} esol ed by nei he P= {u, }no P′= {u′, ′}, and assume ha u, = u′. Then he se {u, , u′}is no a me ic basis, which is a con adic ion. The e o e, SP∩SP′= ∅. Thus, |SP| = 1 o e e y P∈P2(G). This p o es ha o e e y pai {u, } he e is a unique pai {x,y}such ha {u, }does no esol e {x,y}. Fu he , he map ϕ:P2(G)→P2(G) gi en by ϕ(P)=SPis well-de ined and injec i e (whe e by abuse o no a ion, we conside SP∈P2(G)). Then ϕis a bijec ion and so he e is a unique pai { ,s}which does no esol e {u, }. Hence, S a emen (a) ollows. Conside now he se Suo non- esol ed pai s by a e ex u∈V(G). As a consequence o S a emen (a) we ha e |Su| = n−1 (i su ices o conside he n−1 dis inc pai s {u, }wi h ∈V(G) {u}). On he o he hand, a pai {x,y} ∈ Sui and only i x,y∈Ni(u) o i=d(x,u)=d(y,u). Hence, |Su| =  1≤i≤ecc(u)|Ni(u)| 2 which p o es S a emen (b).  Gi en u∈V(G), conside he pa i ion P(u)= {Ni(u)|0≤i≤ecc(u)}o V(G)in o classes (whe e N0(u)= {u}). Lemma 2.1(b) says ha he e is a compensa ion be ween e ices o V(G) {u}and pai s o e ices loca ed in he same class o P(u). Fo ins ance, classes o size a leas 4 always con ibu e o Eq. (1) wi h mo e pai s han e ices (6 pai s and 1442 D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 4 e ices in case o size 4) and so hey ha e o be compensa ed wi h classes o size a mos 2 whose con ibu ion is bigge in e ms o e ices han in pai s. No e ha classes o size 3 which con ibu e wi h 3 pai s, a e sel -compensa ed. The e o e, we ha e he ollowing lemma. Lemma 2.2. Le u ∈V(G)and le P(u)= {Ni(u)|0≤i≤ecc(u)}be a pa i ion o V (G)in o classes wi h N0(u)= {u}. Then, he ollowing s a emen s hold. (a) I P(u)con ains a class o size a leas 4 hen i con ains a leas wo classes o size a mos 2di e en han N0(u). (b) I P(u)con ains a class o size a mos 2di e en han N0(u) hen i con ains a class o size a leas 4. The ollowing s aigh o wa d obse a ion will be use ul o he p oo s o his pape . Obse a ion 2.3 ([8]).Le u, , w ∈V(G)such ha { , w} ∈ E(G)and d(u, ) =d. Then, d(u, w) ∈ {d−1,d,d+1}. Lemmas 2.1 and 2.2 a e he key ools o a oid he case analysis in he cha ac e iza ion o he andomly 3-dimensional g aphs. P oposi ion 2.4. I a g aph G is andomly 3-dimensional hen G is he comple e g aph on 4 e ices. P oo . Fi s , obse e ha Gdoes no con ain e ices o deg ee 1 (Lemma 1 o [7]). Indeed, i a e ex uhas a unique neighbou , hen he pai {u, }is esol ed by e e y e ex o G, which con adic s Lemma 2.1(a). Claim 1. The deg ee o e e y e ex o G is a mos 3. P oo o Claim 1. Suppose on he con a y ha he e is a e ex u∈V(G)o deg ee a leas 4, and le u1,u2,u3,u4∈N1(u). By Lemma 2.1(a), each se Aij = { ∈V(G)|d( , ui)=d( , uj)}wi h 1 ≤i<j≤4 con ains exac ly wo e ices o G. Le ∈V(G)such ha d(u, ) =d. By Obse a ion 2.3,d( , ui)∈ {d−1,d,d+1}and so he se {d( , ui)|1≤i≤4}has a mos 3 elemen s which implies ha belongs o a leas one o he six se s Aij. Hence, n≤7 since u∈Aij o all i,j. Conside now he pa i ion P(u)in which N1(u)is a class o size a leas 4. By Lemma 2.2(a), he e a e a leas wo classes o size a mos 2 di e en han N0(u). Fu he , n≤7 and so he e a e exac ly h ee classes o size 1 in P(u)(one being N0(u)) which implies ha he u hes e ex om uhas deg ee 1; a con adic ion. The e o e, e e y e ex o Ghas deg ee a mos 3.  Claim 2. n∈ {4,7,10}. P oo o Claim 2. Since dim(G)=3, hen Gis nei he a pa h no a cycle and so he e is a e ex u∈V(G)o deg ee 3 wi h neighbou s, say u1,u2,u3. A guing as in he p oo o Claim 1, de ining he analogous se s Aij bu o he e ices u,u1,u2,u3, we ha e n≤10 since e e y se con ains exac ly wo e ices o G,ubelongs o h ee o hem, and e e y e ex o Gbelongs o a leas one o he six se s. The se s {u}and {u1,u2,u3}a e he classes N0(u)and N1(u), espec i ely, in he pa i ion P(u). I his pa i ion does no con ain mo e classes, hen n=4. O he wise, by Lemma 2.2, he e a e h ee possibili ies o P(u): (1) one class o size 4 and wo classes o size 1 (plus N0(u)and N1(u)); (2) N0(u)and h ee classes o size 3 (one being N1(u)); (2) N0(u)and wo classes o size 3 (one being N1(u)). This gi es n=10 o n=7.  Claim 3. The e is no e ex o deg ee 2. P oo o Claim 3. Suppose on he con a y ha he e is a e ex u∈V(G)o deg ee 2. Then, |N1(u)| = 2. By Lemma 2.2, P(u)con ains a class o size a leas 4 and ano he class o size a mos 2 di e en han N0(u). Since n≤10, we ha e he ollowing wo possibili ies o P(u): (1) one class o size 4, wo classes o size 1 (one being N0(u)) and one class o size 2; (2) one class o size 4, one class o size 1 (being N0(u)) and wo classes o size 2. This gi es, espec i ely, n=8 and n=9 con adic ing Claim 2. The h ee p e ious claims p o e ha a g aph Go o de nsa is ying dim(G)= es(G)=3 is 3- egula and n∈ {4,7,10}. Clea ly, n= 7 since he e is no 3- egula g aph wi h 7 e ices. Conside now wo e ices u, ∈V(G)such ha d(u, ) =d(G), whe e d(G)deno es he diame e o G, and le N1(u)= {u1,u2,u3}. By Obse a ion 2.3, he dis ance om o e e y e ex o he se {u,u1,u2,u3}is ei he d(G)o d(G)−1. Hence, belongs o a leas wo o he six se s Aij as de ined in he p oo o Claim 2. By Lemma 2.1(a), each se con ains exac ly wo e ices o Gand ubelongs o h ee o hem. This gi es n<10 and so n=4, which implies ha Gis isomo phic o he comple e g aph K4( he only 3- egula g aph on 4 e ices).  Now, we each he desi ed cha ac e iza ion ha sol es P oblem 1.1. Theo em 2.5. A g aph G is andomly k-dimensional i and only i G is a comple e g aph o an odd cycle. D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 1443 P oo . I Gis isomo phic o a comple e g aph o an odd cycle, i is s aigh o wa d o p o e ha Gis andomly k-dimensional. Suppose now ha Gis a g aph o o de nsa is ying dim(G)= es(G)=k. As was said be o e he case k≤2 was p o ed in [4], ob aining he comple e g aphs K1and K2( o k=1) and odd cycles ( o k=2). Mo eo e , P oposi ion 2.4 p o es he esul o k=3 and so we can assume k≥4. A guing as in he p oo o Lemma 2.1(a) we ha e ha o e e y T∈Pk−1(G), he non-emp y se ST= {{x,y} | Tdoes no esol e {x,y}} ⊂ P2(G) e i ies ha ST∩ST′= ∅ whene e T= T′. The e o e |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 ha Gis isomo phic o he comple e g aph Kn, which is he only g aph o o de nwi h me ic dimension n−1 [2].  3. Realiza ion 3.1. The me ic dimension and he uppe dimension This subsec ion is de o ed o se le in he a i ma i e Conjec u e 1.2. In o de o do his, we compu e he uppe dimension o wo amilies o g aphs o which he me ic dimension is easily ob ained. These g aphs a e cons uc ed om he g id g aphs a aching a he o igin ei he a iangle o a numbe o pendan e ices. We s a wi h some no a ion and echnical lemmas. Le Gℓbe he g id g aph o o de ℓ×ℓwi h ℓ≥2, whose e ex se is he Ca esian p oduc [0, ℓ −1]×[0, ℓ −1]and dis ances gi en by d((x1,x2), (y1,y2)) = |x1−y1|+|x2−y2|. We shall use (x1,x2) o indica e he coo dina es o a e ex x∈V(Gℓ)(analogously, y=(y1,y2), z=(z1,z2), e c.). The ollowing se s o e ices a e called quad an s o 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 he se s Di= {x∈V(Gℓ)|x1+x2=i}wi h 0 ≤i≤2ℓ−2 a e he diagonals o Gℓ(see Fig. 1(a)). A pai o e ices {x,y}is said o be a diagonal pai i x,y∈Di o some i. No e ha a quad an Qi(x)migh be equal o {x}and he e is a o al o de <iin each diagonal Di(o simply ‘‘<’’ when no con usion can a ise) gi en by x<iy⇐⇒ x1<y1. In he sequel we shall assume, wi hou loss o gene ali y, ha he o de o he wo elemen s o a diagonal pai {x,y}is x<y(analogously, <s o { ,s}o <z o { ,z}). Le R(x,y)be he se o e ices o Gℓ ha esol e he pai {x,y} ⊂ V(Gℓ), and le Sbe a esol ing se o Gℓ. No e ha he se R(x,y)∩Sis non-emp y o e e y pai {x,y}. Lemma 3.1. Le {x,y}be a diagonal pai such ha d(x,y)=2. Then, R(x,y)=Q2(x)∪Q4(y). P oo . Fo e e y e ex u∈Q2(x), he e is a sho es u−ypa h going h ough xand so d(u,y)=d(u,x)+d(x,y)= d(u,x)+2. Thus, u esol es {x,y}(analogous o u∈Q4(y)). Le u∈V(Gℓ) (Q2(x)∪Q4(y)), z=(x1,y2)and ˜ z=(y1,x2). Clea ly, he e a e wo sho es pa hs P1and P2joining u o xand u o y, espec i ely, such ha ei he z∈P1,P2o ˜ z∈P1,P2(see Fig. 1(b)). Since z,˜ zdo no esol e he pai {x,y} hen u∈ R(x,y). Gi en a esol ing se So Gℓ, a pai {x,y}is said o be S-unique i he e is a unique e ex u∈S esol ing {x,y}, i.e., R(x,y)∩S= {u}. The e ex uand he pai {x,y}a e said o be associa ed o each o he . The ollowing obse a ion is s aigh o wa d. Obse a ion 3.2. Le S be a esol ing se o Gℓ, and le {x,y}be an S-unique pai wi h associa ed e ex u. I he e is a pai { ,s} such ha R( ,s)⊆R(x,y) hen { ,s}is S-unique wi h associa ed e ex u. No e ha necessa ily u ∈R( ,s). Lemma 3.3. Le S be a esol ing se o Gℓ, and le {x,y}={(x1,x2), (y1,y2)}be an S-unique diagonal pai wi h associa ed e ex u such ha d(x,y) > 2. Then, he e exis exac ly y1−x1S-unique diagonal pai s { ,s}wi h associa ed e ex u and d( ,s)=2. 1444 D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 Fig. 1. (a) Quad an s o xand a diagonal Di, (b) he shadowed egion illus a es Q2(x)∪Q4(y), and he do ed edges o m he pa hs P1and P2. Fig. 2. (a) All he e ices in he shadowed egion plus he wo squa ed e ices do no esol e he pai {x,y}, (b) he shadowed egion illus a es R(x,y). P oo . A simila a gumen as in he p oo o Lemma 3.1, conside ing z=(x1,y2)and ˜ z=(y1,x2), gi es ha e e y e ex u∈Q3(z)∪Q1(˜ z)does no esol e he pai {x,y}. Clea ly, he e ices (x1+j,y2+j)wi h 0 <j<y1−x1do no esol e he pai {x,y}ei he (see Fig. 2(a)). Thus, he exp ession o R(x,y)in his case is R(x,y)=V(Gℓ) (Q3(z)∪Q1(˜ z)∪ {(x1+j,y2+j)|0<j<y1−x1}). This se can also be exp essed as ollows: R(x,y)= 0≤j<y1−x1 R( j,sj) whe e j=(x1+j,y2+j+1), sj=(x1+j+1,y2+j)and d( j,sj)=2 (see Fig. 2(b)). Since R( j,sj)⊆R(x,y),Obse a ion 3.2 p o es he esul .  Two diagonal pai s {x,y},{ ,s}such ha d(x,y)=d( ,s)=2 a e said o be in he same ow i x2= 2and y2=s2. Analogously, hey a e in he same column i x1= 1and y1=s1. Lemma 3.4. Le S be a esol ing se o Gℓ, and le {x,y}be an S-unique diagonal pai wi h associa ed e ex u such ha d(x,y)=2. I he e exis wo S-unique diagonal pai s { ,s},{ ,z}in he same ow (column) han {x,y}wi h associa ed e ices, espec i ely, and wand u = , w, hen =w. P oo . Suppose ha he pai s { ,s},{ ,z}a e in he same ow (analogous o columns) han {x,y}, i.e., x2= 2= 2and y2=s2=z2. Assume also ha x1< 1< 1. Clea ly, R( ,s)⊂(R(x,y)∪R( ,z)) and so =wsince = u. Now, we each ou main esul in his subsec ion which se les in he a i ma i e Conjec u e 1.2. Theo em 3.5. Fo e e y pai a,b o in ege s wi h 2≤a≤b, he e exis s a connec ed g aph G wi h dim(G)=a and dim+(G)=b. P oo . Le Hℓbe he g aph ob ained om Gℓwi h ℓ≥2, by a aching a iangle a e ex (0,0), i.e., V(Hℓ)=V(Gℓ)∪ {α, β} and E(Hℓ)=E(Gℓ)∪ {{α, β},{α, (0,0)},{β, (0,0)}} (see Fig. 3(a)). Obse e ha dis ances in Hℓbeha e as in Gℓ, excep o he new e ices αand β o which d(α, x)=d(β, x)=x1+x2+1 o e e y x=(x1,x2)∈V(Gℓ). Thus, he p e ious lemmas can be applied o he g aph Hℓ. Claim A. dim(Hℓ)=2and dim+(Hℓ)=2ℓ−2. D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 1445 Fig. 3. (a) A minimal esol ing se o Hℓo size 2ℓ−2, (b) a minimal esol ing se o Hℓ,mo size m+2ℓ−4. P oo o Claim A. I is well-known ha dim(Gℓ)=2 he se {(0,0), (ℓ −1,0)}being a me ic basis (see o ins ance [8]). This se can be adap ed o a me ic basis o Hℓby conside ing {α, (ℓ −1,0)}. Hence, dim(Hℓ)=2. To p o e ha dim+(Hℓ)≥2ℓ−2 one can easily check ha he se S= {(x1,x2)|1≤x1≤ℓ−2,x2∈ {x1,x1+1}} ∪ {(0,1), α} is a esol ing se o Hℓo size 2ℓ−2. Mo eo e , Sis minimal because emo ing ei he a e ex (x1,x1)o (x1,x1+1) om Sgi es ha ei he he pai {(x1,x1), (x1−1,x1+1)}o he pai {(x1,x1+1), (x1+1,x1)}is no esol ed by any elemen o S. Clea ly, (0,1)and αcanno be emo ed om S.Fig. 3(a) illus a es his minimal esol ing se . We nex p o e ha dim+(Hℓ)≤2ℓ−2. Le Sbe a minimal esol ing se o Hℓ. Conside he pai {α, β}which is only esol ed by ei he αo β. Wi hou loss o gene ali y, we assume ha α∈Sand β∈ S. Since Sis minimal, e e y e ex u∈Shas an associa ed S-unique pai , say p(u). Obse e ha {β, (0,0)}is no an S-unique pai (e e y e ex o Gℓ esol es i ) and so he e is no e ex u∈Sso ha p(u)= {β, (0,0)}. Also no e ha α esol es all he non-diagonal pai s o Gℓ. Hence, e e y e ex u∈S {α}has an associa ed S-unique diagonal pai p(u). Mo eo e , by Lemma 3.3, we can assume ha he elemen s o p(u)a e a dis ance 2 om each o he . Le us conside all hese S-unique pai s. By Lemma 3.4, o all pai s o he same ow (o column), he e a e a mos wo dis inc e ices associa ed o hese pai s. Mo eo e , we claim ha he e is a mos one such e ex in he i s ow (and he i s column). Indeed, by Lemma 3.1 we ha e R((0,1), (1,0)) =Q2((0,1)) ∪Q4((1,0)) = {(0,x2)|1≤x2≤ ℓ−1}∪{(x1,0)|1≤x1≤ℓ−1}. Suppose ha he e is a e ex ∈S∩Q2((0,1)) (analogous o ∈S∩Q4((1,0)) by symme y). Since all he pai s in he same ow as {(0,1), (1,0)}a e esol ed by and Sis minimal, hen he e is no o he e ex o Sassocia ed o pai s in such ow. Hence, in o al, since he e a e ℓ−1 ows (and columns), he e a e a mos 2(ℓ −2)+1S-unique pai s ha can be associa ed o he e ices o S {α}, and hus |S {α}| = |S| − 1≤2(ℓ −2)+1.  Conside now he g aph Hℓ,mob ained om Gℓwi h ℓ≥3 by a aching a se o m≥2 pendan e ices {α1, . . . , αm}a (0,0)(see Fig. 3(b)). Claim B. dim(Hℓ,m)=m+1and dim+(Hℓ,m)=m+2ℓ−4. P oo o Claim B. As was said be o e, he se {(0,0), (ℓ−1,0)}is a me ic basis o Gℓ[8]. Thus, i can be easily checked ha he se {α1, . . . , αm, (ℓ −1,0)}is a esol ing se o Hℓ,m, which gi es dim(Hℓ,m)≤m+1. To p o e ha dim(Hℓ,m)≥m+1, i su ices o show ha |S| ≥ m+1 o e e y me ic basis S. A me ic basis Smus con ain all he pendan e ices bu a mos one. Suppose ha {α1, . . . , αm−1} ⊂ Sand αm∈ S(i {α1, . . . , αm} ⊂ S, he esul clea ly ollows). Since no pendan e ex esol es he pai {(0,1), (1,0)}, hen he e is a e ex, say u∈R((0,1), (1,0)) =Q2((0,1)) ∪Q4((1,0)). Wi hou loss o gene ali y, suppose ha u∈Q2((0,1)). Then he pai {αm, (1,0)}is no esol ed by any e ex in he se {α1, . . . , αm−1,u}and so |S| ≥ m+1. The e o e, dim(Hℓ,m)=m+1. Mimicking he p oo o Claim A, only eplacing αby α1, . . . , αm−1and βby αm(compa e Fig. 3(a) and (b)) i is p o ed ha dim+(Hℓ,m)=m+2ℓ−4.  Claims A and Bgi e a connec ed g aph Gwi h dim(G)=aand dim+(G)=bwhene e a=2 and bis e en (G∼ =Hℓ o ℓ=(b+2)/2) o a>2 and b−ais odd (G∼ =Hℓ,m o ℓ=2+(b−a+1)/2 and m=a−1). In o de o ob ain he g aph Gin he emaining cases, we modi y sligh ly he g aphs Hℓand Hℓ,mby emo ing he se o e ices {(x1,x2)|x1=ℓ−1}. Deno e by ˜ Hℓand ˜ Hℓ,m he esul ing g aphs. No e ha a (ℓ −1)×ℓg id, say ˜ Gℓ, plays now he ole o Gℓbu all he ools de eloped abo e can also be applied in his case. Hence, one can ollow he p oo s o Claims A and B o compu e he me ic dimension and he uppe dimension o ˜ Hℓand ˜ Hℓ,m. The e a e only h ee changes: 1. Take he se {(0,0), (ℓ −2,0)}as a me ic basis o ˜ Gℓ. 2. Remo e he e ex (ℓ −2, ℓ −1) om Sob aining a minimal esol ing se o size 2ℓ−3 ( o ˜ Hℓ) o 2ℓ+m−5 ( o ˜ Hℓ,m). 1446 D. Ga ijo e al. / Disc e e Applied Ma hema ics 161 (2013) 1440–1447 3. Apply he column e sion o Lemma 3.4 o ge |S {α}| ≤ 2(ℓ −2)o |S {α1, . . . , αm−1}| ≤ 2(ℓ −2)which di ec ly gi es |S| ≤ 2ℓ−3 ( o ˜ Hℓ) o |S| ≤ 2ℓ+m−5 ( o ˜ Hℓ,m). Thus, we ha e ha dim(˜ Hℓ)=2, dim+(˜ Hℓ)=2ℓ−3,dim(˜ Hℓ,m)=m+1 and dim+(˜ Hℓ,m)=m+2ℓ−5. The e o e, we ob ain a g aph Gwi h dim(G)=aand dim+(G)=bwhene e a=2 and bis odd (G∼ =˜ Hℓ o ℓ=2+(b−1)/2) o a>2 and b−ais e en (G∼ =˜ Hℓ,m o ℓ=3+(b−a)/2 and m=a−1).  3.2. The esol ing numbe In Sec ion 3.1, we ha e p o ed ha e e y pai a,bo in ege s wi h 2 ≤a≤bis ealizable as he me ic dimension and he uppe dimension, espec i ely, o a ce ain g aph. Modi ying sligh ly he abo e cons uc ions, one can easily p o e ha e e y pai a,bis ealizable as he me ic dimension and he uppe dimension, espec i ely, o an in ini e amily o g aphs. I su ices o eplace he e ex (0,0)in Gℓby a pa h o a bi a y leng h. I he esul ing g aph plays he ole o Gℓin he s udy de eloped in he p e ious subsec ion, hen he alues o he me ic dimension and he uppe dimension a e p ese ed. Theo em 3.7 below says ha no in ege a≥4 is ealizable as he esol ing numbe o an in ini e amily o g aphs (no e ha he pa h P2is he only g aph wi h esol ing numbe 1 bu he e a e in ini e amilies o g aphs wi h esol ing numbe 2 and 3, conc e ely, odd cycles and pa hs o a=2 and e en cycles o a=3). In o de o p o e his esul , we i s ela e he esol ing numbe o he diame e o a g aph, which is o independen in e es . P oposi ion 3.6. Le G be a g aph wi h diame e d(G)and esol ing numbe es(G)≥3. I G is no an e en cycle, hen d(G)≤3 es(G)−5. P oo . Le us deno e = es(G). Suppose on he con a y ha d(G) > 3 −5. Then, we can assume ha he e a e wo e ices u, ∈V(G)such ha d(u, ) =3 −4=3( −1)−1. Conside a sho es u– pa h P= {u=u1,u2,...,u3( −1)= |ui is adjacen o ui+1}, and suppose ha he e is a e ex w∈ Padjacen o some e ex uiwi h i= 1,3( −1)(o he wise i can be easily checked ha {u1,...,u }is no a esol ing se ). Clea ly, e e y e ex uj∈Pdoes no esol e ei he {w, ui−1}o {w, ui}o {w, ui+1}. Indeed, assume i≤j(analogous o i>j). By Obse a ion 2.3,ujdoes no esol e a leas one pai among hose o med by he e ices ui−1,ui,ui+1, w. Mo eo e , he pai s {ui−1,ui},{ui−1,ui+1}and {ui,ui+1}a e all esol ed by uj, since Pis a sho es pa h. Thus, one pai among {w, ui−1},{w, ui},{w, ui+1}is no esol ed by uj. Conside now he se s 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 he a gumen abo e, A∪B∪C=P. Fu he mo e, |P| = 3( −1)and |A|,|B|,|C| ≤ −1 (since hese se s a e no esol ing se s o G) and so |A|=|B|=|C| = −1. This implies ha A,Band Ca e pai wise disjoin bu ui∈A∩C; a con adic ion.  Obse e ha when es(G)≤2 o Gis an e en cycle, he bound o P oposi ion 3.6 does no hold. I su ices o conside he pa h P2( o es(G)=1), an odd cycle o leng h a leas 5 ( o es(G)=2) and an e en cycle o leng h a leas 6 ( o es(G)=3). Theo em 3.7. Fo e e y in ege a ≥4, he se o g aphs wi h esol ing numbe a is ini e. P oo . A g aph Go o de n, diame e d(G)and me ic dimension dim(G)sa is ies he ollowing ela ion [8]: n≤d(G)dim(G)+dim(G). Since dim(G)≤ es(G) hen n≤d(G) es(G)+ es(G). By P oposi ion 3.6, we ob ain n≤(3 es(G)−5) es(G)+ es(G)=(3a−5)a+a. This uppe bound o ndepends only on he alue o aand so he esul ollows.  4. Concluding ema ks and open ques ions In his pape , we ha e se led in he a i ma i e a conjec u e posed by Cha and e al. [3] claiming ha e e y pai a,b o in ege s wi h 2 ≤a≤bis ealizable as he me ic dimension and he uppe dimension, espec i ely, o some connec ed g aph. We ha e also shown ha , su p isingly, he se o g aphs wi h gi en esol ing numbe a≥4 is always ini e, and we ha e cha ac e ized he andomly k-dimensional g aphs, a oiding he b u e o ce case analysis. I would be in e es ing o s udy he ealiza ion o iples a,b,co in ege s as he me ic dimension, he uppe dimension and he esol ing numbe , espec i ely, o some connec ed g aph. Also, he ques ion o bounding he size o he se o g aphs (may be es ic ing o speci ic amilies) wi h gi en esol ing numbe a emains open. I would be also in e es ing o p o ide a polynomial uppe bound on nin e ms o he esol ing numbe since we belie e ha he exponen ial uppe bound gi en in he p oo o Theo em 3.7 is no igh . 1447 Acknowledgemen s We hank wo anonymous e e ees o hei many use ul sugges ions and commen s, which helped o imp o e he pape subs an ially. The i s and second au ho s we e pa ially suppo ed by JA-FQM164. The hi d au ho was pa ially suppo ed by he ESF EUROCORES p og amme Eu oGIGA ComPoSe IP04 MICINN P ojec EUI-EURC-2011-4306, and JA-FQM164. Re e ences [1] J. Cáce es, C. He nando, M. Mo a, I.M. Pelayo, M.L. Pue as, C. Sea a, D.R. Wood, On he me ic dimension o ca esian p oduc s o g aphs, SIAM J. Disc e e Ma h. 21 (2) (2007) 423–441. [2] G. Cha and, Linda E oh, Ma k A. Johnson, O ud R. Olle mann, Resol a ili y in g aphs and he me ic dimension o a g aph, Disc e e Appl. Ma h. 105 (2000) 99–113. [3] G. Cha and, C. Poisson, P. Zhang, Resol abili y and he uppe dimension o g aphs, Compu . Ma h. Appl. 39 (2000) 19–28. [4] G. Cha and, P. Zhang, On he ch oma ic dimension o a g aph, Cong . Nume . 145 (2000) 97–108. [5] F. Ha a y, R.A. Mel e , On he me ic dimension o a g aph, A s Combin. 2 (1976) 191–195. [6] M. Jannesa i, B. Omoomi, Cha ac e iza ion o andomly k-dimensional g aphs, 2011. a xi .o g/abs/1103.3570 1. [7] M. Jannesa i, B. Omoomi, On andomly k-dimensional g aphs, Appl. Ma h. Le . 24 (2011) 1625–1629. [8] S. Khulle , B. Ragha acha i, A. Rosen eld, Landma ks in g aphs, Disc e e Appl. Ma h. 70 (1996) 217–229. [9] P.J. Sla e , Lea es o ees, Cong . Nume . 14 (1975) 549–559.