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.
PEI Jianfeng, LIN Shangwei
. Two sufficient conditions for maximally restricted-edge-connected hypergraphs[J]. Operations Research Transactions, 2019
, 23(2)
: 120
-126
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.012
[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.
