Some Topics On Strong K-Helly Hypergraphs

The Helly property is of the most important concepts in hypergraph theory because mang hypergraph classes have the property.A graph has the Helly property if and only if its is triangle-free.Hence hypergraphs with the Helly property have also other properties which generalise those of triangle free graphs.Berge and Duchet have defined the k-Helly property and given the necessary and sufficient condition in the paper [1].If a hypergraph has k-Helly property,its partial hypergraphs also have the k-Helly property,but its induced subhypergraphs do not necessarily have the k-Helly property.We give a polynomial algorithm for checking whether a hypergraph has the strong k-Helly property.The folowing are my main results:Theorem 1 A hypergraph has the strong Helly property if only if for any three vertices x,y,z and any three hyperedges E xy, E xz, E yzof H with { x , y }? Exy,{ x , z }? Exz,{ y , z }? Eyz,there exists v∈{ x , y ,z} such that v∈E xy∩E xz∩Eyz.Theorem 2 The interval hypergraph has the strong Helly property.Theorem 3 The balanced hypergraph has the strong Helly property.Theorem 4 A hypergraph H is strong k-Helly if and only if for every set A of verties with A = k+ 1,there exists x∈Asuch thatTheorem 5 The strong k-Helly property of a hypergraph H with m hyperedges,maximal degree ?and rank r can be tested in ( )O mr 2 k? time.Theorem 6 If the hereditary hypergraph H? satisfies k-Helly property, then H is strong k-Helly hypergraph.Theorem 7 The r-partial hypergraph has strong r-Helly property.Theorem 8 A circular interval hypergraph has n vertices and rank r.If n>3r,H has the strong Helly property.Theorem 9 If r-uniform circular interval hypergraph on n vertices has strong Helly property with then m ( H )≤n ? r+ 1.Theorem 10 Let H be a Hypergraph,which is defined on X , X = n, If Ei∩E j≤k, ( ?E i ,E j∈H) ThenTheorem 11 s≥2, n≥r≥2s,...