The Bondage Number of the Strong Product of a Complete Graph and a Path

Abstract

The bondage number $b(G)$ of a graph $G$ is the cardinality of a minimum edge set whose removal from $G$ results in a graph with the domination number greater than that of $G$. It is a parameter to measure the vulnerability of a communication network under link failure. In this paper, we obtain the exact value of the bondage number of the strong product of a complete graph and a path. That is, for any two integers $m\ge 1$ and $n\ge 2$, $b(K_m⊠P_n)=\lceil \frac{m}{2}\rceil$ if $n\equiv 0$ (mod 3); $m$ if $n\equiv 2$ (mod 3); $\lceil \frac{3m}{2}\rceil$ if $n\equiv 1$ (mod 3). Furthermore, we determine the exact value of the bondage number of the strong product of a complete graph and a special starlike tree.

15 pages

References in corpus (1)

• Bondage number of grid graphs