4 citations · 6 across the 5 of their papers we have counts for
14 papers
The complexity of blocking (semi)total dominating sets with edge contractions
Esther Galby
We consider the problem of reducing the (semi)total domination number of graph by one by contracting edges. It is known that this can always be done with at most three edge contrac…
Using edge contractions to reduce the semitotal domination number
Esther Galby, Paloma T. Lima, Felix Mann +1
In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting edges, for some fixed . We show that this can alway…
Reducing the domination number of -free graphs via one edge contraction
Esther Galby, Felix Mann, Bernard Ries
In this note, we consider the following problem: given a connected graph , can we reduce the domination number of by using only one edge contraction? We show that the proble…
Blocking total dominating sets via edge contractions
Esther Galby, Felix Mann, Bernard Ries
In this paper, we study the problem of deciding whether the total domination number of a given graph can be reduced using exactly one edge contraction (called 1-Edge Contractio…
Approximating Independent Set and Dominating Set on VPG graphs
Esther Galby, Andrea Munaro
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain -hard on -VPG graphs admi…
Blocking dominating sets for -free graphs via edge contractions
Esther Galby, Paloma T. Lima, Bernard Ries
In this paper, we consider the following problem: given a connected graph , can we reduce the domination number of by one by using only one edge contraction? We show that th…