123
Views
3
CrossRef citations to date
0
Altmetric
Original Articles

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

& ORCID Icon
Pages 511-527 | Received 03 Jan 2014, Accepted 12 Sep 2016, Published online: 28 Feb 2017
 

ABSTRACT

Let γ(G) denote the domination number of a graph G. A set BE(G) is called a bondage edge set of G if γ(GB)>γ(G). The bondage number b(G) of G is the cardinality of a minimum bondage edge set of G. A set SV(G) is called a k-packing of graph G if dG(x,y)>k for every pair of distinct vertices x,yS. A vertex v of G is called critical if γ(Gv)=γ(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.

AMS 2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.