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.

No reviews yet.

No comments yet.