平面图上的团横贯数与独立数  

Clique-transversal number and independence number in planar graphs

作　　者：孙玉潇 梁作松[2] 单而芳[1] 

机构地区：[1]上海大学理学院,上海200444 [2]曲阜师范大学管理学院,日照276800

出　　处：《应用数学与计算数学学报》2015年第4期514-520,共7页Communication on Applied Mathematics and Computation

基　　金：国家自然科学基金资助项目(11426144);山东省自然科学青年基金资助(ZR2014AQ008)

摘　　要：设G为简单图,若G的点子集S与图中的每个团都有非空的交,则称S是图G的一个团横贯集,这里G的团是指图中的极大完全子图且至少包含两个点.图G的最小团横贯集所含点的数目称为G的团横贯数,记作τC(G).如果G的每条边至少包含在一个t阶完全子图中且τC(G)≤|V(G)|/t,则称G具有〈t〉一性质.提出了平面图分离4-团的概念.首先证明了最大度不超过5的平面图具有〈t〉-性质.其次,对任意平面图G,若它不含分离4-团且每条边都包含在一个4-团之中,得到了它的横贯数的上界和独立数的可达下界.A clique-transversal set D of a graph G is a subset of vertices of G such that D meets all cliques of G, where a clique is defined as a maximal complete subgraph having at least two vertices. The clique-transversal number, denoted by τc （G）, of G is the minimum cardinality of a clique-transversal set in G. A class G of graphs satisfies （t）-property if τc（G） ≤ ｜V（G）｜/t for every G ∈gt = {G∈ g： every edge of G is contained in a complete subgraph on t vertices}. We put forward the definition of separating 4-clique in planar graphs. In this paper, we show that the class of planar graphs with the maximum degree at most five satisfies （4）-property. For planar graphs without separating 4-cliques, if every edge of G lies in a 4-clique of G, we establish sharp lower bounds on the independence number and upper bounds on the clique-transversal number.

关 键 词：平面图 团横贯数 独立数 〈t〉-性质 分离4-团 

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