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...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 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 pap...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.展开更多
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 thi...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].展开更多
基金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.
基金the National Nature Science Foundation of China (Grant Nos.10571117,60773078)the Hong Kong Polytechnic University (Grant No.G-YX69) Shuguang Plan of Shanghai Education Development Foundation (Grant No.06SG42)
文摘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.
基金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].
