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

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

• edge-connectivity
• (k,l)-edge-maximal hypergraphs
• r-uniform hypergraphs
• 05c65
• 05c35