Bazgan, Cristina

Brankovic, Ljiljana

Casel, Katrin

Fernau, Henning

2020-06-15

<p>We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.</p>

Discrete Applied Mathematics, v.280, p. 23-42

1872-6771

0166-218X

https://hdl.handle.net/1959.11/53636

Elsevier BV, North-Holland

Domination Chain: Characterisation, Classical Complexity, Parameterised Complexity and Approximability

Conference Publication

Publication