Operations Research Transactions ›› 2013, Vol. 17 ›› Issue (2): 35-40.

• Original Articles • Previous Articles     Next Articles

The bound of clique-transversal numbers in claw-free graphs

LIANG Zuosong1,SHAN Erfang2,*,GUAN Mei3   

  1. 1. Department of Mathematics,  Shanghai University, Shanghai 200444, China 2. School of Management,  Shanghai University, Shanghai 200444, China 3. Department of Mathematics and Physics,  Hefei College, Hefei 230601, China
  • Received:2012-11-21 Online:2013-06-15 Published:2013-06-15

Abstract: A  clique-transversal set $S$ of a graph $G=(V, E)$ is a subset of vertices of $G$ such that $S$ meets all cliques of $G$, where a clique is defined as a complete subgraph  maximal under inclusion and having at least two vertices. The  clique-transversal number, of $G$ denoted by $\tau_C(G)$,  is the minimum cardinality of a clique-transversal set in $G$.  In this paper we discuss the bound of clique-transversal numbers in several subclasses of claw-free graphs.

Key words: clique-transversal number, clique-transversal set, claw-free graph, bound

CLC Number: