Valentin Bouquet

activity

20192023

most citedOn the vertices belonging to all, some, none minimum dominating set

3 citations · 5 across the 7 of their papers we have counts for

collaborators

Showing 2020Show all

4 papers · 1 filter

math.CO2020

The complexity of the Perfect Matching-Cut problem

Valentin Bouquet, Christophe Picouleau

Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with ma…

math.CO2020

Partition of graphs with maximum degree ratio

Valentin Bouquet, François Delbot, Christophe Picouleau

Given a graph $G$ and a non trivial partition $(V_{1}, V_{2})$ of its vertex-set, the satisfaction of a vertex $v \in V_{i}$ is the ratio between the size of it's closed neighborhood in $V…

math.CO2020

On Minimum Dominating Sets in cubic and (claw,H)-free graphs

Valentin Bouquet, François Delbot, Christophe Picouleau +1

Given a graph $G = (V, E)$ , $S \subseteq V$ is a dominating set if every $v \in V ∖ S$ is adjacent to an element of $S$ . The Minimum Dominating Set problem asks for a dominating…

math.CO2020★ 2 cited

The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs

Valentin Bouquet, Christophe Picouleau

We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.