On the Sizes of k-edge-maximal r-uniform Hypergraphs  

作　　者：Ying-zhi TIAN Hong-Jian LAI Ji-xiang MENG Li-qiong XU 

机构地区：[1]College of Mathematics and System Sciences,Xinjiang University,Urumqi 830046,China [2]Department of Mathematics,West Virginia University,Morgantown,WV 26506,USA [3]School of Science,Jimei University,Xiamen 361021,China

出　　处：《Acta Mathematicae Applicatae Sinica》2022年第3期532-539,共8页应用数学学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.11861066,11531011);Tianshan Youth Project of Xinjiang(2018Q066)。

摘　　要：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|.A hypergraph H′=(V′,E′)is called a subhypergraph of H=(V,E)if V′⊆V and E′⊆E.The edge-connectivity of a hypergraph H is the cardinality of a minimum edge set F⊆E such that H−F is not connected,where H−F=(V,E\F).An 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 e∈E(K_(n)^(r))\E(H),H+e contains at least one subhypergraph with edge-connectivity at least k+1.Let k and r be integers with k≥2 and r≥2,and let t=t(k,r)be the largest integer such that(t−1 r−1)≤k.That is,t is the integer satisfying(t−1 r−1)≤k<(t r−1).We prove that if H is an r-uniform k-edge-maximal hypergraph such that n=|V(H)|≥t,then(i)|E(H)|≤(t r)+(n−t)k,and this bound is best possible;(ii)|E(H)|≥(n−1)k−((t−1)k−(t r))[n/t],and this bound is best possible.

关 键 词：EDGE-CONNECTIVITY k-edge-maximal hypergraphs r-uniform hypergraphs 

分 类 号：O157.5[理学—数学]