The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected. A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree. In this paper, we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs.
Lin-Ken Tong, Er-Fang Shan
. Sufficient Conditions for Maximally Edge-Connected Hypergraphs[J]. Journal of the Operations Research Society of China, 2021
, 9(1)
: 119
-129
.
DOI: 10.1007/s40305-018-0224-4
[1] Whitney, H.:Congruent graphs and the connectivity of a graph. Am. J. Math. 54, 150-168(1932)
[2] Dankelmann, P., Meierling, D.:Maximally edge-connected hypergraphs. Discrete Math. 339, 33-38(2016)
[3] Hellwig, A., Volkmann, L.:Maximally edge-connected graphs and digraphs-a survey. Discrete Math. 308, 3265-3296(2008)
[4] Bahmanian, M.A., Šajna, M.:Connection and separation in hypergraphs. Theory Appl. Graphs 2(2), 1-24(2015)
[5] Berg, A.R., Jackson, B., Jordán, T.:Edge splitting and connectivity augmentation in directed hypergraphs. Discrete Math. 273, 71-84(2003)
[6] Bernáth, A., Grappe, R., Szigeti, Z.:Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph. J. Graph Theory 72, 291-312(2012)
[7] Dewar, M., Pike, D., Proos, J.:Connectivity in hypergraphs. Canad. Math. Bull. 61, 252-271(2018)
[8] Jami, N., Szigeti, Z.:Edge-connectivity of permutation hypergraphs. Discrete Math. 312, 2536-2539(2012)
[9] Király, Z., Cosh, B., Jackson, B.:Local edge-connectivity augmentation in hypergraphs is NPcomplete. Discrete Appl. Math. 158, 723-727(2010)
[10] Hellwig, A., Volkmann, L.:Sufficient conditions for graphs to be λ-optimal, super-edge-connected and maximally edge-connected. J. Graph Theory 48, 228-246(2005)
[11] Berge, C.:Graphs and Hypergraphs, North-Holland Mathematical Library, vol. 6, 2nd edn. Springer, Amsterdam (1976)
[12] Bretto, A.:Hypergraph Theory:an introduction. Springer, Berlin (2013)
[13] Soneoka,T.,Nakada,H.,Imase,M.:Sufficientconditionsfordensegraphstobemaximallyconnected. Proc. IEEE Int Conf Circuit Syst 85, 811-814(1985)
[14] Soneoka, T., Nakada, H., Imase, M., Peyrat, C.:Sufficient conditions for maximally connected dense graphs. Discrete Math. 63, 53-66(1987)
[15] Dankelmann, P., Volkmann, L.:New sufficient conditions for equality of minimum degree and edgeconnectivity. Ars Combin. 40, 270-278(1995)
[16] Plesník, J., Znám, S.:On equality of edge-connectivity and minimum degree of a graph. Arch. Math. (Brno) 25, 19-25(1989)
[17] Lesniak, L.:Resluts on the edge-connectivity of graphs. Discrete Math. 8, 351-354(1974)
