Domination parameters with number 2 : interrelations and algorithmic consequences
Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier Science BV
2024
|
| Materias: | |
| Acceso en línea: | http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1588 |
| Aporte de: |
| id |
I71-R177-UNGS-1588 |
|---|---|
| record_format |
dspace |
| spelling |
I71-R177-UNGS-15882024-07-23T17:14:56Z Domination parameters with number 2 : interrelations and algorithmic consequences Bonomo, Flavia Brešar, Boštjan Grippo, Luciano Norberto Milanič, Martin Safe, Martín D. Graph domination Total domination Rainbow domination 2-domination Integer domination Double domination Split graph Approximation algorithm Inapproximability Matemática Aplicada Matemática Pura Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil:Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Safe, Martín M. Universidad Nacional del Sur. Departamento de Matemática; Argentina. Fil: Brešar, Boštjan. University of Maribor. Faculty of Natural Sciences and Mathematics; Slovenia. Fil: Milanič, Martin. University of Primorska; Eslovenia. 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 2024-07-16T17:07:07Z 2024-07-16T17:07:07Z 2018 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Bonomo, F. et al. (1-2018). Domination parameters with number 2: interrelations and algorithmic consequences. Discrete Applied Mathematics, 235, 23-50. 0166-218X http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1588 eng http://dx.doi.org/10.1016/j.dam.2017.08.017 info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Science BV Discrete Applied Mathematics. (1-2018); 235: 23-50 https://linkinghub.elsevier.com/retrieve/pii/S0166218X17304031 |
| institution |
Universidad Nacional de General Sarmiento |
| institution_str |
I-71 |
| repository_str |
R-177 |
| collection |
Repositorio Institucional Digital de Acceso Abierto (UNGS) |
| language |
Inglés |
| orig_language_str_mv |
eng |
| topic |
Graph domination Total domination Rainbow domination 2-domination Integer domination Double domination Split graph Approximation algorithm Inapproximability Matemática Aplicada Matemática Pura |
| spellingShingle |
Graph domination Total domination Rainbow domination 2-domination Integer domination Double domination Split graph Approximation algorithm Inapproximability Matemática Aplicada Matemática Pura Bonomo, Flavia Brešar, Boštjan Grippo, Luciano Norberto Milanič, Martin Safe, Martín D. Domination parameters with number 2 : interrelations and algorithmic consequences |
| topic_facet |
Graph domination Total domination Rainbow domination 2-domination Integer domination Double domination Split graph Approximation algorithm Inapproximability Matemática Aplicada Matemática Pura |
| description |
Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina |
| format |
Artículo Artículo publishedVersion |
| author |
Bonomo, Flavia Brešar, Boštjan Grippo, Luciano Norberto Milanič, Martin Safe, Martín D. |
| author_facet |
Bonomo, Flavia Brešar, Boštjan Grippo, Luciano Norberto Milanič, Martin Safe, Martín D. |
| author_sort |
Bonomo, Flavia |
| 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 |
| publisher |
Elsevier Science BV |
| publishDate |
2024 |
| url |
http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/1588 |
| work_keys_str_mv |
AT bonomoflavia dominationparameterswithnumber2interrelationsandalgorithmicconsequences AT bresarbostjan dominationparameterswithnumber2interrelationsandalgorithmicconsequences AT grippolucianonorberto dominationparameterswithnumber2interrelationsandalgorithmicconsequences AT milanicmartin dominationparameterswithnumber2interrelationsandalgorithmicconsequences AT safemartind dominationparameterswithnumber2interrelationsandalgorithmicconsequences |
| _version_ |
1817374902247751680 |