BZPEER

preprint2022arXiv

The bondage number of chordal graphs

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$ . The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set edges $A\subseteq E(G)$ such that $γ(G-A)=γ(G)+1$ . A chordal graph is a graph with no induced cycle of length four or more. In this paper, we prove that the bondage number of a chordal graph $G$ is at most the order of its maximum clique, that is, $b(G)\leq ω(G)$ . We show that this bound is best possible.

preprint2022arXiv

The complexity of the bondage problem in planar graphs

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$ . The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set of edges $A\subseteq E(G)$ , such that $γ(G-A)=γ(G)+1$ . The $d$ -Bondage is the problem of deciding, given a graph $G$ and an integer $d\geq 1$ , if $b(G)\leq d$ . This problem is known to be $\mathsf{NP}$ -hard even for bipartite graphs and $d=1$ . In this paper, we show that $1$ -Bondage is $\mathsf{NP}$ -hard, even for the class of $3$ -regular planar graphs, the class of subcubic claw-free graphs, and the class of bipartite planar graphs of maximum degree $3$ , with girth $k$ , for any fixed $k\geq 3$ . On the positive side, for any planar graph $G$ of girth at least $8$ , we show that we can find, in polynomial time, a set of three edges $A$ such that $γ(G-A)>γ(G)$ . Last, we exposed some classes of graphs for which Dominating Set can be solved in polynomial time, and where $d$ -Bondage can also be solved in polynomial time, for any fixed $d\geq 1$ .

preprint2020arXiv

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

Given a graph $G=(V,E)$ , $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$ . The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is $NP$ -complete even when $G$ is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of $(claw, H)$ -free graphs when $H$ has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is $NP$ -complete for cubic graphs.

Valentin Bouquet

Research overview

Is this your work?

3 publications

The bondage number of chordal graphs

The complexity of the bondage problem in planar graphs

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

See the researcher in context

Building this map preview