Upper bounds on the bondage number of the strong product of a graph and a tree

ABSTRACT

Let $\gamma \left(G\right)$ denote the domination number of a graph $G$. A set $B\subseteq E\left(G\right)$ is called a bondage edge set of $G$ if $\gamma (G-B)>\gamma \left(G\right)$. The bondage number $b\left(G\right)$ of $G$ is the cardinality of a minimum bondage edge set of $G$. A set $S\subseteq V\left(G\right)$ is called a k-packing of graph G if $d_G(x,y)>k$ for every pair of distinct vertices $x,y\in S$. A vertex v of G is called critical if $\gamma (G-v)=\gamma \left(G\right)-1$. In this paper, we prove that for any nontrivial tree T, $b\left(T\right)=2$ if and only if the set composed of all the critical vertices of T is a maximum 2-packing of T. Moreover, as the main work of this paper, we obtain several results of some sharp upper bounds of the bondage number of the strong product of a nonempty graph G and a nontrivial tree T under different conditions.

KEYWORDS:

• Bondage number
• strong product
• tree

AMS 2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 05C69
• 05C76

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Heping Zhang  http://orcid.org/0000-0001-5385-6687

Additional information

Funding

This work is supported by NSFC [grant nos. 61073046 & 61501208]