论文摘要
Helly性质是超图理论中很重要的一个概念,因为很多超图类都有Helly性质.一个图具有Helly性质的充要条件是图不含三角形,因而具有Helly性质的超图是不含三角形的图的一种推广。进一步地,Berge和Duchet[13]定义了k-Helly性质并且给出了超图具有此性质的充要条件。因为超图如果具有k-Helly性质,则它的部分超图也具有k-Helly性质,但它的诱导子超图未必具有k-Helly性质,所以本人定义了强k-Helly性质,并给出了它的充要条件。根据此充要条件,当固定k时,我又给出了检验一个超图是否具有强k-Helly性质的多项式算法.下面是我的主要结果:定理1超图H具有强Helly性质,当且仅当对H的任意3个顶点x,y,z,对任意H中的3条边E xy, E xz, E yz,其中{ x , y} ? Exy,{ x , z} ? Exz,{ y , z} ? Eyz,存在v∈{ x , y ,z},使得v∈E xy∩E xz∩Eyz。定理2区间超图具有强Helly性质。定理3平衡超图具有强Helly性质。定理4超图H具有强k-Helly性质的充要条件:对每个顶点子集A,A = k+ 1,存在一个顶点x∈A,使得jx∈E∩∩A≥kEj。定理5设超图H有m条边,最大度为?,上秩为r,H能被时间复杂性为O （ mr 2k? ）的算法检验是否具有强k-Helly性质。定理6若超图H的遗传超图H?具有k-Helly性质,则H是强k-Helly超图.定理7 r部完全超图具有强r-Helly性质。定理8设圈区间超图H的顶点数为n,上秩为r .若n >3r,则H具有强Helly性质.定理9设r-一致圈区间超图H的顶点数为n,且r > n2.若H具有强Helly性质,则m（ H ）≤n ? r+1 .定理10超图H是定义在X上的超图,满足X = n, Ei∩E j≤k, （ ?E i ,E j∈H）则11定理11对s≥2, n≥r≥2s, M 2（ n, r , q , s ） =??? nr ??ss???。