中文

Operations Research Transactions >

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

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

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

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

Cite this article

Jing ZHAO, Erfang SHAN, Jiagui ZHAO . Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected[J]. Operations Research Transactions, 2021 , 25(1) : 123 -131 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.012

References

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
Outlines

/

〈 〉