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

8 papers

math.CO2023

On the complexity of Dominating Set for graphs with fixed diameter

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

A set $S \subseteq V$ of a graph $G = (V, E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$ . Dominating Set is the problem of deciding, given a graph $G$ a…

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.CO2021

The complexity of the bondage problem in planar 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

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.

math.CO2019★ 3 cited

On the vertices belonging to all, some, none minimum dominating set

Valentin Bouquet, François Delbot, Christophe Picouleau

We characterize the vertices belonging to all minimum dominating sets, to some minimum dominating sets but not all, and to no minimum dominating set. We refine this characterizatio…