English

运筹学学报 >

2021 , Vol. 25 >Issue 1: 123 - 131

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

 

最大边连通和super-边连通超图的充分条件

展开
  • 1. 上海大学数学系, 上海 200444
    2. 上海大学管理学院, 上海 200444
    3. 上海公安学院, 上海 200137
赵加贵 E-mail: 416526575@qq.com

收稿日期: 2018-04-04

  网络出版日期: 2021-03-05

基金资助

国家自然科学基金(11971298)

收起

Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected

Expand
  • 1. Department of Mathematics, Shanghai University, Shanghai 200444, China
    2. School of Management, Shanghai University, Shanghai 200444, China
    3. Shanghai Police College, Shanghai 200137, China

Received date: 2018-04-04

  Online published: 2021-03-05

Fold

摘要

设H是连通超图。若超图H的边连通度等于其最小度，则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成，则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次，给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了Dankelmann和Volkmann（1997）以及Hellwig和Volkmann（2005）在图上的相关结论。

关键词： 超图; 边连通度; 最大边连通超图; super-边连通; 度序列最小度

本文引用格式

赵静, 单而芳, 赵加贵 . 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021 , 25(1) : 123 -131 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.012

Abstract

Let H be a connected hypergraph. The hypergraph H is called maximally edge connected if its edge connectivity is equal to minimum degree. The hypergraph H is super-edge-connected, if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree. In this paper we give simple degree sequence conditions for uniform linear hypergraphs to be maximally edge-connected. Also, we give a sufficient condition for uniform linear hypergraphs to be super-edge-connected. These results generalize previous results on graphs due to Dankelmann and Volkmann(1997), Hellwig and Volkmann(2005) to hypergraphs.

Key words： hypergraph; edge connectivity; maximally edgeconnected; degree sequence, super-edge-connected; minimum degree

参考文献

1 Whitney L . Congruent graphs and the connectivity of graphs[J]. American Journal of Mathematics, 1932, 54, 150- 168.
2 Volkmann L . Degree sequence conditions for equal edge-connectivityand minimum degree depending on the clique number[J]. Journal of GraphTheory, 2004, 42, 234- 245.
3 Lü M , Wu C , Chen G . On super connectivity of Cartesian productgraphs[J]. Networks, 2008, 52 (2): 78- 87.
4 Milz S , Volkmann L . Degree sequence conditions for maximallyedge-connected and super-edge-connected digraphs depending on theclique number[J]. Discrete Mathematics, 2018, 341, 484- 491.
5 Hellwig A , Volkmann L . Maximally edge-connected and vertex-connectedgraphs and digraphs: a survey[J]. Discrete Mathematics, 2008, 308, 3265- 3296.
6 Dankelmann P , Volkmann L . Degree sequence conditions for maximallyedge-connected graphs and digraphs[J]. Journal of Graph Theory, 1997, 26, 27- 34.
7 Bollobás B . On graphs with equal edge-connectivity and minimumdegree[J]. Discrete Mathematics, 1979, 28, 321- 323.
8 Hellwig A , Volkmann L . Maximally edge-connected digraphs[J]. The Australasian Journal of Combinatorics, 2003, 27, 23- 32.
9 Hellwig A , Volkmann L . Sufficient conditions for graphs to be λ'-optimal, super-edge-connected and maximallyedge-connected[J]. Journal of Graph Theory, 2005, 48, 228- 246.
10 Dewar M, Pike D, Proos J. Connectivity in hypergraphs[J]. arXiv: 1611.07087.
11 Jami N , Szigeti Z . Edge-connectivity of permutation hypergraphs[J]. Discrete Mathematics, 2012, 312, 2536- 2539.
12 Dankelmann P , Meierling D . Maximally edge-connected hypergraphs[J]. Discrete Mathematics, 2016, 339, 33- 38.
Options
文章导航

/

〈 〉