一类团横贯数等于团独立数的图  

A Class of Graphs Whose Clique Transversal Numbers Equal Clique Independence Numbers

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

机构地区：[1]湛江师范学院基础教育学院,广东湛江524300 [2]上海大学数学系,上海200444

出　　处：《湛江师范学院学报》2009年第3期11-12,15,共3页Journal of Zhanjiang Normal College

基　　金：国家自然科学基金资助项目(10571117);上海市曙光计划资助项目(06SG42)

摘　　要：把图G的每一个团看作一个点,两点之间有边相连当且仅当它们对应的团有非空交(即有公共点),这样得到的图称为图G的团图,记为K(G).文章证明了如果一个图对应的团图为二部图,则该图的团横贯数等于团独立数,即cτ(G)=cα(G),另外给出了判断一个图的团图是否为二部图的一个计算时间为o(n4)的多项式时间算法.The clique-graph of a graph G, denoted K（G）, is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques have nonempty intersection. In this paper, we prove that if the clique graph of G is a bipartite graph, then the clique transversal number of G equals the clique independence number of G. In addition, we present a polynomial-algorithm to decided whether the clique-graph of a graph G is a bipartite graph.

关 键 词：团 团横贯数 团独立数 团图算法 

分 类 号：O157.5[理学—数学] TN927.21[理学—基础数学]