Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Brešar, Boštjan
dc.contributor.author
Grippo, Luciano Norberto
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Milanič, Martin
dc.contributor.author
Safe, Martin Dario
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2020-02-10T15:35:54Z
dc.date.issued
2018-01
dc.identifier.citation
Bonomo, Flavia; Brešar, Boštjan; Grippo, Luciano Norberto; Milanič, Martin; Safe, Martin Dario; Domination parameters with number 2: Interrelations and algorithmic consequences; Elsevier Science; Discrete Applied Mathematics; 235; 1-2018; 23-50
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/97057
dc.description.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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
2-DOMINATION
dc.subject
APPROXIMATION ALGORITHM
dc.subject
DOUBLE DOMINATION
dc.subject
GRAPH DOMINATION
dc.subject
INAPPROXIMABILITY
dc.subject
INTEGER DOMINATION
dc.subject
RAINBOW DOMINATION
dc.subject
SPLIT GRAPH
dc.subject
TOTAL DOMINATION
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Domination parameters with number 2: Interrelations and algorithmic consequences
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-12-16T19:11:57Z
dc.journal.volume
235
dc.journal.pagination
23-50
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina
dc.description.fil
Fil: Brešar, Boštjan. Institute of Mathematics, Physics and Mechanics; Eslovenia. University of Maribor; Eslovenia
dc.description.fil
Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina
dc.description.fil
Fil: Milanič, Martin. University of Primorska; Eslovenia
dc.description.fil
Fil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina
dc.journal.title
Discrete Applied Mathematics
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X17304031
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.dam.2017.08.017
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1511.00410
Archivos asociados