摘要
把图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.
出处
《湛江师范学院学报》
2009年第3期11-12,15,共3页
Journal of Zhanjiang Normal College
基金
国家自然科学基金资助项目(10571117)
上海市曙光计划资助项目(06SG42)
关键词
团
团横贯数
团独立数
团图算法
clique
clique transversal number
clique independence number
clique graph algorithms
