Domination number and feedback vertex number of complements of line graphs

In general, determining the domination number gamma(G) and the feedback vertex number tau(G) of a claw-free graph (even a line graph) is NP-hard. In contrast, the situation becomes different for the complement of a line graph. In this paper, it is shown that gamma(G over bar )<= 3 for a claw-free G with alpha(G)>= 3, and thus determining the domination number of the complement of a claw-free G with alpha(G)>= 3 is polynomial, where alpha(G) is the independence number of G. Furthermore, if a graph G is not a star, has no isolated vertex and isolated edge, then 2 <=gamma(J(G))<= 3, where J(G) is the complement of the line graph L(G) of G. If a graph G is not a star, and has no isolated vertex, tau(J(G))=n-Delta(G)-1, provided Delta(G)>= 6. For the case when Delta(G)<= 5, tau(J(G)) is also given. Thereby, we are able to show that determining tau(J(G)) is polynomial.