Domination number and feedback vertex number of complements of line graphs

Abstract

AbstractIn general, determining the domination number [Formula: see text] and the feedback vertex number [Formula: see text] 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 [Formula: see text] for a claw-free G with [Formula: see text] and thus determining the domination number of the complement of a claw-free G with [Formula: see text] is polynomial, where [Formula: see text] is the independence number of G. Furthermore, if a graph G is not a star, has no isolated vertex and isolated edge, then [Formula: see text] 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, [Formula: see text] provided [Formula: see text] For the case when [Formula: see text] is also given. Thereby, we are able to show that determining [Formula: see text] is polynomial.

Keywords

• Line graph
• jump graph
• feedback vertex number
• decycling number
• domination number