Clique-Transversal Sets in 4-Regular Claw-Free Graphs  

作　　者：Er Fang SHAN Li Ying KANG 

机构地区：[1]Department of Mathematics, Shanghai University, Shanghai 200444, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2011年第5期883-890,共8页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China （Grant No. 60773078）, the PuJiang Project of Shanghai （Grant No. 09PJ1405000） and Key Disciplines of Shanghai Municipality （Grant No. $30104）

摘　　要：A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.

关 键 词：Clique-transversal set claw-free graph line graph regular graph 

分 类 号：O157.5[理学—数学] O177.3[理学—基础数学]