Domination number and feedback vertex number of complements of line graphs. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Chen, Xiaohong; Wu, Baoyindureng
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 19:Issue 3(2022)
• Page Start: 171
• Page End: 176
• Publication Date: 2022-09-02
• Subjects: Line graph -- jump graph -- feedback vertex number -- decycling number -- domination number
• DOI: 10.1080/09728600.2022.2142863
• Languages: English
• ISSNs: 0972-8600

Abstract

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.