On the sizes of k-edge-maximal r-uniform hypergraphs

DOI10.1007/S10255-022-1095-3MaRDI QIDQ2155642zbMATH OpenOpenAlexFDO

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

Publication date 15 July 2022

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

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

zbMATH Keywords

edge-connectivity\(r\)-uniform hypergraphs\(k\)-edge-maximal hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) 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 hypergraph $H^{\prime }=(V^{\prime },E^{\prime })$ is called a subhypergraph of $H=(V,E)$ if $V^{\prime }subseteqV$ and $E^{\prime }subseteqE$. A $r$-uniform hypergraph $H=(V,E)$ is $k$-edge-maximal if every subhypergraph of $H$ has edge-connectivity at most $k$, but for any edge $einE(K_n^r)setminusE(H)$, $H+e$ contains at least one subhypergraph with edge-connectivity at least $k+1$. Let $k$ and $r$ be integers with $kgeq2$ and $rgeq2$, and let $t=t(k,r)$ be the largest integer such that ${(}_{r-1}^{t-1})leqk$. That is, $t$ is the integer satisfies ${(}_{r-1}^{t-1})leqk<{(}_{r-1}^t)$. We prove that if $H$ is a $r$-uniform $k$-edge-maximal hypergraph such that $n=|V(H)|geqt$, then ($i$) $|E(H)|leq{(}_r^t)+(n-t)k$, and this bound is best possible; ($ii$) $|E(H)|geq(n-1)k-((t-1)k-{(}_r^t))lfloorfracntfloor$, and this bound is best possible. This extends former results in [8] and [6].

Recommendations

• On the sizes of \((k, l)\)-edge-maximal \(r\)-uniform hypergraphs
• Sufficient conditions for maximally edge-connected hypergraphs
• On the sizes of vertex-\(k\)-maximal \(r\)-uniform hypergraphs
• Sufficient conditions for hypergraphs to be maximally edge-connected
• Maximally edge-connected hypergraphs

Cites work

• k-Components, Clusters and Slicings in Graphs
• Connection and separation in hypergraphs
• Connectivity in hypergraphs
• Edge-connection of graphs, digraphs, and hypergraphs
• Graph theory
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On \(k\)-maximal strength digraphs
• On the lower bound of \(k\)-maximal digraphs
• The size of strength‐maximal graphs

Cited in

(6)

• A note on G-intersecting families
• On the sizes of \((k, l)\)-edge-maximal \(r\)-uniform hypergraphs
• scientific article; zbMATH DE number 1839818 (Why is no real title available?)
• Realizing degree sequences with \(k\)-edge-connected uniform hypergraphs
• On the sizes of vertex-\(k\)-maximal \(r\)-uniform hypergraphs
• Maximally connected \(p\)-partite uniform hypergraphs

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

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