English

运筹学学报 >

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

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

超图的限制边连通度与最优限制边连通

展开
  • 1. 上海大学数学系, 上海 200444;
    2. 上海大学管理学院, 上海 200444

收稿日期: 2018-01-29

  网络出版日期: 2020-11-18

基金资助

国家自然科学基金（No.11971298）

收起

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

摘要

设H=（V，E）是顶点集为V，超边集为E的连通超图。对H的边子集S，若H\S不连通而且不含孤立点，则称S是H的一个限制边割。把H中最小限制边割的基数称为H的限制边连通度，记为λ'（H）。对边e，其边度是指在H中与e相交的超边的数目，H中最小边度记为ξ（H）。如果λ'（H）=ξ（H），那么称超图H是最优限制边连通的，简记为λ'-最优。研究超图H的限制边连通度和λ'-最优，推广了图上关于限制边连通度和λ'-最优的一些结论。

关键词： 超图; 限制边连通度; 最优限制边连通性

本文引用格式

童林肯, 单而芳 . 超图的限制边连通度与最优限制边连通[J]. 运筹学学报, 2020 , 24(4) : 145 -152 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.04.013

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

参考文献

[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
文章导航

/

〈 〉