Domination parameters with number 2: Interrelations and algorithmic consequences

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),...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2018
Materias:
2-domination
Approximation algorithm
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow domination
Split graph
Total domination
Approximation algorithms
Rainbow dominations
Split graphs
Graph theory
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v235_n_p23_Bonomo
http://hdl.handle.net/20.500.12110/paper_0166218X_v235_n_p23_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0166218X_v235_n_p23_Bonomo
record_format dspace
spelling paper:paper_0166218X_v235_n_p23_Bonomo2023-06-08T15:15:35Z Domination parameters with number 2: Interrelations and algorithmic consequences 2-domination Approximation algorithm Double domination Graph domination Inapproximability Integer domination Rainbow domination Split graph Total domination Approximation algorithms 2-domination Double domination Graph domination Inapproximability Integer domination Rainbow dominations Split graphs Total domination Graph theory 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. © 2017 Elsevier B.V. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v235_n_p23_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v235_n_p23_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 2-domination
Approximation algorithm
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow domination
Split graph
Total domination
Approximation algorithms
2-domination
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow dominations
Split graphs
Total domination
Graph theory
spellingShingle 2-domination
Approximation algorithm
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow domination
Split graph
Total domination
Approximation algorithms
2-domination
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow dominations
Split graphs
Total domination
Graph theory
Domination parameters with number 2: Interrelations and algorithmic consequences
topic_facet 2-domination
Approximation algorithm
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow domination
Split graph
Total domination
Approximation algorithms
2-domination
Double domination
Graph domination
Inapproximability
Integer domination
Rainbow dominations
Split graphs
Total domination
Graph theory
description 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. © 2017 Elsevier B.V.
title Domination parameters with number 2: Interrelations and algorithmic consequences
title_short Domination parameters with number 2: Interrelations and algorithmic consequences
title_full Domination parameters with number 2: Interrelations and algorithmic consequences
title_fullStr Domination parameters with number 2: Interrelations and algorithmic consequences
title_full_unstemmed Domination parameters with number 2: Interrelations and algorithmic consequences
title_sort domination parameters with number 2: interrelations and algorithmic consequences
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v235_n_p23_Bonomo
http://hdl.handle.net/20.500.12110/paper_0166218X_v235_n_p23_Bonomo
_version_ 1768544268639535104

Ejemplares similares