Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope

Given a graph G = (V;E), a subset S V is 2-dominating if every vertex in S has at least two neighbors in S. The minimum cardinality of such a set is called the 2-domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S, at each step mar...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Marenco, Javier, Blaum, Manuela
Formato:	info:eu-repo/semantics/preprint submittedVersion
Lenguaje:	Inglés
Publicado:	Universidad Torcuato Di Tella 2023
Materias:	Polyhedral combinatorics P3-convexity Hull-number 2-domination number
Acceso en línea:	https://repositorio.utdt.edu/handle/20.500.13098/12151
Aporte de:	Repositorio Digital Universidad Torcuato Di Tella de Universidad Torcuato Di Tella

id	I57-R163-20.500.13098-12151
record_format	dspace
spelling	I57-R163-20.500.13098-121512023-11-23T07:00:27Z Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope Marenco, Javier Blaum, Manuela Polyhedral combinatorics P3-convexity Hull-number 2-domination number Given a graph G = (V;E), a subset S V is 2-dominating if every vertex in S has at least two neighbors in S. The minimum cardinality of such a set is called the 2-domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S, at each step marks all unmarked vertices having two marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P3-hull number of G. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, a complete graph, or a tree. 2023-11-22T16:56:14Z 2023-11-22T16:56:14Z 2023 info:eu-repo/semantics/preprint info:eu-repo/semantics/submittedVersion https://repositorio.utdt.edu/handle/20.500.13098/12151 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-sa/2.5/ar/ 26 p. application/pdf application/pdf Universidad Torcuato Di Tella
institution	Universidad Torcuato Di Tella
institution_str	I-57
repository_str	R-163
collection	Repositorio Digital Universidad Torcuato Di Tella
language	Inglés
orig_language_str_mv	eng
topic	Polyhedral combinatorics P3-convexity Hull-number 2-domination number
spellingShingle	Polyhedral combinatorics P3-convexity Hull-number 2-domination number Marenco, Javier Blaum, Manuela Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
topic_facet	Polyhedral combinatorics P3-convexity Hull-number 2-domination number
description	Given a graph G = (V;E), a subset S V is 2-dominating if every vertex in S has at least two neighbors in S. The minimum cardinality of such a set is called the 2-domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S, at each step marks all unmarked vertices having two marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P3-hull number of G. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, a complete graph, or a tree.
format	info:eu-repo/semantics/preprint submittedVersion
author	Marenco, Javier Blaum, Manuela
author_facet	Marenco, Javier Blaum, Manuela
author_sort	Marenco, Javier
title	Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
title_short	Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
title_full	Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
title_fullStr	Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
title_full_unstemmed	Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope
title_sort	valid inequalities and complete characterizations of the 2-domination and p3-hull number polytope
publisher	Universidad Torcuato Di Tella
publishDate	2023
url	https://repositorio.utdt.edu/handle/20.500.13098/12151
work_keys_str_mv	AT marencojavier validinequalitiesandcompletecharacterizationsofthe2dominationandp3hullnumberpolytope AT blaummanuela validinequalitiesandcompletecharacterizationsofthe2dominationandp3hullnumberpolytope
_version_	1808040729164906496

Valid inequalities and complete characterizations of the 2-domination and P3-hull number polytope

Ejemplares similares