On the sizes of (k, l)-edge-maximal r-uniform hypergraphs

DOI10.7151/DMGT.2362MaRDI QIDQ2107753zbMATH OpenOpenAlexFDO

Authors Yingzhi Tian, Hong-Jian Lai, Murong Xu, Jixiang Meng

Publication date 2 December 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1805.11425

zbMATH Keywords

\((k, l)\)-edge-maximal hypergraphs\(r\)-uniform hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

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 a $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|$. A $r$-uniform hypergraph $H=(V,E)$ is $(k,l)$-edge-maximal if every subhypergraph $H^{\prime }$ of $H$ with $|V(H^{\prime })|geql$ has edge-connectivity at most $k$, but for any edge $einE(K_n^r)setminusE(H)$, $H+e$ contains at least one subhypergraph $H^{″}$ with $|V(H^{″})|geql$ 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. Thus prior results in [Y.Z. Tian, L.Q. Xu, H.-J. Lai, J.X. Meng, On the sizes of $k$-edge-maximal $r$-uniform hypergraphs, arXiv:1802.08843v3] are extended.

Review text

An \(r\)-uniform hypergraph \(H = (V, E)\) where \(|V(H)|=n\) is said to be \((k, l)\)-edge-maximal if every subhypergraph \(H^\prime\) of \(H\) with \(|V (H^\prime)| \geq l\) has edge-connectivity at most \(k\), but for any edge \(e \in E(K_{n}^{r}) \backslash E(H), H + e\) contains at least one subhypergraph \(H^{\prime\prime}\) with \(|V (H^{\prime\prime})| \geq l\) and edge-connectivity at least \(k+1\). In this paper, the authors obtain lower and upper bounds of the sizes of \((k, l)\)-edge-maximal \(r\)-hypergraphs of order \(n\) and show that these bounds are best possible.

Recommendations

• On the sizes of \(k\)-edge-maximal \(r\)-uniform hypergraphs
• On the sizes of vertex-k-maximal r-uniform hypergraphs
• Sufficient conditions for hypergraphs to be maximally edge-connected
• Edge‐maximal (k, i)‐graphs
• Uniform hypergraphs under certain intersection constraints between hyperedges

Cites work

• k-Components, Clusters and Slicings in Graphs
• An edge extremal result for subcohesion
• Connection and separation in hypergraphs
• Connectivity in hypergraphs
• Edge‐maximal (k, i)‐graphs
• Graph theory
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On the sizes of \(k\)-edge-maximal \(r\)-uniform hypergraphs
• The size of strength‐maximal graphs

Cited in

(7)

• On the sizes of \(k\)-edge-maximal \(r\)-uniform hypergraphs
• On the sizes of vertex-k-maximal r-uniform hypergraphs
• Bounds on the number of edges of edge-minimal, edge-maximal and l-hypertrees
• scientific article; zbMATH DE number 1839818 (Why is no real title available?)
• Uniform hypergraphs under certain intersection constraints between hyperedges
• Spectral conditions for the maximum subgraph edge-connectivity of graphs
• A survey on the vertex-(edge-)k-maximal graphs and the k-vertex-(edge-)connected graphs with redundant subgraphs

This page was built for publication: On the sizes of \((k, l)\)-edge-maximal \(r\)-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107753)