| Bounds on the clique-transversal number of regular graphs |
| |
| 作者单位： | Department of |
| |
| 摘 要： | A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.
|
| 收稿时间： | 8 January 2007 |
| 修稿时间： | 9 August 2007 |
Bounds on the clique-transversal number of regular graphs |
| |
| Authors: | ErFang Shan T C E Cheng LiYing Kang |
| |
| Institution: | (1) Department of Mathematics, Shanghai University, Shanghai, 200444, China;(2) Department of Logistics, The Hong Kong Polytechnic University, Hong Kong, China |
| |
| Abstract: | A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound. |
| |
| Keywords: | graph regular graph claw-free cubic graph clique-transversal set clique-transversal number |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
