1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On the Sizes of (k, l)-Edge-Maximal r-Uniform Hypergraphs

Published Online: 20 Oct 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 27 Dec 2019
Accepted: 19 Aug 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let H = (V, E) be a hypergraph, where V is a set of vertices and E is a set of non-empty subsets of V called edges. If all edges of H have the same cardinality r, then H is an r-uniform hypergraph; if E consists of all r-subsets of V, then H is a complete r-uniform hypergraph, denoted by Krn, where n = |V |. An r-uniform hypergraph H = (V, E) is (k, l)-edge-maximal if every subhypergraph H′ of H with |V (H′)| ≥ l has edge-connectivity at most k, but for any edge e ∈ E(Knr) \ E(H), H + e contains at least one subhypergraph H′′ with |V (H′′)| ≥ l and edge-connectivity at least k +1. In this paper, we obtain the lower bounds and the upper bounds of the sizes of (k, l)-edge-maximal hypergraphs. Furthermore, we show that these bounds are best possible.

Keywords

MSC 2010

[1] M.A. Bahmanian and M.Šajna, Connection and separation in hypergraphs, Theory Appl. Graphs 2 (2015) Article 5. doi:10.20429/tag.2015.02020510.20429/tag.2015.020205Search in Google Scholar

[2] F.T. Boesch and J.A.M. McHuge, An edge extremal result for subcohesion, J. Combin. Theory Ser. B 38 (1985) 1–7. doi:10.1016/0095-8956(85)90087-510.1016/0095-8956(85)90087-5Search in Google Scholar

[3] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Grad. Texts in Math. 244 (Springer, Berlin, 2008).10.1007/978-1-84628-970-5Search in Google Scholar

[4] M. Dewar, D. Pike and J. Proos, Connectivity in hypergraphs, Canad. Math. Bull. 61 (2018) 252–271. doi:10.4153/CMB-2018-005-910.4153/CMB-2018-005-9Search in Google Scholar

[5] H.-J. Lai, The size of strength-maximal graphs, J. Graph Theory 14 (1990) 187–197. doi:10.1002/jgt.319014020710.1002/jgt.3190140207Search in Google Scholar

[6] H.-J. Lai and C.-Z. Zhang, Edge-maximal (k, i)-graphs, J. Graph Theory 18 (1994) 227–240. doi:10.1002/jgt.319018030310.1002/jgt.3190180303Search in Google Scholar

[7] W. Mader, Minimale n-fach kantenzusammenhängende Graphen, Math. Ann. 191 (1971) 21–28. doi:10.1007/BF0143346610.1007/BF01433466Search in Google Scholar

[8] D.W. Matula, k-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972) 459–480. doi:10.1137/012204010.1137/0122040Search in Google Scholar

[9] Y.Z. Tian, L.Q. Xu, H.-J. Lai and J.X. Meng, On the sizes of k-edge-maximal r-uniform hypergraphs, (2018). arXiv:1802.08843v3Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo