| 一类团横贯数等于团独立数的图 |
| |
| 引用本文： | 梁作松,单而芳. 一类团横贯数等于团独立数的图[J]. 湛江师范学院学报, 2009, 30(3): 11-12,15 |
| |
| 作者姓名： | 梁作松 单而芳 |
| |
| 作者单位： | 1. 湛江师范学院,基础教育学院,广东,湛江,524300
2. 上海大学,数学系,上海,200444 |
| |
| 基金项目： | 国家自然科学基金资助项目,上海市曙光计划资助项目 |
| |
| 摘 要： | 把图G的每一个团看作一个点,两点之间有边相连当且仅当它们对应的团有非空交（即有公共点）．这样得到的图称为图G的团图,记为K（G）．文章证明了如果一个图对应的团图为二部图,则该图的团横贯数等于团独立数,即τc（G）=ac（G）,另外给出了判断一个图的团图是否为二部图的一个计算时间为o（n^4）的多项式时间算法．
|
| 关 键 词： | 团 团横贯数 团独立数 团图算法 |
A Class of Graphs Whose Clique Transversal Numbers Equal Clique Independence Numbers |
| |
| LIANG Zuo-song,SHAN Er-fang. A Class of Graphs Whose Clique Transversal Numbers Equal Clique Independence Numbers[J]. Journal of Zhanjiang Normal College, 2009, 30(3): 11-12,15 |
| |
| Authors: | LIANG Zuo-song SHAN Er-fang |
| |
| Affiliation: | LIANG Zuo-song , SHAN Er- fang(1. Basic Education College, Zhanjiang Normal College, Zhanjiang Guangdong 524300,China ; 2. Mathimatics Department, Shanghai University, Shanghai 200444,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | clique clique transversal number clique independence number clique graph algorithms |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
