Domination parameters with number 2 : Interrelations and algorithmic consequences

BONOMO, FLAVIA; BRESAR, BOSTJAN; GRIPPO, LUCIANO N.; MILANIC, MARTIN; SAFE, MARTÍN D.

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Año: 2018 vol. 235 p. 23 - 50

0166-218X

In this paper, we study the most basic domination invariants in graphs, in which number 2is intrinsic part of their definitions. We classify them upon three criteria, two of which givethe following previously studied invariants: the weak 2-domination number, γw2(G), the2-domination number, γ2(G), the {2}-domination number, γ{2}(G), the double dominationnumber, γ×2(G), the total{2}-domination number, γt{2}(G), and the total double dominationnumber, γ t×2(G), where G is a graph in which the corresponding invariant is well defined.The third criterion yields rainbow versions of the mentioned six parameters, one of whichhas already been well studied, and three other give new interesting parameters. Togetherwith a special, extensively studied Roman domination, γ R(G), and two classical parameters,the domination number, γ (G), and the total domination number, γt(G), we consider 13domination invariants in graphs. In the main result of the paper we present sharp upperand lower bounds of each of the invariants in terms of every other invariant, a large majorityof which are new results proven in this paper. As a consequence of the main theorem weobtain new complexity results regarding the existence of approximation algorithms for thestudied invariants, matched with tight or almost tight inapproximability bounds, whichhold even in the class of split graphs.