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

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

Abstract

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 d_H(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

CLC Number:

O221

TONG Linken, SHAN Erfang. The restricted edge-connectivity and λ'-optimality of hypergraphs[J]. Operations Research Transactions, 2020, 24(4): 145-152.

References

[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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics

Comments

[1]	ZHAO Jing, SHAN Erfang, ZHAO Jiagui. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131.
[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]	WANG Guoliang, SHI Haizhong. The restricted connectivity of complete-transposition networks [J]. Operations Research Transactions, 2013, 17(3): 57-64.