Quantcast

Domination parameters with number 22: Interrelations and algorithmic consequences

Research paper by FlaviaBonomoab, BoštjanBrešarcd, Luciano N.Grippoe, MartinMilaničfg, Martín D.Safehe

Indexed on: 12 Nov '17Published on: 01 Oct '17Published in: Discrete Applied Mathematics



Abstract

In this paper, we study the most basic domination invariants in graphs, in which number 2<math class="math"><mn is="true">2</mn></math> is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2<math class="math"><mn is="true">2</mn></math>-domination number, γw2(G)<math class="math"><mi is="true">γ</mi><mspace width="0.16667em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mi is="true">w</mi><mspace width="-0.16667em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><mspace width="2.22198pt" is="true"></mspace><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, the 2<math class="math"><mn is="true">2</mn></math>-domination number, γ2(G)<math class="math"><msub is="true"><mrow is="true"><mi is="true">γ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, the {2}<math class="math"><mrow is="true"><mo is="true">{</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></math>-domination number, γ{2}(G)<math class="math"><mi is="true">γ</mi><mspace width="0.2777em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mrow is="true"><mo is="true">{</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, the double domination number, γ×2(G)<math class="math"><mi is="true">γ</mi><mspace width="0.16667em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mo is="true">×</mo><mspace width="-0.16667em" is="true"></mspace><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, the total {2}<math class="math"><mrow is="true"><mo is="true">{</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></math>-domination number, γt{2}(G)<math class="math"><mi is="true">γ</mi><mspace width="0.2777em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mi mathvariant="italic" is="true">t</mi><mrow is="true"><mo is="true">{</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, and the total double domination number, γt×2(G)<math class="math"><mi is="true">γ</mi><mspace width="0.2777em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mi mathvariant="italic" is="true">t</mi><mspace width="-0.16667em" is="true"></mspace><mo is="true">×</mo><mspace width="-0.16667em" is="true"></mspace><mn is="true">2</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, where G<math class="math"><mi is="true">G</mi></math> 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)<math class="math"><mi is="true">γ</mi><mspace width="0.2777em" is="true"></mspace><mspace width="-0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mspace width="-0.16667em" is="true"></mspace></mrow><mrow is="true"><mi mathvariant="italic" is="true">R</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, and two classical parameters, the domination number, γ(G)<math class="math"><mi is="true">γ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, and the total domination number, γt(G)<math class="math"><msub is="true"><mrow is="true"><mi is="true">γ</mi></mrow><mrow is="true"><mi is="true">t</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>, we consider 13<math class="math"><mn is="true">13</mn></math> 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.