Valentin Bouquet

collaborators

3 papers

math.CO2022

The bondage number of chordal graphs

Valentin Bouquet

A set $S \subseteq V (G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$ . Let $γ (G)$ be the cardinality of a minimum dominating set in $G$ .…

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

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…