“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16491 |
|
| Abstract: | |
|
The smallest number of cliques, covering all edges of a graph G , is called the (edge) clique cover number of G and is denoted by \cc(G) . It is an easy observation that if G is a line graph on n vertices, then \cc(G) ≤ n . G. Chen et al. [Discrete Math. 219 (2000), no. 1-3, 17-26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if G is a connected claw-free graph on n vertices with three pairwise nonadjacent vertices, then \cc(G) ≤ n and the equality holds if and only if G is either the graph of icosahedron, or the complement of a graph on 10 vertices called "twister" or the pth power of the cycle Cn , for some positive integer p ≤ ⎣(n−1)/3⎦.
Download TeX format |
|
| back to top | |
