Disc e e Ma hema ics 297 (2005) 26–37
www.else ie .com/loca e/disc
Rebuilding con ex se s in g aphs
José Cáce esa,1, Albe o Má quezb,2, O ud R. Oelle mannc,3,
Ma ía Luz Pue asa,4
aDepa men o S a is ics and Applied Ma hema ics, Uni e si y o Alme ia, Spain
bDepa men o Applied Ma hema ics I, Uni e si y o Se ille, Spain
cDepa men o Ma hema ics and S a is ics, The Uni e si y o Winnipeg, 515 Po age A enue, Winnipeg,
Mani oba, Canada R3B 2E9
Recei ed 17 Decembe 2002; ecei ed in e ised o m 18 June 2004; accep ed 1 Ma ch 2005
A ailable online 11 July 2005
Abs ac
Theusualdis ancebe weenpai so e icesinag aphna u allygi es ise o heno iono anin e al
be weenapai o e icesin ag aph.Thisin u nallowsus oex end heno ionso con exse s,con ex
hull, and ex eme poin s in Euclidean space o he e ex se o a g aph. The ex eme e ices o a
g aph a e known o be p ecisely he simplicial e ices, i.e., he e ices whose neighbo hoods a e
comple e g aphs. I is known ha he class o g aphs wi h he Minkowski–K ein–Milman p ope y,
i.e., he p ope y ha e e y con ex se is he con ex hull o i s ex eme poin s, is p ecisely he class
o cho dal g aphs wi hou induced 3- ans.We define a e ex o be a con ou e ex i he eccen ici y
o e e y neighbo is a mos as la ge as ha o he e ex. In his pape we show ha e e y con ex
se o e ices in a g aph is he con ex hull o he collec ion o i s con ou e ices. We cha ac e ize
hose g aphs o which e e y con ex se has he p ope y ha i s con ou e ices coincide wi h i s
ex eme poin s.A se o e ices in a g aph is a geode ic se i he union o he in e als be ween pai s
o e ices in he se , aken o e all pai s in he se , is he en i e e ex se . We show ha he con ou
e ices in dis ance he edi a y g aphs o m a geode ic se .
© 2005 Else ie B.V. All igh s ese ed.
Keywo ds: Eccen ici y; Con ou e ex; Dis ance he edi a y g aph; Con ex hull; Geode ic se
E-mail add ess: o.oelle [email protected] (O. Oelle mann).
1Resea ch suppo ed in pa by FQM 164 g an .
2Resea ch suppo ed in pa by FQM 305 g an .
3Resea ch suppo ed by an NSERC g an Canada.
4Resea ch suppo ed in pa by BFM2001-2474 g an .
0012-365X/$-see on ma e © 2005 Else ie B.V. All igh s ese ed.
doi:10.1016/j.disc.2005.03.020
J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37 27
1. In oduc ion
The s udy o abs ac con exi y began in he ea ly fi ies wi h he sea ch o an axiom
sys em ha defines a con ex se and in some way gene alizes he classical concep o a
Euclidean con ex se . Nume ous con ibu ions o his opic ha e been made. An ex ensi e
su ey o his subjec can be ound in [20].
Among he wide a ie y o s uc u es ha ha e been s udied unde abs ac con exi y a e
me ic spaces, o de ed se s o la ices and g aphs, he las being he ocus o his pape . We
now gi e a b ie in oduc ion o abs ac con exi y as i pe ains o g aphs. Le Vbe a fini e
se and Ma fini e collec ion o subse s o V.Then Mis an alignmen o Vi and only i M
is closed unde in e sec ion and con ains bo h Vand he emp y se . I Mis an alignmen o
V, hen he elemen s o Ma e called con ex se s and he pai (V, M)is called an aligned
space.I S⊆V, hen he con exhullo S, deno ed byCH(S),is he smalles con exse ha
con ains S. Suppose X∈M. Then, x∈Xis an ex eme poin o Xi X−{x}∈M. The
collec ion o all ex eme poin s o Xis deno ed by ex(X).Acon ex geome y on a fini e se
is an aligned space wi h he addi ional p ope y ha e e y con ex se is he con ex hull o
i s ex eme poin s. This p ope y is e e ed o as he Minkowski–K ein–Milman p ope y.
Se e al abs ac con exi ies associa ed wi h he e ex se o a g aph a e well known (see
[10]).Thei s udy is o in e es in compu a ional geome y and has some di ec applica ions
o o he a eas such as, o example, game heo y (see [4]).
Fo g aph e minology we ollow [14]; excep ha we use e ex ins ead o poin and
edge ins ead o line. All g aphs conside ed he e a e connec ed, fini e, simple, unweigh ed
and undi ec ed. The dis ance be ween a pai o e ices u, o Gis he leng h o a sho es
u– pa h in Gand is deno ed by dG(u, ) o d(u, ) i Gis clea om con ex . The in e al
be ween a pai u, o e ices in a g aph Gis he collec ion o all e ices ha lie on some
sho es u– pa h in Gand is deno ed by IG[u, ]o I[u, ]i Gis unde s ood. In e als
in g aphs ha e been s udied ex ensi ely (see [2,17,18]) and play an impo an ole in he
s udy o se e al classes o g aphs such as he P olemaic g aphs (see [16]) o block g aphs.
A subse So e ices o a g aph is said o be g-con ex i i con ains he in e al be ween
e e y pai o e ices in S. I is no di ficul o see ha he collec ion o all g-con ex se s is
an alignmen o V. We hus e e o he g-con ex se s simply as con ex se s.A e ex in a
g aph is simplicial i i s neighbo hood induces a comple e subg aph. I can eadily be seen
ha pis an ex eme poin o a con ex se Si and only i pis simplicial in he subg aph
induced by S. I is ue, in gene al, ha he con ex hull o he ex eme poin s o a con ex
se Sis con ained in S, bu equali y holds only in special cases. In [10] i is shown ha a
g aph has he Minkowski–K ein–Milman p ope y i and only i i has no induced cycles
o leng h bigge han 3 and has no induced 3- an (see Fig. 1). Fo ano he mo e ecen and
excellen e e ence ex con aining ma e ial on g aph con exi y see [6].
I a g aph Ghas he Minkowski–K ein–Milman p ope y and Sis a con ex se o V (G),
hen we can ebuild he se S om i s ex eme e ices using he con ex hull ope a ion.
Since his canno be done wi h e e y g aph, using only he ex eme e ices o a gi en
con ex se S, i is na u al o ask i i is possible o ex end he se o ex eme e ices o S o
a se ha allows us o ebuild Susing he e ices in his ex ended se and he con ex hull
ope a ion. In Sec ion 2 we answe his ques ion in he a fi ma i e using he collec ion o
‘con ou e ices’o a se . To his end, le Sbe a se o e ices in a g aph Gand ecall ha
28 J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37
c
b
d
a
Fig. 1. A 3- an.
he eccen ici y in So a e ex u∈Sis gi en by eccS(u) =max{d(u, ) : ∈S}and a
e ex ∈S o which d(u, ) =eccS(u) is called an eccen ic e ex o uin S. In case
S=V (G), we deno e eccS(u) by ecc(u). A e ex u∈Sis said o be a con ou e ex o
Si eccS(u)⩾eccS( ) o e e y neighbo o uin S. The se o all con ou e ices o S
is called he con ou se o Sand is deno ed by C (S).I S=V (G), he subg aph induced
by he con ou se o Sis called he con ou o Gand is deno ed by C (G). In Sec ion 3 we
es ablish s uc u al p ope ies o con ou e ices and cha ac e ize hose g aphs ha a e he
con ou o some o he g aph using a cons uc ion simila o he one used in [3].
In o de o find he con ex hull o a se Sone begins by aking he union o he in e als
be ween pai s o e ices o S, aken o e all pai s o e ices in S. We deno e his se by
IG[S]o I[S], i.e., I[S]={u, }⊆SI[u, ]and call i he geode ic closu e o S. One hen
epea s his p ocedu e wi h he new se and con inues un il, o he fi s ime, one eaches a
se T o which he geode ic closu e is he se i sel , i.e., T=I[T]. This hen is he con ex
hull o S. I his p ocedu e only has o be pe o med once, we say ha he se Sis a geode ic
se o i s con ex hull. In gene al a subse So a con ex se Tisageode ic se o Ti
I[S]=T. The no ion o a geode ic se o he e ex se o a g aph was fi s defined in [7].
InSec ion4we ocusongeode icse sin‘dis ancehe edi a yg aphs’.Wefi s discusshe e
how heseg aphsa e ela ed o heg aphswi h he Minkowski–K ein–Milmanp ope y and
how he esul s o Sec ion 4 ex end esul s known o he las class. Howo ka [15] defined
a connec ed g aph G o be dis ance he edi a y i o e e y connec ed induced subg aph
Ho Gand e e y wo e ices u, in H,dH(u, ) =dG(u, ). In he same pape se e al
cha ac e iza ions o his class o g aphs a e gi en. We s a e he e only one o hese which
we will use in his pape .
Theo em 1. A connec ed g aph Gis dis ance he edi a y i and only i e e y cycle in G
o leng h a leas 5has a pai o c ossing cho ds.
Fu he use ul cha ac e iza ions o his class o g aphs we e es ablished in [1,9,13].
Apa omha ingelegan cha ac e iza ions,dis ancehe edi a yg aphspossesso he use ul
p ope ies. I is a class o g aphs o which se e al NP-ha d p oblems ha e polynomial
solu ions. Fo example he S eine p oblem o g aphs, which is known o be NP-ha d
(see [11]), can be sol ed in polynomial ime in dis ance he edi a y g aphs (see [5,8,12]).
Mo eo e , hese g aphs a e S eine dis ance he edi a y as was shown in [9]; i.e., he S eine
dis ance o a se o e ices is he same, in any connec ed induced subg aph ha con ains
i , as i is in he g aph i sel .
J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37 29
The class o dis ance he edi a y g aphs also p ope ly con ains he g aphs ha possess he
Minkowski–K ein–Milman p ope y since a g aph is cho dal wi hou an induced 3- an i
and only i i is a dis ance he edi a y g aph wi hou an induced 4-cycle. I was shown in [10]
ha in a cho dal g aph e e y non-simplicial e ex lies on a cho dless pa h be ween wo
simplicial e ices. I Gis a cho dless g aph wi hou an induced 3- an, hen Gis dis ance
he edi a y and hus e e y induced pa h is necessa ily a sho es pa h. Hence he simplicial
e ices o a con ex se Sin a g aph wi h he Minkowski–K ein–Milman p ope y is a
geode ic se o S. In Sec ion 4 we show ha he con ou e ices o a dis ance he edi a y
g aph o m a geode ic se o he g aph. In [19] i shown ha he con ou e ices can be
used o find minimum S eine geode ic se s o dis ance he edi a y g aphs.
2. The con ou se o a g aph
In his sec ion we will show ha he con ou se o a con ex se So e ices in a g aph
Gcan be used o ebuild he se by finding i s con ex hull, in he same way ha ex eme
e ices a e used in cho dal g aphs in [10]. Mo eo e , we cha ac e ize hose g aphs ha ing
he p ope y ha he ex eme e ices and he con ou e ices o e e y con ex se coincide.
Fi s we show ha he con ou se o Gcon ains all he ex eme e ices.
Lemma 2. Le Gbe a g aph and S⊆V (G).Then C (S) con ains all ex eme e ices
o S.
P oo . Le u∈Sbe an ex eme e ex o S. Then uis a simplicial e ex o S.Wenow
show ha uis a con ou e ex o S. Le be a neighbo o uin Sand e∈San eccen ic
e ex o in S, i.e., d( , e)=eccS( ). Suppose ha d(u, e)=d( , e)−1 and le
Pbe a sho es u– epa h. Then he e ex ollowing uon P, say w,isno . Since uis
simplicial, and wmus be adjacen . Howe e , hen d(u, e)⩾d( , e), a con adic ion.
So eccS(u)⩾d(u, e)⩾d( , e)=eccS( ) and he e o e uis a con ou e ex o S.
The ela ionshipbe weencon ou e icesandex eme e icesise enclose o heclass
o dis ance he edi a y g aphs wi hou induced 4-cycles.The nex esul is a cha ac e iza ion
o con ou e ices in g aphs wi h he Minkowski–K ein–Milman p ope y ha esembles
he cha ac e iza ion o simplicial e ices.
P oposi ion 3. Le Gbe a dis ance he edi a y g aph wi hou induced 4-cycles. A e ex
x∈V (G) is acon ou e ex o Gi and only i eachneighbo o xwhichis on asho es
pa h be ween xand some eccen ic e ex o xsa isfies N[x]⊆N[ ].
P oo . I Gis comple e, he esul is immedia e. Suppose now ha Gis no comple e. Then
no con ou e ex o Gcan ha e eccen ici y 1. So i xis a con ou e ex and xeis an
eccen ic e ex o x, hen d(x,xe)⩾2. Le P:(x=)y0y1...y
k(=xe)be a sho es x–xe
pa h. Suppose u= y1is a neighbo o x. Then uis no on Pand uP canno be a sho es
u–xepa h; o he wise, ecc(u) > ecc(x) which is no possible since xis a con ou e ex.
Since Gis dis ance he edi a y, he subg aph induced by uand he e ices o Pcon ains a
30 J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37
sho es u–xepa h. Hence he e is a cho d be ween uand some e ex on Pwhose dis ance
om xis less han o equal o 2. I uy1is a cho d, hen u∈N(y1)as desi ed. I uis a
neighbo o y2, hen he 4-cycle xy1y2ux mus ha e a cho d. So uy1is an edge and again
u∈N(y1).
Con e sely, suppose ha xhas he p ope y ha each o i s neighbo s which is on a
sho es pa h be ween xand some eccen ic e ex o xsa isfies N[x]⊆N[ ]. Suppose x
has a neighbo ysuch ha ecc(x) < ecc(y). Then xlies on a sho es pa h Pbe ween yand
an eccen ic e ex ye o y.Soyeis also an eccen ic e ex o x. By ou hypo hesis yis
a neighbo o he e ex adjacen o xin P−y. This is no possible as Pis a sho es y–ye
pa h. So ecc(y)⩽ecc(x) and xis a con ou e ex o G.
Rema k 4. The abo e esul does no hold o all cho dal g aphs. Take o example he
3- ano Fig.1. Fo hisg aphbo h heneighbo s, o ei he oneo he wosimplicial e ices,
lieonsomesho es pa h oaneccen ic e exbu hei closedneighbo hoodsa eno equal.
Howe e , he con e se o he abo e esul holds o all connec ed g aphs G, i.e., i a e ex
x∈V (G) has he p ope y ha o each neighbo o xwhichis ona sho es pa h be ween
xand some eccen ic e ex o x,N[x]⊆N[ ], hen xis a con ou e ex.
The ollowing esul shows ha he con ex hull o he con ou se o a con ex se o
e ices in a g aph is he en i e se , wi hou any es ic ion on he g aph. So his esul is
simila o he Minkowski–K ein–Milman p ope y and holds o all g aphs.
Theo em 5. Le Gbe a g aph and Sa con ex subse o e ices. Then S=CH(C (S)).
P oo . Suppose, o hecon a y, ha S= CH(C (S)).SinceSisacon exse ,CH(C (S)) ⊆
S. So, by ou assump ion, S−CH(C (S)) =∅. Le u∈S−CH(C (S)) be such ha
ecc(u)⩾ecc( ) o all ∈S−CH(C (S)). Since u/∈C (S), he e exis s a neighbo
o uin Ssuch ha eccS( ) > eccS(u) and, by ou choice o u, he e ex belongs o
CH(C (S)).
Le e∈Sbe an eccen ic e ex o in S, i.e., d( , e)=eccS( ). No e ha in his
case eccS( e)⩾eccS( ) > eccS(u) and e∈CH(C (S)). The e o e d(u, e)⩽eccS(u) <
eccS( ) =d( , e)and so d(u, e)+1⩽d( , e).
Le Pbe a sho es e–upa h in S.Then P ollowed by he edge u ,isa e– pa h whose
leng h is d(u, e)+1⩽d( , e). So i is a sho es pa h be ween eand ha con ains u.
This con adic s he ac ha u/∈CH(C (S)).
In g aphs wi h he Minkowski–K ein–Milman p ope y, he se o ex eme e ices o a
con ex se Sis minimal in he sense ha any ex eme poin o Sis no in he con ex hull
o a subse o S ha does no con ain i . Un o una ely he con ou se does no sha e his
p ope y in gene al as can be seen in he example o Fig. 1. In his case he con ou is he
se {a, b, c, d}, bu CH({a,b,d})=CH({a, b, c, d}).
Howe e , he e a e examples whe e he con ou e ices a e a minimal se in a simila
way ha ex eme e ices a e. In he g aph o Fig. 2 wi h S=V (G), he con ou se is
C (S) ={a, b, c, d}and he con ex hull o any p ope subse o C (S) is a p ope subse
o S.

J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37 31
acbd
Fig. 2. G aph wi h a minimal con ou .
u
w
x
y
Fig. 3. A da .
We now cha ac e ize hose connec ed g aphs o which e e y con ex se has he p ope y
ha i s con ou e ices coincide wi h i s ex eme poin s.
Theo em 6. A connec ed g aph Ghas he p ope y ha C (S) =ex(S) o all con ex se s
So e ices o Gi and only i Ghas he Minkowski–K ein–Milman p ope y and does no
con ain a da as induced subg aph (see Fig. 3).
P oo . SupposeGhas he p ope y ha C (S)=ex(S) o all con exse sSo e iceso G.
Le Sbe any con ex se o G.Then we know ha Sis he con ex hull o i s con ou e ices.
SinceC (S)=ex(S) i ollows ha Sis also hecon exhull o i sex eme e ices.HenceG
has heMinkowski–K ein–Milmanp ope y.The e o eGischo dalwi hou induced3- ans.
Hence Gis dis ance he edi a y wi hou induced 4-cycles. Suppose Ghas a da as induced
subg aph.Label he e iceso suchada asinFig.3.Le Xbe he e icesinI[u, ]−{u, }.
Then he subg aph Xinduced by Xis comple e; o he wise, Ghas an induced 4-cycle,
con adic ing he ac ha Gis cho dal.Also i x∈X, hen {u, w, y, x, } is a connec ed
subg aph o Gand since Gis dis ance he edi a y i con ains a sho es w– pa h as well as
a sho es y– pa h. Hence wx,yxa e edges o G.Sowand ya e adjacen o e e y e ex
in X. Since d(w,y) =2, i ollows ha I[y,w]−{w, y} is a comple e g aph. Suppose
I[w, y]con ains e ices no in X∪{u}, say u∈I[w, y]−(X ∪{u}). Then d(u, )=2.
Since Gcon ains no induced 4-cyclesI[u, ]−{u, } is comple e. I I[u, ]=X,
hen he e is some e ex such ha u /∈E(G) bu u , ∈E(G). Hence uu is an
induced u– pa h o leng h 3. This con adic s he ac ha Gis dis ance he edi a y. Thus
S=CH({u, , w, y, x})=I[w, y]∪I[u, ]. Hence all e ices o Sexcep hose in Xa e
con ou e ices o S. This con adic s he hypo hesis since uis a con ou e ex o S ha
is no an ex eme poin o S, i.e., uis no simplicial.
32 J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37
Fo he con e se, suppose Ghas he Minkowski–K ein–Milman p ope y and does no
con ain a da as induced subg aph. Suppose Sis a con ex se ha has a con ou e ex
u ha is no simplicial. Then Sis no comple e and uis adjacen wi h a pai w, y o
non-adjacen e ices. Le X=N(u) ∩I[u, ]. Since Ghas he Minkowski–K ein–Milman
p ope y i can be shown ha Xis comple e. So wand ycanno bo h belong o I[u, ].I
∈(N(u)−I[u, ]), hen mus be adjacen oe e y e exinXsinceuis acon ou e ex
o Gand since Gis dis ance he edi a y. So nei he wno ybelongs o X.I uu1u2...u
e=
is a sho es u– pa h in G, hen e⩾2 and nei he wno yis adjacen wi h u2. Hence
{u, w, y, u1,u
2} is isomo phic o a da , con a y o hypo hesis. Thus C (S) =ex(S).
Cha ac e izing g aphs G o which C (G) =ex(G) appea s much mo e di ficul . Any
connec ed g aph His an induced subg aph o a g aph Gwi h his p ope y. To see his,
ake |V(H)|pai wise e ex disjoin , non- i ial cliques and pai o each e ex o Hin a
one- o-one manne wi h one o hese cliques. Now iden i y each e ex o Hwi h exac ly
one e exin heclique ha i hasbeenpai edo wi h and le Gbe he esul ingg aph.Then
Ghas he p ope y ha C (G) =ex(G). I ollows ha hose g aphs o which he con ou
se and he collec ion o ex eme poin s coincide can ha e induced cycles o a bi a ily la ge
o de . Howe e , no e e y g aph wi h his p ope y can be cons uc ed in his manne . Take
o example he g aph ob ained om he 6-cycle 1,
2,...,
6,
1by joining a lea u1 o
1and a lea u4 o 4. Then he esul ing g aph Ghas he p ope y ha C (G) =ex(G) bu
Gis no ob ained by he abo e cons uc ion.
3. G aphs wi h a gi en con ou se
In hissec ionwecha ac e ize hoseg aphswhicha e hecon ou o someo he g aph.The
ob ious ela ionshipbe weencon ou andpe iphe al e icesallowus ouse hecons uc ion
used in [3] o also cha ac e ize hose g aphs ha a e he con ou o some g aph.
Lemma 7. Le Gbe a connec ed g aph and Ca componen o i s con ou . Then all e ices
in Cha e he same eccen ici y.
The ollowing esul ells us which g aphs a e no he con ou o any g aph.
P oposi ion 8. I His a connec ed,non-comple e g aph wi h adius 1, hen His no he
con ou o any g aph.
P oo . Le Hbe a connec ed, non-comple e g aph wi h adius 1. Then some e ex u∈
V(H)is a neighbo o e e y o he e ex in H. Since His no comple e he e a e wo non-
adjacen e ices and .Suppose he eexis sag aphGsuch ha His hesubg aphinduced
by i s con ou .Then Gmus be connec ed, since His connec ed. So, using Lemma 7, e e y
e ex in Hhas he same eccen ici y, say k. No e ha ecc( )⩾2, because dG( , )=2,
so k⩾2.
Le w∈V (G) be such ha ecc(u) =d(u, w) =k. Then w/∈C (G), since k⩾2.
So he e exis s a neighbo w1o wsuch ha ecc(w1)>ecc(w)⩾k. Again w1/∈C (G),
J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37 33
H1
Hi
H
k
2 M
Fig. 4. A disconnec ed con ou se .
because i s eccen ici y is bigge han k. So he e exis s a neighbo w2o w1such ha
ecc(w2)>ecc(w1)>k. This p ocess canno con inue indefini ely since Gis a fini e g aph.
Howe e , hen he las e ex picked should be a con ou e ex. Since i s eccen ici y is
bigge han kwe ha e a con adic ion. 
Suppose ha His a g aph wi h adius g ea e han 1. We now desc ibe a g aph Gsuch
ha i s con ou is H, using he cons uc ion gi en in [3]. Le Gbe he join o Hand K1.
Then e e y e ex o Hhas eccen ici y 2 and he e ex o G−V(H)has eccen ici y 1.
Hence he e ices o Ha e p ecisely he con ou e ices o G.
A sligh ly di e en cons uc ion allows us o ob ain a g aph wi h gi en disconnec ed
con ou se such ha he eccen ici ies o he e icesine e ycomponen a e gi ennumbe s
a leas 2.Mo ep ecisely,le Hbeadisconnec edg aphwi hcomponen s,H1,H
2,...,H
k.
Le n1,n
2,...,n
kbe kna u al numbe s such ha n1=nk=max{n1,n
2,...,n
k}and M=
max{n1,n
2,...,n
k}⩽2min{n1,n
2,...,n
k}=2m. No e ha hese a e na u al es ic ions,
because Mwill be he diame e o he g aph Gand mwill be g ea e han o equal o he
adius. Then he e exis s a connec ed g aph Gsuch ha His he con ou o Gand he
eccen ici y o e e y e ex in each componen Hio His equal o ni. To cons uc such
a g aph Gwe begin wi h he pa h 1 2...
M+1o o de M+1. Now eplace 1by H1
and M+1by Hkso ha all e ices in H1a e neighbo s o 2and all e ices in Hka e
neighbo s o M.
Now, o each i,2⩽i⩽k−1, he eexis sa e ex nion hepa hsuch ha i seccen ici y
is ni−1. We now add Hi o he g aph and join all he e ices o Hi o ni(see Fig. 4).
Then ecc(ui)=ni o all ui∈Hi,andC (G) =H.
4. Con ou se s and geode ic se s in dis ance he edi a y g aphs
In his sec ion we show ha he con ou e ices o a dis ance he edi a y g aph o m a
geode ic se . I is no di ficul o see ha a se So e ices is a con ex se o a dis ance
he edi a y g aph Gi and only i Sinduces a connec ed g aph and is he union o e ices in
blocks o Gminus any collec ion o simplicial e ices om he subg aph induced by hese
blocks. The esul s o his sec ion hus show ha he con ou e ices o all con ex se s in
dis ance he edi a y g aphs a e geode ic se s o such se s.As poin ed ou in he in oduc ion
his may be iewed as an ex ension o he esul which s a es ha he simplicial e ices o
con ex se s in g aphs wi h he Minkowski–K ein–Milman p ope y a e a geode ic se o
he con ex se .
34 J. Cáce es e al./Disc e e Ma hema ics 297 (2005) 26–37
The nex esul shows ha i Gis a dis ance he edi a y g aph, hen e e y e ex has an ec-
cen ic e ex ha isacon ou e ex.Mo eo e ,i Gsa isfies heMinkowski–K ein–Milman
p ope y and i xis a e ex o G, wi h ecc(x)⩾2, hen e e y eccen ic e ex o xmus be
a con ou e ex.
Lemma 9. (1) I Gis adis ance he edi a yg aphandx∈V (G), hen he eis an eccen ic
e ex o x ha is a con ou e ex.
(2) Le Gbe a dis ance he edi a y g aph wi hou induced 4-cycles. I x∈V (G) is such
ha ecc(x)⩾2, hen each eccen ic e ex o xis a con ou e ex o G.
P oo . (1) The esul holds o all dis ance he edi a y g aphs wi h diame e a mos 2.
Suppose hus ha diam(G)⩾3. Among all eccen ic e ices o xle xebe one wi h
maximum eccen ici y. Le P:x= 0 1...
k=xebe a sho es x–xepa h. We show xe
is a con ou e ex. I his is no he case, hen xeis adjacen wi h some e ex uwhose
eccen ici y exceeds ha o xe.Thus ecc(u) > ecc(xe)⩾ecc(x) =k.Soecc(u)⩾3. We may
assume ulies on Pand ha u= k−1. Suppose ueis an eccen ic e ex o u.Then he e is
a sho es u–uepa h Q ha con ains xe. Suppose Q:u=u0u1...u
=uewhe e u0= k−1.
Thenu2isno onP.Also clea ly uu2/∈E(G).Theonly e exon P ha u2may be adjacen
ois k−2. Indeed u2 k−2isan edge; o he wise,ecc(x)⩾d(x,u2)>k.Since ecc( k−1)⩾3,
u2mus be adjacen o a e ex no on P.I u3is adjacen wi h a e ex o Pi can only be
adjacen wi h k−3; o he wise, ei he d( k−1,u
3)= 3o d(x, k)= k. Howe e , i u3 k−3
is an edge, we ha e a 6-cycle k−3 k−2 k−1 ku2u3wi hou c ossing cho ds, which is no
possible in a dis ance he edi a y g aph. So u3 k−3/∈E(G) and d( 0,u
3)=k. By ou choice
o xe= k,3⩽ecc(u3)⩽ecc( k)<ecc( k−1).Soecc( k−1)⩾4 and hence u4is no on P.
As be o e we can a gue ha he only e ex o P ha u4is possibly adjacen o is k−4.I
u4 k−4∈E(G), henasbe o eweob aina6-cycle k−4 k−3 k−2u2u3u4 k−4whichhasno
c ossing cho ds. So u4 k−4/∈E(G). Howe e , hen d(x,u4)=k+1>ecc(x) which is no
possible. So u= k−1. No e uis no adjacen wi h k−i o i⩾3; o he wise, d(x,xe)<k,
whichisno possible.Also k−2u∈E(G);o he wise,we ha ea con adic ion oou choice
o xe= k.I k−1u∈E(G), hen u2is no on P. No e ha in his case u2is adjacen wi h
a mos one e ex on P, namely, k−2.Sou3is no on P.Fo i⩾3, uicanno be on Psince
in his case ei he d(x, k)<k o d(u, ui)<i, bo h o which canno happen. Mo eo e ,
he only e ex on P ha uican be adjacen wi h (i any) is k−i; o he wise, as in he
p e ious case, we ha e a con adic ion. I u3 k−3∈E(G), hen k−3 k−2 k−1 ku2u3 k−3
is a 6-cycle wi hou c ossing cho ds. So u3 k−3/∈E(G). In his case u2 k−3∈E(G) and
d(x,u3)=k. So by ou choice o xe= k,ecc(u3)⩽ecc( k)<ecc(u)⩽ecc(u ).So3< .
I u4 k−4∈E(G), hen k−4 k−3 k−2u2u3u4 k−4is a 6-cycle wi hou c ossing cho ds. So
u4 k−4/∈E(G). Bu hen d(x,u4)=k+1 con adic ing he ac ha ecc(x) =k. Hence we
may assume k−1u/∈E(G).
I u2= k−1, i.e., u2is no on P, hen a leas one o u2 k−2and u2 k−1is an edge o G.
I u2 k−2/∈E(G), we ha e a 5-cycle wi h ou c ossing cho ds. So assume u2 k−2∈E(G).
Fo i⩾3 we may a gue, as be o e, ha uiis no on Pand ha uiis adjacen o a mos
one e ex on P, namely, k−i. Bu hen, as in he p e ious case, we ha e a con adic ion
o he ac ha ecc( ) =k. So we may assume k−1=u2. Clea ly, u3= k−2since
d(u, u3)=3= d(u, k−2). Indeed, o i⩾3, uiis no on Pand uiis adjacen wi h a mos