| 团图为数的图中的闭团贯数 |
| |
| 引用本文： | 梁作松,单而芳.团图为数的图中的闭团贯数[J].上海大学学报(英文版),2008,12(3):197-199. |
| |
| 作者姓名： | 梁作松 单而芳 |
| |
| 作者单位： | LIANG Zuo-song（Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China）
SHAN Er-fang（Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China;Department of Logistics, The Hong Kong Polytechnic University, Hong Kong, P. R. China） |
| |
| 基金项目： | 国家自然科学基金
,
上海市教委资助项目 |
| |
| 摘 要： | Given a graph G,a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C|≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as TC (G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as 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 in G have nonempty intersection. Let F be a class of graphs G such that F={G|K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus TC (G)/|G|≤1/2 for all G ∈ F.
|
| 关 键 词： | 团图 树 团横贯数 跳跃 |
| 收稿时间： | 2006-08-31 |
| 修稿时间： | 2006年8月31日 |
Clique-transversal number of graphs whose clique-graphs are trees |
| |
| LIANG Zuo-song,SHAN Er-fang.Clique-transversal number of graphs whose clique-graphs are trees[J].Journal of Shanghai University(English Edition),2008,12(3):197-199. |
| |
| Authors: | LIANG Zuo-song SHAN Er-fang |
| |
| Affiliation: | 1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China
2. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China;Department of Logistics, The Hong Kong Polytechnic University, Hong Kong, P. R. China |
| |
| Abstract: | Given a graph G,a subgraph C is called a clique of G if C is a complete subgraph of G maximal under inclusion and |C|≥2. A clique-transversal set S of G is a set of vertices of G such that S meets all cliques of G. The clique-transversal number, denoted as TC (G), is the minimum cardinality of a clique-transversal set in G. The clique-graph of G, denoted as 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 in G have nonempty intersection. Let F be a class of graphs G such that F={G|K(G) is a tree}. In this paper the graphs in F having independent clique-transversal sets are shown and thus TC (G)/|G|≤1/2 for all G ∈ F. |
| |
| Keywords: | clique-transversal number clique-graph tree bound 团图 trees graphs paper independent sets class intersection taking minimum cardinality number cliques complete subgraph maximal inclusion |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 |
|
点击此处可从《上海大学学报(英文版)》下载全文 |
|
