On the Clique-Transversal Number in(Claw,K_4 )-Free 4-Regular Graphs  

作　　者：Ding Guo WANG Er Fang SHAN Zuo Song LIANG 

机构地区：[1]Department of Mathematics,Shanghai University [2]College of Mathematics Science,Chongqing Normal University [3]School of Management,Shanghai University

出　　处：《Acta Mathematica Sinica,English Series》2014年第3期505-516,共12页数学学报（英文版）

基　　金：Supported by National Nature Science Foundation of China(Grant Nos.11171207 and 10971131)

摘　　要：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 by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].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 by τC（G）,is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC（G） and characterize the extremal graphs achieving the lower bound for a connected（claw,K4）-free 4-regular graph G.Furthermore,we show that for any 2-connected（claw,K4）-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].

关 键 词：GRAPH clique-transversal set CLIQUE 4-regular graph claw-free graph 

分 类 号：O157.5[理学—数学]