Domination number and feedback vertex number of complements of line graphs
| Autor: | Xiaohong Chen, Baoyindureng Wu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | AKCE International Journal of Graphs and Combinatorics, Vol 19, Iss 3, Pp 171-176 (2022) |
| Druh dokumentu: | article |
| ISSN: | 09728600 2543-3474 0972-8600 |
| DOI: | 10.1080/09728600.2022.2142863 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|