图的限制边连通度是经典边连通度的推广，可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到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.
[1] Dankelmann P, Meierling D. Maximally edge-connected hypergraphs[J]. Discrete Mathematics, 2016, 339(1):33-38.
[2] Esfahanian A H, Hakimi S L. On computing a conditional edge connectivity of a graph[J]. Information Processing Letters, 1988, 27(4):195-199.
[3] Wang Y Q, Li Q. Super edge connectivity properties of graphs with diameter 2[J]. Journal of Shanghai Jiaotong University, 1999, 33(6):646-649.
[4] Hellwig A, Volkmann L. Sufficient conditions for λ'-optimality in graphs of diameter 2[J]. Discrete Mathematics, 2004, 283(1):113-120.
[5] Hellwig A, Volkmann L. Sufficient conditions graphs to be λ'-optimal, super-edge-connected and maximally edge-connected[J]. Journal of Graph Theory, 2005, 48(3):228-246.
[6] Balbuena C, García-Vázquez P, Marcote X. Sufficient conditions for λ'-optimality in graphs with girth g[J]. Journal of Graph Theory, 2010, 52(1):73-86.
[7] Hellwig A, Volkmann L. Maximally edge-connected graphs and digraphs-a survey[J]. Discrete Mathematics, 2008, 308(15):3265-3296.
[8] Chartrand G. A graph-theoretic approach to a communication problem[J]. SIAM Journal on Applied Mathematics, 1966, 14(4):778-781.
[9] Plesník J. Critical graphs of given diameter[J]. Acta Facultatis Rerum Naturalium Universitatis Comenianae, 1975, 30:71-93.
