Manuela Blaum

dblp:240/5802 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
2since 2021 · last 2023
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 2 since 2021
YearPublicationVenuePosition
2023 Complete characterizations of the 2-domination and P3-hull number polytopes
Manuela Blaum, Javier Marenco
Discret. Appl. Math.1
2021 Valid inequalities and complete characterizations of the 2-domination and the P3-hull number polytopes
abstract
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 previously 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. These parameters are relevant both as a generalization of the domination number and in the context of discrete convexities in graphs, particularly the P3 convexity. 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, or a complete graph. If G is a tree we give the complete description of the associated 2-domination polytope.
Manuela Blaum, Javier Marenco
LAGOS1
2019 Computing the P3-hull number of a graph, a polyhedral approach
Manuela Blaum, Javier Marenco
Discret. Appl. Math.1