Domination number and feedback vertex number of complements of line graphs. Issue 3 (2nd September 2022) - Chen, Xiaohong; Wu, Baoyindureng
Abstract: In general, determining the domination number γ ( G ) and the feedback vertex number τ ( 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 γ ( G ¯ ) ≤ 3 for a claw-free G with α ( G ) ≥ 3, and thus determining the domination number of the complement of a claw-free G with α ( G ) ≥ 3 is polynomial, where α ( 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 ≤ γ ( 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, τ ( J ( G ) ) = n − Δ ( G ) − 1, provided Δ ( G ) ≥ 6 . For the case when Δ ( G ) ≤ 5, τ ( J ( G ) ) is also given. Thereby, we are able to show that determining τ ( J ( G ) ) is polynomial.