关键词: 一致线性超图, 限制边连通度, 最小度, 直径

Abstract: 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.

Key words: uniform and linear hypergraphs, restricted edge-connectivity, minimum degree, diameter