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

摘要

Let gamma(G) denote the domination number of a graph G. A set B subset of E(G) is called a bondage edge set of Gif gamma (G - B) gamma(G). The bondage number b(G) of G is the cardinality of a minimum bondage edge set of G. A set S subset of V(G) is called a k-packing of graph G if dG(x, y) k for every pair of distinct vertices x, y is an element of S. A vertex v of G is called critical if gamma (G -v) = gamma (G) - 1. In this paper, we prove that for any nontrivial tree T, b(T) = 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.