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

doi:10.15960/j.cnki.issn.1007-6093.2021.01.012

Operations Research Transactions ›› 2021, Vol. 25 ›› Issue (1): 123-131.doi: 10.15960/j.cnki.issn.1007-6093.2021.01.012

Previous Articles Next Articles

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

Jing ZHAO¹, Erfang SHAN², Jiagui ZHAO³^,*()

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:2018-04-04 Online:2021-03-15 Published:2021-03-05
Contact: Jiagui ZHAO E-mail:416526575@qq.com

Abstract

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

CLC Number:

O157.5

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.

Figures/Tables 2

References 12

1	Whitney L . Congruent graphs and the connectivity of graphs[J]. American Journal of Mathematics, 1932, 54, 150- 168. doi: 10.2307/2371086
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. doi: 10.1002/net.20224
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. doi: 10.1016/j.disc.2017.09.015
5	Hellwig A , Volkmann L . Maximally edge-connected and vertex-connectedgraphs and digraphs: a survey[J]. Discrete Mathematics, 2008, 308, 3265- 3296. doi: 10.1016/j.disc.2007.06.035
6	Dankelmann P , Volkmann L . Degree sequence conditions for maximallyedge-connected graphs and digraphs[J]. Journal of Graph Theory, 1997, 26, 27- 34. doi: 10.1002/(SICI)1097-0118(199709)26:1<27::AID-JGT4>3.0.CO;2-J
7	Bollobás B . On graphs with equal edge-connectivity and minimumdegree[J]. Discrete Mathematics, 1979, 28, 321- 323. doi: 10.1016/0012-365X(79)90139-0
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. doi: 10.1002/jgt.20053
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. doi: 10.1016/j.disc.2011.08.010
12	Dankelmann P , Meierling D . Maximally edge-connected hypergraphs[J]. Discrete Mathematics, 2016, 339, 33- 38. doi: 10.1016/j.disc.2015.07.008

[1]	TONG Linken, SHAN Erfang. The restricted edge-connectivity and λ'-optimality of hypergraphs [J]. Operations Research Transactions, 2020, 24(4): 145-152.
[2]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[3]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[4]	LI Shan, SHAN Erfang, ZHANG Lin. A note on total domination in 5-regular graphs [J]. Operations Research Transactions, 2017, 21(1): 125-128.
[5]	LIN Yi, NI Zhenyu, SHAN Erfang. Total transversals in 5-uniform hypergraphs [J]. Operations Research Transactions, 2016, 20(2): 97-104.
[6]	ZHANG Xinyue, HUANG Zhenghai, LI Zhiming. A face recognition method based on discriminative hypergraph and nonnegative matrix factorization [J]. Operations Research Transactions, 2015, 19(3): 108-115.
[7]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 12

Related Articles 7

Recommended Articles

Metrics

Comments