discrete89151

《discrete89151》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DISCRETEMATHEMATICSELSEVIERDiscreteMathematics160(1996)2539AHellytheoreminweaklymodularspaceHans-JfirgenBandelta'*,VictorChepoibaMathematischesSeminar,Universit~itHamburg,D-20146Hamburg,GermanyuCatedradeCibernetic~tMatematicgt,UniversitateadeStatdinMoldova,277009Chi~in~u,MoldovaReceived27April1994

2、AbstractThed-convexsetsinametricspacearethosesubsetswhichincludethemetricintervalbetweenanytwoofitselements.Weakmodularityisacertainintervalpropertyfortriplesofpoints.Thed-convexityofadiscreteweaklymodularspaceXcoincideswiththegeodesicconvexityofthegraphformedbythetwo-pointintervalsinX.TheHellynum

3、berofsuchaspaceXturnsouttobethesameasthecliquenumberoftheassociatedgraph.ThisresultthusentailsaHellytheoremforquasi-mediangraphs,pseudo-modulargraphs,andbridgedgraphs.1.IntroductionThewell-knowntheoremofHellysaysthateachfinitefamilyofconvexsetsin~"hasanonemptyintersectionprovidedeachsubfamilyofatm

4、ostn+1setshasnonemptyintersection.Thisresultanditsrelativesformacentralthemeinabstractconvexity[25,27].TheHellynumberofanabstractconvexityisthesmallestnumberh>~2suchthateveryfinitefamilyofconvexsetsmeetinghbyhhasanonemptyintersection.Alowerboundonh(relevantinthecaseofdiscreteconvexities)isthelarge

5、stsizecoofaclique,thatis,amaximalsetwhosesubsetsareallconvex.Thisnumbercoisthencalledthecliquenumber.FortheminimalpathconvexityofagraphHellynumberandcliquenumberareactuallyequal[20,15].Thesameisalsotrueinfiniteconvexgeometries[19].InthecaseofthegeodesicconvexityofgraphstheHellynumberhmaywellexceed

6、thecliquenumberco(the5-cyclebeingthesmallestexample),sothatitisinterestingtofindparticularclasseswhereequalityofthosetwonumbersholds.ChordalgraphsareofthiskindaswasshownbyChepoi[10].Thisresultwasthengeneralizedtodismantlablegraphs[6]aswellastopseudo-modulargraphs[6,14].*Correspondingauthor.0012-36

7、5X/96/$15.00©1996ElsevierScienceB.V.AllrightsreservedSSD!0012-365X(95)00217-026H.-J.Bandelt,KChepoi/DiscreteMathematics160(1996)25-39InthispaperwewillfurtherextendthisHelly-typetheoremforthegeodesicconvexity(alia