Show simple item record

dc.rights.licensehttps://creativecommons.org/licenses/by-sa/2.5/ar/es_AR
dc.contributor.authorMarenco, Javieres_AR
dc.contributor.authorBlaum, Manuelaes_AR
dc.date.accessioned2023-11-22T16:56:14Z
dc.date.available2023-11-22T16:56:14Z
dc.date.issued2023
dc.identifier.urihttps://repositorio.utdt.edu/handle/20.500.13098/12151
dc.description.abstractGiven 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.es_AR
dc.format.extent26 p.es_AR
dc.format.mediumapplication/pdfes_AR
dc.languageenges_AR
dc.publisherUniversidad Torcuato Di Tellaes_AR
dc.rightsinfo:eu-repo/semantics/openAccesses_AR
dc.subjectPolyhedral combinatoricses_AR
dc.subjectP3-convexityes_AR
dc.subjectHull-numberes_AR
dc.subject2-domination numberes_AR
dc.titleValid inequalities and complete characterizations of the 2-domination and P3-hull number polytopees_AR
dc.typeinfo:eu-repo/semantics/preprintes_AR
dc.type.versioninfo:eu-repo/semantics/submittedVersiones_AR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record