中文

Operations Research Transactions >

2020 , Vol. 24 >Issue 4: 145 - 152

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2020.04.013

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

Expand
  • 1. Department of Mathematics, Shanghai University, Shanghai 200444, China;
    2. School of Management, Shanghai University, Shanghai 200444, China

Received date: 2018-01-29

  Online published: 2020-11-18

Fold

Abstract

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 adjacent 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.

Key words： hypergraph; restricted edge-connectivity; λ'-optimal

Cite this article

TONG Linken, SHAN Erfang . The restricted edge-connectivity and λ'-optimality of hypergraphs[J]. Operations Research Transactions, 2020 , 24(4) : 145 -152 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.04.013

References

[1] Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information Processing Letters, 1988, 27(4):195-199.
[2] Balbuena C, García-Vázquez P, Marcote X. Sufficient conditions for λ'-optimality in graphs with girth g[J]. Journal of Graph Theory, 2006, 52:73-86.
[3] Balbuena C, Lin Y Q, Miller M. Diameter-sufficient conditions for a graph to be super-restricted connected[J]. Discrete Applied Mathematics, 2008, 156:2827-2834.
[4] Hellwig A, Volkmann L. Sufficient conditions for graphs to be λ'-optimal, super-edge-connected, and maximally edge-connected[J]. Journal of Graph Theory, 2005, 48:228-246.
[5] Hellwig A, Volkmann L. Sufficient conditions for λ'-optimality in graphs of diameter 2[J]. Discrete Mathematics, 2004, 283:113-120.
[6] 王应前, 李乔. 图的限制性边连通度等于其最小边度的一个充分条件[J]. 高校应用数学学报, 2001, 16(3):269-275.
[7] Xu J M, Xu K L. Note on restricted edge-connectivity of graphs[J]. Discrete Mathematics, 2002, 243:291-298.
[8] 张国珍. 极大限制边连通网络的充分条件[J]. 计算机工程与应用, 2017, 53(8):19-22.
[9] Zhang Z. Sufficient conditions for restricted-edge-connectivity to be optimal[J]. Discrete Mathematics, 2007, 307(22):2891-2899.
[10] Hellwig A, Volkmann L. Maximally edge-connected and vertex-connected graphs and digraphs-a survey[J]. Discrete Mathematics, 2008, 308:3265-3296.
[11] Bahmanian M A, Šajna M. Connection and separation in hypergraphs[J]. Theory and Applications of Graphs, 2015, 2(2):0-24.
[12] 陈来焕, 刘凤霞, 孟吉翔. 超图的连通度[J]. 新疆大学学报(自然科学版), 2017, 34(1):1-6.
[13] Dankelmann P, Meierling D. Maximally edge-connected hypergraphs[J]. Discrete Mathematics, 2016, 339:33-38.
[14] Jami N, Szigeti Z. Edge-connectivity of permutation hypergraphs[J]. Discrete Mathematics, 2012, 312:2536-2539.
[15] Király Z, Cosh B, Jackson B. Local edge-connectivity augmentation in hypergraphs is NP-complete[J]. Discrete Applied Mathematics, 2010, 158:723-727.
[16] Bretto A. Hypergraph Theory:an Introduction[M]. Berlin:Springer, 2013.
[17] Berge C. Graphs and Hypergraphs[M]. Amsterdam:North-Holland Publishing Co, 1976.
Options
Outlines

/

〈 〉