English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (4): 145-152.doi: 10.15960/j.cnki.issn.1007-6093.2020.04.013

• • 上一篇    下一篇

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

童林肯1, 单而芳2,*   

  1. 1. 上海大学数学系, 上海 200444;
    2. 上海大学管理学院, 上海 200444
  • 收稿日期:2018-01-29 发布日期:2020-11-18
  • 通讯作者: 单而芳 E-mail:efshan@shu.edu.cn
  • 基金资助:
    国家自然科学基金（No.11971298）

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

TONG Linken1, SHAN Erfang2,*   

  1. 1. Department of Mathematics, Shanghai University, Shanghai 200444, China;
    2. School of Management, Shanghai University, Shanghai 200444, China
  • Received:2018-01-29 Published:2020-11-18

PDF

137

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

关键词: 超图, 限制边连通度, 最优限制边连通性

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

中图分类号: