Article in volume
Authors:
Title:
On the sizes of $(k,l)$-edge-maximal $r$-uniform hypergraphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 179-194
Received: 2019-12-27 , Revised: 2020-08-19 , Accepted: 2020-08-19 , Available online: 2020-09-30 , https://doi.org/10.7151/dmgt.2362
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
$K_n^r$, where $n=|V|.$ An $r$-uniform hypergraph $H=(V,E)$ is
$(k,l)$-edge-maximal if every subhypergraph $H'$ of $H$ with $|V(H')|\geq l$
has edge-connectivity at most $k$, but for any edge $e\in E(K_n^r)\setminus E(H)$,
$H+e$ contains at least one subhypergraph $H''$ with $|V(H'')|\geq 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:
edge-connectivity, $(k,l)$-edge-maximal hypergraphs, $r$-uniform hypergraphs
References:
- M.A. Bahmanian and M. Šajna, Connection and separation in hypergraphs, Theory Appl. Graphs 2 (2015) Article 5.
https://doi.org/10.20429/tag.2015.020205 - F.T. Boesch and J.A.M. McHuge, An edge extremal result for subcohesion, J. Combin. Theory Ser. B 38 (1985) 1–7.
https://doi.org/10.1016/0095-8956(85)90087-5 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer, Berlin, 2008).
- M. Dewar, D. Pike and J. Proos, Connectivity in hypergraphs, Canad. Math. Bull. 61 (2018) 252–271.
https://doi.org/10.4153/CMB-2018-005-9 - H.-J. Lai, The size of strength-maximal graphs, J. Graph Theory 14 (1990) 187–197.
https://doi.org/10.1002/jgt.3190140207 - H.-J. Lai and C.-Z. Zhang, Edge-maximal $(k,i)$-graphs, J. Graph Theory 18 (1994) 227–240.
https://doi.org/10.1002/jgt.3190180303 - W. Mader, Minimale $n$-fach kantenzusammenhängende Graphen, Math. Ann. 191 (1971) 21–28.
https://doi.org/10.1007/BF01433466 - D.W. Matula, $k$-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972) 459–480.
https://doi.org/10.1137/0122040 - 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.08843v3
Close