Rebuilding convex sets in graphs

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