极大限制边连通超图的两个充分条件

Two sufficient conditions for maximally restricted-edge-connected hypergraphs

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.

The restricted edge-connectivity of a graph is a generalization of the classical edge-connectivity,and can be used to accurately measure the fault tolerance of networks.Maximally restricted-edge-connected graphs are a class of graphs with optimal restricted edge-connectivity.In this paper,we first extend the concepts of the restricted edge-connectivity and the minimum edge degree to r-uniform and linear hypergraphs H,prove that the minimum edge degreeξ(H)of H is an upper bound on its restricted edge-connectivityλ′(H)if its minimum degreeδ(H)≥r+1,and call the hypergraph H withξ(H)=λ′(H)a maximally restricted-edge-connected hypergraph.Next,we show that an r-uniform and linear hypergraph H with order n and minimum degreeδ(H)≥(n-1)/(2(r-1))+(r-1)is maximally restricted-edge-connected.Finally,we prove that an r-uniform and linear hypergraph H with diameter 2 and girth at least 4 is maximally restricted-edge-connected.These results are generalizations of corresponding results in graphs.