Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871640 | Discrete Applied Mathematics | 2018 | 28 Pages |
Abstract
In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2-domination number, γw2(G), the 2-domination number, γ2(G), the {2}-domination number, γ{2}(G), the double domination number, γÃ2(G), the total {2}-domination number, γt{2}(G), and the total double domination number, γ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 which has already been well studied, and three other give new interesting parameters. Together with 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 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Flavia Bonomo, BoÅ¡tjan BreÅ¡ar, Luciano N. Grippo, Martin MilaniÄ, MartÃn D. Safe,