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.