两类Berge超图的Turan数  

The Turan numbers of two kinds of Berge hypergraphs

作　　者：康丽英[1] 薛益赛 单而芳[2] Liying Kang;Yisai Xue;Erfang Shan

机构地区：[1]上海大学数学系,上海200444 [2]上海大学管理学院,上海200444

出　　处：《中国科学：数学》2024年第11期1807-1820,共14页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11971298)资助项目。

摘　　要：设F是一个图,H是一个超图.若存在双射ϕ:E(F)→E(H)使得对于任意e∈E(F),都有e■(e),则称H是一个Berge-F.若超图G不含任何Berge-F作为子超图,则称G是禁用Berge-F.将n阶禁用Berge-F的r-一致超图所能达到的最大边数称为Berge-F的Tur′an数,记作exr(n,Berge-F).如果存在F的一条边使得这条边被删除之后图F的染色数下降,则称F是边临界图.本文研究当F分别是pKk和边临界图的情形,给出了Berge-F的Tur'an数的精确值,其中pKk是p个点不交的k-团的并图.Let F be a graph.A hypergraph H is called a Berge-F if there is a bijectionϕ:E(F)→E(H)such that e⊆φ(e)for each e∈E(F).We say that the hypergraph H is Berge-F-free if there is no sub-hypergraph of H isomorphic to any Berge-F.The maximum number of edges,denoted by exr(n,Berge-F),in an n-vertex r-uniform Berge-F-free hypergraph is the Turan number of Berge-F.A graph F is called an edge-critical graph if the removal of an edge decreases the chromatic number of F.In this paper,we give the Turan number of Berge-F when F is pK_(k) or an edge-critical graph.

关 键 词：Berge-超图 Turan数 边临界图 

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