超图的限制边连通度与最优限制边连通  

The restricted edge-connectivity and λ’-optimality of hypergraphs

作　　者：童林肯 单而芳[2] TONG Linken;SHAN Erfang(Department of Mathematics,Shanghai University,Shanghai 200444,China;School of Management,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学数学系,上海200444 [2]上海大学管理学院,上海200444

出　　处：《运筹学学报》2020年第4期145-152,共8页Operations Research Transactions

基　　金：国家自然科学基金(No.11971298)。

摘　　要：设H=(V,F)是顶点集为V,超边集为E的连通超图。对H的边子集S,若H\S不连通而且不含孤立点,则称S是H的一个限制边割。把H中最小限制边割的基数称为H的限制边连通度,记为λ’(H)。对边e,其边度是指在H中与e相交的超边的数目,H中最小边度记为ξ(H)。如果λ’(H)=ξ(H),那么称超图H是最优限制边连通的,简记为λ’-最优。研究超图H的限制边连通度和λ’-最优,推广了图上关于限制边连通度和λ’-最优的一些结论。Let H=(V,E)be a connected hypergraph consisting of a vertex set V and an edge set E.For S⊆E(H),S is a restricted edge-cut,if H\S is disconnected and there are no isolated vertices in H\S.The restricted edge-connectivity,denoted byλ’(H),is defined as the minimum cardinality over all restricted edge-cuts.The edgedegree dH(e)of an edge e∈E(H)is defined as the number of edges adj acent to e,and the minimum edge-degree of H is denoted byξ(H).The hypergraph H is calledλ’-optimal,ifλ’(H)=ξ(H).In this paper,we consider the restricted edge-connectivity andλ’-optimality of hypergraphs and generalize some results on the restricted edge-connectivity andλ’-optimality of graphs to hypergraphs.

关 键 词：超图 限制边连通度 最优限制边连通性 

分 类 号：O221[理学—运筹学与控制论]