# On Bondage Numbers of Graphs: A Survey with Some Comments

Authors: Jun-Ming Xu
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

The domination number of a graphG is the smallest number of vertices which dominate all remaining vertices by edges of G. The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than the domination number of G. The concept of the bondage number was formally introduced by Fink et al. in 1990. Since then, this topic has  received considerable research attention and made some progress, variations, and generalizations. This paper gives a survey on the bondage number, including known results, conjectures, problems, and some comments, also selectively summarizes other types of bondage numbers.


---

## Body

## 1. Introduction

For terminology and notation on graph theory not given here, the reader is referred to Xu [1]. Let G=(V,E) be a finite, undirected, and simple graph. We call |V| and |E| the order and size of G and denote them by υ=υ(G) and ε=ε(G), respectively, unless otherwise specified. Through this paper, the notations Pn, Cn, and Kn always denote a path, a cycle, and a complete graph of order n, respectively, the notation Kn1,n2,…,nt denotes a complete t-partite graph with n1⩽n2⩽⋯⩽nt and nt>1, Kt(m)=Kn1,n2,…,nt with n1=⋯=nt=m, and K1,n-1 is a star. For two vertices x and y in a connected graph G, we use dG(x,y) to denote the distance between x and y in G.For a vertexx in G, let NG(x) be the open  set of neighbors of x and NG[x]=N[x]=NG(x)∪{x} the closed set of neighbors of x. For a subset X⊂V(G), NG(X)=(∪x∈XNG(x))∩X¯, and NG[X]=NG(X)∪X, where X¯=V(G)∖X. Let Ex be the set of edges incident with x in G; that is, Ex={xy∈E(G):y∈NG(x)}. We denote the degree of x by dG(x)=|Ex|. The maximum and the minimum degrees of G are denoted by Δ(G) and δ(G), respectively. A vertex of degree zero is called an isolated vertex. An edge incident with a vertex of degree one is called a pendant edge.The bondage number is an important parameter of graphs which is based upon the well-known domination number.A subsetS⊆V(G) is called a dominating set of G if NG[S]=V(G); that is, every vertex  x in S¯ has at least one neighbor in S. The domination number of G, denoted by γ(G), is the minimum cardinality among all dominating sets; that is,
(1)γ(G)=min{|S|:S⊆V(G),NG[S]=V(G)}.
A dominating set S is called a γ-set of G if |S|=γ(G).The domination is such an important and classic conception that it has become one of the most widely studied topics in graph theory and also is frequently used to study property of networks. The domination, with many variations and generalizations, is now well studied in graph and networks theory. The early vast literature on domination includes the bibliography compiled by Hedetniemi and Laskar [2] and a thorough study of domination appears in the books by Haynes et al. [3, 4]. However, the problem determining the domination number for general graphs was early proved to be NP-complete (see GT2 in Appendix in Garey and Johnson [5], 1979).Among various problems related with the domination number, some focus on graph alterations and their effects on the domination number. Here, we are concerned with a particular graph alternation, the removal of edges from a graph.Graphs with domination numbers changed upon the removal of an edge were first investigated by Walikar and Acharya [6] in 1979. A graph is called edge-domination-critical graph if γ(G-e)>γ(G) for every edge e in G. The edge-domination-critical graph was characterized by Bauer et al. [7] in 1983; that is, a graph is edge-domination-critical if and only if it is the union of stars.However, for lots of graphs, the domination number is out of the range of one-edge removal. It is immediate thatγ(H)⩾γ(G) for any spanning subgraph H of G. Every graph G has a spanning forest T with γ(G)=γ(T), and so, in general, a graph has a nonempty subset F⊆E(G) for which γ(G-F)=γ(G).Then it is natural for the alternation to be generalized to the removal of several edges, which is just enough to enlarge the domination number. That is the idea of the bondage number.A measure of the efficiency of a domination in graphs was first given by Bauer et al. [7] in 1983, who called this measure as domination line-stability, defined as the minimum number of lines (i.e., edges) which when removed from G increases γ.In 1990, Fink et al. [8] formally introduced the bondage number as a parameter for measuring the vulnerability of the interconnection network under link failure. The minimum dominating set of sites plays an important role in the network for it dominates the whole network with the minimum cost. So we must consider whether its function remains good when the network is attacked. Suppose that someone such as a saboteur does not know which sites in the network take part in the dominating role, but does know that the set of these special sites corresponds to a minimum dominating set in the related graph. Then how many links does he has to attack so that the cost cannot remains the same in order to dominate the whole network? That minimum number of links is just the bondage number.Thebondage numberb(G) of a nonempty undirected graph G is the minimum number of edges whose removal from G results in a graph with larger domination number. The precise definition of the bondage number is as follows:
(2)b(G)=min{|B|:B⊆E(G),γ(G-B)>γ(G)}.
Since the domination number of every spanning subgraph of a nonempty graph G is at least as great as γ(G), the bondage number of a nonempty graph is well defined.We call such an edge-setB with γ(G-B)>γ(G) the bondage set and the minimum one the minimum bondage set. In fact, if B is a minimum bondage set, then γ(G-B)=γ(G)+1 because the removal of one single edge cannot increase the domination number by more than one. If b(G) does not exist, for example, empty graphs, we define b(G)=∞.It is quite difficult to compute the exact value of the bondage number for general graphs since it strongly depends on the domination number of the graphs. Much work focused on the bounds on the bondage number as well as the restraints on some particular classes of graphs or networks. The purpose of this paper is to give a survey of results and research methods related to these topics for graphs and digraphs. For some results and research methods, we will make some comments to develop our further study.The rest of the paper is organized as follows. Section2 gives some preliminary results and complexity. Sections 3 and 4 survey some upper bounds and lower bounds, respectively. The results for some special classes of graphs and planar graphs are stated in Sections 5 and 6, respectively. In Section 7, we introduce some results on crossing number restraints. In Sections 8 and 9, we are concerned about other and generalized types of bondage numbers, respectively. In Section 10, we introduce some results for digraphs. In the last section, we introduce some results for vertex-transitive graphs by applying efficient dominating sets.


## 2. Simplicity and Complexity

As we have known from Introduction, the bondage number is an important parameter for measuring the stability or the vulnerability of a domination in a graph or a network. Our aim is to compute the bondage number for any given graphs or networks. One has determined the exact value of the bondage number for some graphs with simple structure. For arbitrarily given graph, however, it has been proved that determining its bondage number is NP-hard.


### 2.1. Exact Values for Ordinary Graphs

We begin our investigation of the bondage number by computing its value for several well-known classes of graphs with simple structure. In 1990, Fink et al. [8] proposed the concept of the bondage number and completely determined the exact values of bondage numbers of some ordinary graphs, such as complete graphs, paths, cycles, and complete multipartite graphs.Theorem 1 (Fink et al. [8], 1990).
The exact values of bondage numbers of the following class of graphs are completely determined:(3)b(Kn)=⌈n2⌉;b(Pn)={2ifn≡1(mod3),1otherwise,b(Cn)={3ifn≡1(mod3),2otherwise,b(Kn1,n2,…,nt)={⌈j2⌉ifnj=1andnj+1⩾2,forsomej,1⩽j<t,2t-1ifn1=n2=⋯=nt=2,∑i=1t-1‍niotherwise.The complete graphKn is the unique (n-1)-regular graph of order n⩾2,b(Kn)=⌈n/2⌉ by Theorem 1. The t-partite graph Kt(2) with t=n/2 is an (n-2)-regular graph G of order n⩾2, and not unique, b(G)=n-1 by Theorem 1 for an even integer n⩾4. For an (n-3)-regular graph G of order n⩾4, Hu and Xu [9] obtained the following result.Theorem 2 (Hu and Xu [9]).
b
(
G
)
=
n
-
3 for any  (n-3)-regular graph G of order n⩾4.Up to the present, no results have been known fork-regular graphs with 3⩽k⩽n-4. For general graphs, there are the following two results.Theorem 3 (Teschner [10], 1997).
IfG is a nonempty graph with a unique minimum dominating set, then b(G)=1.Theorem 4 (Bauer et al. [7], 1983).
If any vertex of a graphG is adjacent with two or more vertices of degree one, then b(G)=1.Bauer et al. [7] observed that the star is the unique graph with the property that the bondage number is 1 and the deletion of any edge results in the domination number increasing. Motivated by this fact, Hartnell and Rall [11] proposed the concept of uniformly bonded graphs. A graph is called to be uniformly bonded if it has bondage number b and the deletion of any b edges results in a graph with increased domination number. Unfortunately, there are a few uniformly bonded graphs.Theorem 5 (Hartnell and Rall [11], 1999).
The only uniformly bonded graphs with bondage number 2 areC3 and P4. The unique uniformly bonded graph with bondage number 3 is C4. There are no such graphs for bondage number greater than 3.As we mentioned, to compute the exact value of bondage number for a graph strongly depends upon its domination number. In this sense, studying the bondage number can greatly inspire one's research concerned with dominations. However, determining the exact value of domination number for a given graph is quite difficult. In fact, even if the exact value of the domination number for some graph is determined, it is still very difficulty to compute the value of the bondage number for that graph. For example, for the hypercubeQn, we have γ(Qn)=2n-1, but we have not yet determined b(Qn) for any n⩾2.Perhaps Theorems3 and 4 provide an approach to compute the exact value of bondage number for some graphs by establishing some sufficient conditions for b(G)=b. In fact, we will see later that Theorem 3 plays an important role in determining the exact values of the bondage numbers for some graphs. Thus, to study the bondage number, it is important to present various characterizations of graphs with a unique minimum dominating set.


### 2.2. Characterizations of Trees

For trees, Bauer et al. [7] in 1983 from the point of view of the domination line-stability, independently and Fink  et al. [8] in 1990 from the point of view of the domination edge-vulnerability obtained the following result.Theorem 6.
For any nontrivial treeT, b(T)⩽2.By Theorem6, it is natural to classify all trees according to their bondage numbers. Fink  et al. [8] proved that a forbidden subgraph characterization to classify trees with different bondage numbers is impossible, since they proved that if F is a forest, then F is an induced subgraph of a tree T with b(T)=1 and a tree T′ with b(T′)=2. However, they pointed out that the complexity of calculating the bondage number of a tree of order n is at most O(n2) by methodically removing each pair of edges.Even so, some characterizations, whether a tree has bondage number 1 or 2, have been found by several authors; see, for example, [10, 12, 13].First we describe the method due to Hartnell and Rall [12], by which all trees with bondage number 2 can be constructed inductively. An important tree Ft in the construction is shown in Figure 1. To characterize this construction, we need some terminologies:Figure 1
TreeFt.(1)
attach a pathPn to a vertex x of a tree, which means to link x and one end-vertex of the Pn by an edge.
(2)
attachFt to a vertex x, which means to link x and a vertex y of Ft by an edge.The following are four operations on a treeT:Type 1:
attach aP2 to x∈V(T), where γ(T-x)=γ(T) and x belongs to at least one γ-set of T (such a vertex exists, say, one end-vertex of P5).Type 2:
attach aP3 to x∈V(T), where γ(T-x)<γ(T).Type 3:
attachF1 to x∈V(T), where x belongs to at least one γ-set of T.Type 4:
attachFt, t⩾2, to x∈V(T), where x can be any vertex of T.Let𝒞={T:T is a tree, and T=K1,T=P4, and T=Ft for some t⩾2, or T can be obtained from P4 or Ft(t⩾2) by a finite sequence of operations of Types 1,2,3,4}.Theorem 7 (Hartnell and Rall [12], 1992).
A tree has bondage number 2 if and only if it belongs to𝒞.Looking at different minimum dominating sets of a tree, Teschner [10] presented a totally different characterization of the set of trees having bondage number 1. They defined a vertex to be universal if it belongs to each minimum dominating set, and to be idle if it does not belong to any minimum dominating set.Theorem 8 (Teschner [10], 1997).
A treeT has bondage number 1 if and only if T has a universal vertex or an edge xy satisfying(1)
x and y are neither universal nor idle; and(2)
all neighbors ofx and y (except for x and y) are idle.For a positive integerk, a subset I⊆V(G) is called a k-independent set (also called a k-packing) if dG(x,y)>k for any two distinct vertices x and y in I. When k=1, 1-set is the normal independent set. The maximum cardinality among all k-independent sets is called the k-independence number (or k-packing number) of G, denoted by αk(G). A k-independent set I is called an αk-set if |I|=αk(G). A graph G is said to be αk-stable if αk(G)=αk(G-e) for every edge e of G. There are two important results on k-independent sets.Proposition 9 (Topp and Vestergaard [13], 2000).
A treeT is αk-stable if and only if T has a unique αk-set.Proposition 10 (Meir and Moon [14], 1975).
α
2
(
G
)
⩽
γ
(
G
) for any connected graph G with equality for any tree.Hartnell  et al. [15], independently and Topp and Vestergaard [13] also gave a constructive characterization of trees with bondage number 2 and, applying Proposition 10, presented another characterization of those trees.Theorem 11 (Hartnell et al. [15], 1998; Top and Vestergaard [13], 2000).
b
(
T
)
=
2 for a tree T if and only if T has a unique α2-set.According to this characterization, Hartnell  et al. [15] presented a linear algorithm for determining the bondage number of a tree.In this subsection, we introduce three characterizations for trees with bondage number 1 or 2. The characterization in Theorem7 is constructive, constructing all trees with bondage number 2, a natural and straightforward method, by a series of graph-operations. The characterization in Theorem 8 is a little advisable, by describing the inherent property of trees with bondage number 1. The characterization in Theorem 11 is wonderful, by using a strong graph-theoretic concept, αk-set. In fact, this characterization is a byproduct of some results related to αk-sets for trees. It is that this characterization closed the relation between two concepts, the bondage number and the k-independent set, and hence is of research value and important significance.


### 2.3. Complexity for General Graphs

As mentioned above, the bondage number of a tree can be determined by a linear time algorithm. According to this algorithm, we can determine within polynomial time the domination number of any tree by removing each edge and verifying whether the domination number is enlarged according to the known linear time algorithm for domination numbers of trees.However, it is impossible to find a polynomial time algorithm for bondage numbers of general graphs. If such an algorithmA exists, then the domination number of any nonempty undirected graph G can be determined within polynomial time by repeatedly using A. Let G0=G and Gi+1=Gi-Bi, where Bi is the minimum edge set of Gi found by A such that γ(Gi-Bi)=γ(Gi-1)+1 for each i=0,1,…; we can always find the minimum Bi whose removal from Gi enlarges the domination number, until Gk=Gk-1-Bk-1 is empty for some k⩾1, though Bk-1 is not empty. Then γ(G)=γ(Gk)-k=υ(G)-k. As known to all, if NP≠P, the minimum dominating set problem is NP-complete, and so polynomial time algorithms for the bondage number do not exist unless NP=P.In fact, Hu and Xu [16] have recently shown that the problem determining the bondage number of general graphs is NP-hard.Problem 1.
Consider the decision problem:Bondage ProblemInstance: a graphG and a positive integer b(⩽ε(G)).Question: isb(G)⩽b?Theorem 12 (Hu and Xu [16], 2012).
The bondage problem is NP-hard.The basic way of the proof is to follow Garey and Johnson's techniques for proving NP-hardness [5] by describing a polynomial transformation from the known NP-complete problem: 3-satisfiability problem.Theorem12 shows that we are unable to find a polynomial time algorithm to determine bondage numbers of general graphs unless NP=P. At the same time, this result also shows that the following study on the bondage number is of important significance.(i)
Find approximation polynomial algorithms with performance ratio as small as possible.(ii)
Find the lower and upper bounds with difference as small as possible.(iii)
Determine exact values for some graphs, specially well-known networks.Unfortunately, we cannot prove whether or not determining the bondage number is NP-problem since for any subsetB⊂E(G) it is not clear that there is a polynomial algorithm to verify γ(G-B)>γ(G). Since the problem of determining the domination number is NP-complete, we conjecture that it is not in NP. This is a worthwhile task to be studied further.Motivated by the linear time algorithm of Hartnell  et al. to compute the bondage number of a tree, we can make an attempt to consider whether there is a polynomial time algorithm to compute the bondage number for some special classes of graphs such as planar graphs, Cayley graphs, or graphs with some restrictions of graph-theoretical parameters such as degree, diameter, connectivity, and domination number.


## 2.1. Exact Values for Ordinary Graphs

We begin our investigation of the bondage number by computing its value for several well-known classes of graphs with simple structure. In 1990, Fink et al. [8] proposed the concept of the bondage number and completely determined the exact values of bondage numbers of some ordinary graphs, such as complete graphs, paths, cycles, and complete multipartite graphs.Theorem 1 (Fink et al. [8], 1990).
The exact values of bondage numbers of the following class of graphs are completely determined:(3)b(Kn)=⌈n2⌉;b(Pn)={2ifn≡1(mod3),1otherwise,b(Cn)={3ifn≡1(mod3),2otherwise,b(Kn1,n2,…,nt)={⌈j2⌉ifnj=1andnj+1⩾2,forsomej,1⩽j<t,2t-1ifn1=n2=⋯=nt=2,∑i=1t-1‍niotherwise.The complete graphKn is the unique (n-1)-regular graph of order n⩾2,b(Kn)=⌈n/2⌉ by Theorem 1. The t-partite graph Kt(2) with t=n/2 is an (n-2)-regular graph G of order n⩾2, and not unique, b(G)=n-1 by Theorem 1 for an even integer n⩾4. For an (n-3)-regular graph G of order n⩾4, Hu and Xu [9] obtained the following result.Theorem 2 (Hu and Xu [9]).
b
(
G
)
=
n
-
3 for any  (n-3)-regular graph G of order n⩾4.Up to the present, no results have been known fork-regular graphs with 3⩽k⩽n-4. For general graphs, there are the following two results.Theorem 3 (Teschner [10], 1997).
IfG is a nonempty graph with a unique minimum dominating set, then b(G)=1.Theorem 4 (Bauer et al. [7], 1983).
If any vertex of a graphG is adjacent with two or more vertices of degree one, then b(G)=1.Bauer et al. [7] observed that the star is the unique graph with the property that the bondage number is 1 and the deletion of any edge results in the domination number increasing. Motivated by this fact, Hartnell and Rall [11] proposed the concept of uniformly bonded graphs. A graph is called to be uniformly bonded if it has bondage number b and the deletion of any b edges results in a graph with increased domination number. Unfortunately, there are a few uniformly bonded graphs.Theorem 5 (Hartnell and Rall [11], 1999).
The only uniformly bonded graphs with bondage number 2 areC3 and P4. The unique uniformly bonded graph with bondage number 3 is C4. There are no such graphs for bondage number greater than 3.As we mentioned, to compute the exact value of bondage number for a graph strongly depends upon its domination number. In this sense, studying the bondage number can greatly inspire one's research concerned with dominations. However, determining the exact value of domination number for a given graph is quite difficult. In fact, even if the exact value of the domination number for some graph is determined, it is still very difficulty to compute the value of the bondage number for that graph. For example, for the hypercubeQn, we have γ(Qn)=2n-1, but we have not yet determined b(Qn) for any n⩾2.Perhaps Theorems3 and 4 provide an approach to compute the exact value of bondage number for some graphs by establishing some sufficient conditions for b(G)=b. In fact, we will see later that Theorem 3 plays an important role in determining the exact values of the bondage numbers for some graphs. Thus, to study the bondage number, it is important to present various characterizations of graphs with a unique minimum dominating set.


## 2.2. Characterizations of Trees

For trees, Bauer et al. [7] in 1983 from the point of view of the domination line-stability, independently and Fink  et al. [8] in 1990 from the point of view of the domination edge-vulnerability obtained the following result.Theorem 6.
For any nontrivial treeT, b(T)⩽2.By Theorem6, it is natural to classify all trees according to their bondage numbers. Fink  et al. [8] proved that a forbidden subgraph characterization to classify trees with different bondage numbers is impossible, since they proved that if F is a forest, then F is an induced subgraph of a tree T with b(T)=1 and a tree T′ with b(T′)=2. However, they pointed out that the complexity of calculating the bondage number of a tree of order n is at most O(n2) by methodically removing each pair of edges.Even so, some characterizations, whether a tree has bondage number 1 or 2, have been found by several authors; see, for example, [10, 12, 13].First we describe the method due to Hartnell and Rall [12], by which all trees with bondage number 2 can be constructed inductively. An important tree Ft in the construction is shown in Figure 1. To characterize this construction, we need some terminologies:Figure 1
TreeFt.(1)
attach a pathPn to a vertex x of a tree, which means to link x and one end-vertex of the Pn by an edge.
(2)
attachFt to a vertex x, which means to link x and a vertex y of Ft by an edge.The following are four operations on a treeT:Type 1:
attach aP2 to x∈V(T), where γ(T-x)=γ(T) and x belongs to at least one γ-set of T (such a vertex exists, say, one end-vertex of P5).Type 2:
attach aP3 to x∈V(T), where γ(T-x)<γ(T).Type 3:
attachF1 to x∈V(T), where x belongs to at least one γ-set of T.Type 4:
attachFt, t⩾2, to x∈V(T), where x can be any vertex of T.Let𝒞={T:T is a tree, and T=K1,T=P4, and T=Ft for some t⩾2, or T can be obtained from P4 or Ft(t⩾2) by a finite sequence of operations of Types 1,2,3,4}.Theorem 7 (Hartnell and Rall [12], 1992).
A tree has bondage number 2 if and only if it belongs to𝒞.Looking at different minimum dominating sets of a tree, Teschner [10] presented a totally different characterization of the set of trees having bondage number 1. They defined a vertex to be universal if it belongs to each minimum dominating set, and to be idle if it does not belong to any minimum dominating set.Theorem 8 (Teschner [10], 1997).
A treeT has bondage number 1 if and only if T has a universal vertex or an edge xy satisfying(1)
x and y are neither universal nor idle; and(2)
all neighbors ofx and y (except for x and y) are idle.For a positive integerk, a subset I⊆V(G) is called a k-independent set (also called a k-packing) if dG(x,y)>k for any two distinct vertices x and y in I. When k=1, 1-set is the normal independent set. The maximum cardinality among all k-independent sets is called the k-independence number (or k-packing number) of G, denoted by αk(G). A k-independent set I is called an αk-set if |I|=αk(G). A graph G is said to be αk-stable if αk(G)=αk(G-e) for every edge e of G. There are two important results on k-independent sets.Proposition 9 (Topp and Vestergaard [13], 2000).
A treeT is αk-stable if and only if T has a unique αk-set.Proposition 10 (Meir and Moon [14], 1975).
α
2
(
G
)
⩽
γ
(
G
) for any connected graph G with equality for any tree.Hartnell  et al. [15], independently and Topp and Vestergaard [13] also gave a constructive characterization of trees with bondage number 2 and, applying Proposition 10, presented another characterization of those trees.Theorem 11 (Hartnell et al. [15], 1998; Top and Vestergaard [13], 2000).
b
(
T
)
=
2 for a tree T if and only if T has a unique α2-set.According to this characterization, Hartnell  et al. [15] presented a linear algorithm for determining the bondage number of a tree.In this subsection, we introduce three characterizations for trees with bondage number 1 or 2. The characterization in Theorem7 is constructive, constructing all trees with bondage number 2, a natural and straightforward method, by a series of graph-operations. The characterization in Theorem 8 is a little advisable, by describing the inherent property of trees with bondage number 1. The characterization in Theorem 11 is wonderful, by using a strong graph-theoretic concept, αk-set. In fact, this characterization is a byproduct of some results related to αk-sets for trees. It is that this characterization closed the relation between two concepts, the bondage number and the k-independent set, and hence is of research value and important significance.


## 2.3. Complexity for General Graphs

As mentioned above, the bondage number of a tree can be determined by a linear time algorithm. According to this algorithm, we can determine within polynomial time the domination number of any tree by removing each edge and verifying whether the domination number is enlarged according to the known linear time algorithm for domination numbers of trees.However, it is impossible to find a polynomial time algorithm for bondage numbers of general graphs. If such an algorithmA exists, then the domination number of any nonempty undirected graph G can be determined within polynomial time by repeatedly using A. Let G0=G and Gi+1=Gi-Bi, where Bi is the minimum edge set of Gi found by A such that γ(Gi-Bi)=γ(Gi-1)+1 for each i=0,1,…; we can always find the minimum Bi whose removal from Gi enlarges the domination number, until Gk=Gk-1-Bk-1 is empty for some k⩾1, though Bk-1 is not empty. Then γ(G)=γ(Gk)-k=υ(G)-k. As known to all, if NP≠P, the minimum dominating set problem is NP-complete, and so polynomial time algorithms for the bondage number do not exist unless NP=P.In fact, Hu and Xu [16] have recently shown that the problem determining the bondage number of general graphs is NP-hard.Problem 1.
Consider the decision problem:Bondage ProblemInstance: a graphG and a positive integer b(⩽ε(G)).Question: isb(G)⩽b?Theorem 12 (Hu and Xu [16], 2012).
The bondage problem is NP-hard.The basic way of the proof is to follow Garey and Johnson's techniques for proving NP-hardness [5] by describing a polynomial transformation from the known NP-complete problem: 3-satisfiability problem.Theorem12 shows that we are unable to find a polynomial time algorithm to determine bondage numbers of general graphs unless NP=P. At the same time, this result also shows that the following study on the bondage number is of important significance.(i)
Find approximation polynomial algorithms with performance ratio as small as possible.(ii)
Find the lower and upper bounds with difference as small as possible.(iii)
Determine exact values for some graphs, specially well-known networks.Unfortunately, we cannot prove whether or not determining the bondage number is NP-problem since for any subsetB⊂E(G) it is not clear that there is a polynomial algorithm to verify γ(G-B)>γ(G). Since the problem of determining the domination number is NP-complete, we conjecture that it is not in NP. This is a worthwhile task to be studied further.Motivated by the linear time algorithm of Hartnell  et al. to compute the bondage number of a tree, we can make an attempt to consider whether there is a polynomial time algorithm to compute the bondage number for some special classes of graphs such as planar graphs, Cayley graphs, or graphs with some restrictions of graph-theoretical parameters such as degree, diameter, connectivity, and domination number.


## 3. Upper Bounds

By Theorem12, since we cannot find a polynomial time algorithm for determining the exact values of bondage numbers of general graphs, it is weightily significative to establish some sharp bounds on the bondage number of a graph. In this section, we survey several known upper bounds on the bondage number in terms of some other graph-theoretical parameters.


### 3.1. Most Basic Upper Bounds

We start this subsection with a simple observation.Observation 1 (Teschner [10], 1997).
LetH be a spanning subgraph obtained from a graph G by removing k edges. Then b(G)⩽b(H)+k.If we select a spanning subgraphH such that b(H)=1, then Observation 1 yields some upper bounds on the bondage number of a graph G. For example, take H=G-Ex+e and k=dG(x)-1, where e∈Ex, the following result can be obtained.Theorem 13 (Bauer et al. [7], 1983).
If there exists at least one vertexx in a graph G such that γ(G-x)⩾γ(G), then b(G)⩽dG(x)⩽Δ(G).The following early result obtained can be derived from Observation1 by taking H=G-Exy and k=d(x)+d(y)-2.Theorem 14 (Bauer et al. [7], 1983; Fink et al. [8], 1990).
b
(
G
)
⩽
d
(
x
)
+
d
(
y
)
-
1 for any two adjacent vertices x and y in a graph G; that is,
(4)b(G)⩽minxy∈E(G){dG(x)+dG(y)-1}.This theorem gives a natural corollary obtained by several authors.Corollary 15 (Bauer et al. [7], 1983; Fink et al. [8], 1990).
IfG is a graph without isolated vertices, then b(G)⩽Δ(G)+δ(G)-1.In 1999, Hartnell and Rall [11] extended Theorem 14 to the following more general case, which can be also derived from Observation 1 by taking H=G-Ex-Ey+(x,z,y) if dG(x,y)=2, where (x,z,y) is a path of length 2 in G.Theorem 16 (Hartnell and Rall [11], 1999).
b
(
G
)
⩽
d
(
x
)
+
d
(
y
)
-
1 for any distinct two vertices x and y in a graph G with dG(x,y)⩽2; that is,
(5)b(G)⩽mindG(x,y)⩽2{dG(x)+dG(y)-1}.Corollary 17 (Fink et al. [8], 1990).
If a vertex of a graphG is adjacent with two or more vertices of degree one, then b(G)=1.We remark that the bounds stated in Corollary15 and Theorem 16 are sharp. As indicated by Theorem 1, one class of graphs in which the bondage number achieves these bounds is the class of cycles whose orders are congruent to 1 modulo 3.On the other hand, Hartnell and Rall [17] sharpened the upper bound in Theorem 14 as follows, which can be also derived from Observation 1.Theorem 18 (Hartnell and Rall [17], 1994).
b
(
G
)
⩽
d
G
(
x
)
+
d
G
(
y
)
-
1
-
|
N
G
(
x
)
∩
N
G
(
y
)
| for any two adjacent vertices x and y in a graph G; that is,
(6)b(G)⩽minxy∈E(G){dG(x)+dG(y)-1-|NG(x)∩NG(y)|}.These results give simple but important upper bounds on the bondage number of a graph, and is also the foundation of almost all results on bondage numbers upper bounds obtained till now.By careful consideration of the nature of the edges from the neighbors ofx and y, Wang [18] further refined the bound in Theorem 18. For any edge xy∈E(G), NG(y) contains the following four subsets:(1)
T1(x,y)=NG[x]∩NG(y);(2)
T2(x,y)={w∈NG(y):NG(w)⊆NG(y)-x};(3)
T3(x,y)={w∈NG(y):NG(w)⊆NG(z)-x for some z∈NG(x)∩NG(y)};(4)
T4(x,y)=NG(y)∖(T1(x,y)∪T2(x,y)∪T3(x,y)).The illustrations ofT1(x,y), T2(x,y), T3(x,y), and T4(x,y) are shown in Figure 2 (corresponding vertices pointed by dashed arrows).Figure 2
Illustration ofTi(x,y) for i=1,2,3,4.Theorem 19 (Wang [18], 1996).
For any nonempty graphG,
(7)b(G)⩽minxy∈E(G){dG(x)+|T4(x,y)|}.The graph in Figure2 shows that the upper bound given in Theorem 19 is better than that in Theorems 16 and 18, for the upper bounds obtained from these two theorems are dG(x)+dG(y)-1=11 and dG(x)+dG(y)-|NG(x)∩NG(y)|=9, respectively, while the upper bound given by Theorem 19 is dG(x)+|T4(x,y)|=6.The following result is also an improvement of Theorem14, in which t=2.Theorem 20 (Teschner [10], 1997).
IfG contains a complete subgraph Kt with t⩾2, then b(G)⩽minxy∈E(Kt){dG(x)+dG(y)-t+1}.Following Fricke  et al. [19], a vertex x of a graph G is γ-good if x belongs to some γ-set of G and γ-bad if x belongs to no γ-set of G. Let A(G) be the set of γ-good vertices, and let B(G) be the set of γ-bad vertices in G. Clearly, {A(G),B(G)} is a partition of V(G). Note there exists some x∈A such that γ(G-x)=γ(G), say, one end-vertex of P5. Samodivkin [20] presented some sharp upper bounds for b(G) in terms of γ-good and γ-bad vertices of G.Theorem 21 (Samodivkin [20], 2008).
LetG be a graph.(a)
LetC(G)={x∈V(G):γ(G-x)⩾γ(G)}. If C(G)≠∅, then
(8)b(G)⩽min{dG(x)+γ(G)-γ(G-x):x∈C(G)}.(b)
IfB≠∅, then
(9)b(G)⩽min{|NG(x)∩A|:x∈B(G)}.Theorem 22 (Samodivkin [20], 2008).
LetG be a graph. If A+(G)={x∈A(G):dG(x)⩾1  and γ(G-x)<γ(G)}≠∅, then
(10)b(G)⩽minx∈A+(G),y∈B(G-x){dG(x)+|NG(y)∩A(G-x)|}.Proposition 23 (Samodivkin [20], 2008).
Under the notation of Theorem19, if x∈A+(G), then (T1(x,y)-{x})∪T2(x,y)∪T3(x,y)⊆NG(y)∖B(G-x).By Proposition23, if x∈A+(G), then
(11)dG(x)+miny∈NG(x){|T4(x,y)|}⩾dG(x)+miny∈NG(x){|NG(y)∩A(G-x)|}⩾dG(x)+miny∈B(G-x){|NG(y)∩A(G-x)|}.
Hence, Theorem 19 can be seen to follow from Theorem 22. Any graph G with b(G) achieving the upper bound in Theorem 19 can be used to show that the bound in Theorem 22 is sharp.Lett⩾2 be an integer. Samodivkin [20] constructed a very interesting graph Gt to show that the upper bound in Theorem 22 is better than the known bounds. Let H0,H1,H2,…,Ht+1 be mutually vertex-disjoint graphs such that H0≅K2, Ht+1≅Kt+3 and Hi≅Kt+3-e for each i=1,2,…,t. Let V(H0)={x,y}, xt+1∈V(Ht+1) and xi1,xi2∈V(Hi),xi1xi2∉E(Hi) for each i=1,2,…,t. The graph Gt is defined as follows:
(12)V(Gt)=⋃k=0t+1V(Hk),E(Gt)=(⋃k=0t+1E(Hk))∪(⋃i=1t{xxi1,xxi2})∪{xxt+1}.
Such a constructed graph Gt is shown in Figure 3 when t=2.Figure 3
The graphG2.Observe thatγ(Gt)=t+2, A(Gt)=V(Gt), dGt(x)=2t+2, dGt(xt+1)=t+3, dGt(y)=1, and dGt(z)=t+2 for each z∈V(Gt-{x,y,xt+1}). Moreover, γ(G-y)<γ(G) and γ(Gt-z)=γ(Gt) for any z∈V(Gt)-{y}. Hence, each of the bounds stated in Theorems 13–20 is greater than or equals t+2.Consider the graphGt-xy. Clearly, γ(Gt-xy)=γ(Gt) and
(13)B(Gt-xy)=B(Gt-y)={x}∪V(Ht+1-xt+1)∪(⋃k=1t{xk1,xk2}).
Therefore, NGt(x)∩G(Gt-y)={xt+1} which implies that the upper bound stated in Theorem 22 is equal to dGt(y)+|{xt+1}|=2. Clearly, b(Gt)=2, and hence this bound is sharp for Gt.From the graphGt, we obtain the following statement immediately.Proposition 24.
For every integert⩾2, there is a graph G such that the difference between any upper bound stated in Theorems 13–20 and the upper bound in Theorem 22 is equal to t.Although Theorem22 supplies us with the upper bound that is closer to b(G) for some graph G than what any one of Theorems 13–20 provides, it is not easy to determine the sets A+(G) and B(G) mentioned in Theorem 22 for an arbitrary graph G. Thus, the upper bound given in Theorem 22 is of theoretical importance, but not applied since, until now, we have not found a new class of graphs whose bondage numbers are determined by Theorem 22.The above-mentioned upper bounds on the bondage number are involved in only degrees of two vertices. Hartnell and Rall [11] established an upper bound on b(G) in terms of the numbers of vertices and edges of G with order n. For any connected graph G, let δ-(G) represent the average degree of vertices in G; that is, δ-(G)=(1/n)∑x∈VdG(x). Hartnell and Rall first discovered the following proposition.Proposition 25.
For any connected graphG, there exist two vertices x and y with distance at most two and with the property that dG(x)+dG(y)⩽2δ-(G).Using Proposition25 and Theorem 16, Hartnell and Rall gave the following bound.Theorem 26 (Hartnell and Rall [11], 1999).
b
(
G
)
⩽
2
δ
-
(
G
)
-
1 for any connected graph G.Note that2ε=nδ-(G) for any graph G with order n and size ε. Theorem 26 implies the following bound in terms of order n and size ε.Corollary 27.
b
(
G
)
⩽
(
4
ε
/
n
)
-
1 for any connected graph G with order n and size ε.A lower bound onε in terms of order n and the bondage number is obtained from Corollary 28 immediately.Corollary 28.
ε
⩾
(
n
/
4
)
(
b
(
G
)
+
1
) for any connected graph G with order n and size ε.Hartnell and Rall [11] gave some graphs G with order n to show that for each value of b(G); the lower bound on ε(G) given in the Corollary 28 is sharp for some values of n.


### 3.2. Bounds Implied by Connectivity

Useκ(G) and λ(G) to denote the vertex-connectivity and the edge-connectivity of a connected graph G, respectively, which are the minimum numbers of vertices and edges whose removal result in G disconnected. The famous Whitney inequality is stated as κ(G)⩽λ(G)⩽δ(G) for any graph or digraph G. Corollary 15 is improved by several authors as follows.Theorem 29 (Hartnell and Rall [17], 1994; Teschner [10], 1997).
IfG is a connected graph, then b(G)⩽λ(G)+Δ(G)-1.The upper bound given in Theorem29 can be attained. For example, a cycle C3k+1 with k⩾1, b(C3k+1)=3 by Theorem 1. Since κ(C3k+1)=λ(C3k+1)=2, we have κ(C3k+1)+λ(C3k+1)-1=2+2-1=3=b(C3k+1).Motivated by Corollary15, Theorems 29, and the Whitney inequality, Dunbar  et al. [21] naturally proposed the following conjecture.Conjecture 30.
IfG is a connected graph, then b(G)⩽Δ(G)+κ(G)-1.However, Liu and Sun [22] presented a counterexample to this conjecture. They first constructed a graph H showed in Figure 4 with γ(H)=3 and b(H)=5. Then, let G be the disjoint union of two copies of H by identifying two vertices of degree two. They proved that b(G)⩾5. Clearly, G is a 4-regular graph with κ(G)=1 and λ(G)=2, and so b(G)⩽5 by Theorem 29. Thus, b(G)=5>4=Δ(G)+κ(G)-1.Figure 4
A graphH with γ(H)=3 and b(H)=5.With a suspicion of the relationship between the bondage number and the vertex-connectivity of a graph, the following conjecture is proposed.Conjecture 31 (Liu and Sun [22], 2003).
For any positive integerr, there exists a connected graph G such that b(G)⩾Δ(G)+κ(G)+r.To the knowledge of the author, until now no results have been known about this conjecture.We conclude this subsection with the following remarks. From Theorem29, if Conjecture 31 holds for some connected graph G, then λ(G)>κ(G)+r, which implies that G is of large edge-connectivity and small vertex-connectivity. Use ξ(G) to denote the minimum edge-degree of G; that is,
(14)ξ(G)=minxy∈E(G){dG(x)+dG(y)-2}.
Theorem 14 implies the following result.Proposition 32.
b
(
G
)
⩽
ξ
(
G
)
+
1 for any graph G.Useλ′(G) to denote the restricted edge-connectivity of a connected graph G, which is the minimum number of edges whose removal result in G disconnected and no isolated vertices.Proposition 33 (Esfahanian and Hakimi [23], 1988).
IfG is neither K1,n nor K3, then λ′(G)⩽ξ(G).Combining Propositions32 and 33, we propose a conjecture.Conjecture 34.
If a connectedG is neither K1,n nor K3, then b(G)⩽δ(G)+λ′(G)-1.A cycleC3k+1 also satisfies b(C3k+1)=3=δ(C3k+1)+λ′(C3k+1)-1 since λ′(C3k+1)=δ(C3k+1)=2 for any integer k⩾1.For the graphH shown in Figure 4, λ′(H)=4 and δ(H)=2, and so b(H)=5=δ(H)+λ′(H)-1.For the4-regular graph G constructed by Liu and Sun [22] obtained from the disjoint union of two copies of the graph H showed in Figure 4 by identifying two vertices of degree two, we have b(G)⩾5. Clearly, λ′(G)=2. Thus, b(G)=5=δ(G)+λ′(G)-1.For the4-regular graph Gt constructed by Samodivkin [20], see Figure 3 for t=2, b(Gt)=2. Clearly, δ(Gt)=1 and λ′(G)=2. Thus, b(G)=2=δ(G)+λ′(G)-1.These examples show that if Conjecture34 is true then the given upper bound is tight.


### 3.3. Bounds Implied by Degree Sequence

Now let us return to Theorem16, from which Teschner [10] obtained some other bounds in terms of the degree sequences. The degree sequenceπ(G) of a graph G with vertex-set V={x1,x2,…,xn} is the sequence π=(d1,d2,…,dn) with d1⩽d2⩽⋯⩽dn, where di=dG(xi) for each i=1,2,…,n. The following result is essentially a corollary of Theorem 16.Theorem 35 (Teschner [10], 1997).
LetG be a nonempty graph with degree sequence π(G). If α2(G)=t, then b(G)⩽dt+dt+1-1.Combining Theorem35 with Proposition 10 (i.e., α2(G)⩽γ(G)), we have the following corollary.Corollary 36 (Teschner [10], 1997).
LetG be a nonempty graph with the degree sequence π(G). If γ(G)=γ, then b(G)⩽dγ+dγ+1-1.In [10], Teschner showed that these two bounds are sharp for arbitrarily many graphs. Let H=C3k+1+{x1x4,x1x3k-1}, where C3k+1 is a cycle (x1,x2,…,x3k+1,x1) for any integer k⩾2. Then γ(H)=k+1 and so b(H)⩽2+2-1=3 by Corollary 36. Since C3k+1 is a spanning subgraph of H and γ(G)=γ(H), Observation 1 yields that b(H)⩾b(C3k+1)=3, and so b(H)=3.Although various upper bounds have been established as the above, we find that the appearance of these bounds is essentially based upon the local structures of a graph, precisely speaking, the structures of the neighborhoods of two vertices within distance 2. Even if these bounds can be achieved by some special graphs, it is more often not the case. The reason lies essentially in the definition of the bondage number, which is the minimum value among all bondage sets, an integral property of a graph. While it easy to find upper bounds just by choosing some bondage set, the gap between the exact value of the bondage number and such a bound obtained only from local structures of a graph is often large. For example, a starK1,Δ, however large Δ is, b(K1,Δ)=1. Therefore, one has been longing for better bounds upon some integral parameters. However, as what we will see below, it is difficult to establish such upper bounds.


### 3.4. Bounds inγ-Critical Graphs

A graphG is called a vertex domination-critical graph (vc-graph or γ-critical for short) if γ(G-x)<γ(G) for any x∈V(G), proposed by Brigham et al. [24] in 1988. Several families of graphs are known to be γ-critical. From definition, it is clear that if G is a γ-critical graph, then γ(G)⩾2. The class of γ-critical graphs with γ=2 is characterized as follows.Proposition 37 (Brigham et al.  [24], 1988).
A graphG with γ(G)=2 is a γ-critical graph if and only if G is a complete graph K2t (t⩾2) with a perfect matching removed.A more interesting family is composed of then-critical graphs Gm,n defined for m,n⩾2 by the circulant undirected graph G(N,±S), where N=(m+1)(n-1)+1 and S={1,2,…,⌊m/2⌋}, in which V(G(N,±S))=N and E(G(N,±S))={ij:|j-i|≡s(modN),s∈S}.The reason whyγ-critical graphs are of special interest in this context is easy to see that they play an important role in study of the bondage number. For instance, it immediately follows from Theorem 13 that if b(G)>Δ(G) then G is a γ-critical graph. The γ-critical graphs are defined exactly in this way. In order to find graphs G with a high bondage number (i.e., higher than Δ(G)) and beyond its general upper bounds for the bondage number, we, therefore, have to look at γ-critical graphs.The bondage numbers of someγ-critical graphs have been examined by several authors; see, for example, [10, 20, 25, 26]. From Theorem 13, we know that the bondage number of a graph G is bounded from above by Δ(G) if G is not a γ-critical graph. For γ-critical graphs, it is more difficult to find an upper bound. We will see that the bondage numbers of γ-critical graphs in general are not even bounded from above by Δ+c for any fixed natural number c.In this subsection, we introduce some upper bounds for the bondage number of aγ-critical graph. By Proposition 37, we easily obtain the following result.Theorem 38.
IfG is a γ-critical graph with γ(G)=2, then b(G)⩽Δ+1.In Section4, by Theorem 59, we will see that the equality in Theorem 38 holds; that is, b(G)=Δ+1 if G is a γ-critical graph with γ(G)=2.Theorem 39 (Teschner [10], 1997).
LetG be a γ-critical graph with degree sequence π(G). Then b(G)⩽max{Δ(G)+1,d1+d2+⋯+dγ-1}, where γ=γ(G).As we mentioned above, ifG is a γ-critical graph with γ(G)=2, then b(G)=Δ+1, which shows that the bound given in Theorem 39 can be attained for γ=2. However, we have not known whether this bound is tight for general γ⩾3. Theorem 39 gives the following corollary immediately.Corollary 40 (Teschner [10], 1997).
LetG be a γ-critical graph with degree sequence π(G). If γ(G)=3, then b(G)⩽max{Δ(G)+1,δ(G)+d2}.From Theorem38 and Corollary 40, we have b(G)⩽2Δ(G) if G is a γ-critical graph with γ(G)⩽3. The following result shows that this bound is not tight.Theorem 41 (Teschner [26], 1995).
LetG be a γ-critical graph graph with γ(G)⩽3. Then b(G)⩽(3/2)Δ(G).Until now, we have not known whether the bound given in Theorem41 is tight or not. We state two conjectures on γ-critical graphs proposed by Samodivkin [20]. The first of them is motivated by Theorems 22 and 19.Conjecture 42 (Samodivkin [20], 2008).
For every connected nontrivialγ-critical graph G,
(15)minx∈A+(G),y∈B(G-x){dG(x)+|NG(y)∩A(G-x)|}⩽32Δ(G).To state the second conjecture, we need the following result onγ-critical graphs.Proposition 43.
IfG is a γ-critical graph, then υ(G)⩽(Δ(G)+1)(γ(G)-1)+1; moreover, if the equality holds, then G is regular.The upper bound in Proposition43 is sharp in the sense that equality holds for the infinite class of γ-critical graphs Gm,n defined in the beginning of this subsection. In Proposition 43, the first result is due to Brigham et al. [24] in 1988; the second is due to Fulman et al. [27] in 1995.For aγ-critical graph G with γ=3, by Proposition 43, υ(G)⩽2Δ(G)+3.Theorem 44 (Teschner [26], 1995).
IfG is a γ-critical graph with γ=3 and υ(G)=2Δ(G)+3, then b(G)⩽Δ+1.We have not known yet whether the equality in Theorem44 holds or not. However, Samodivkin proposed the following conjecture.Conjecture 45 (Samodivkin [20], 2008).
IfG is a γ-critical graph with (Δ(G)+1)(γ-1)+1 vertices, then b(G)=Δ(G)+1.In general, based on Theorem41, Teschner proposed the following conjecture.Conjecture 46 (Teschner [26], 1995).
IfG is a γ-critical graph, then b(G)⩽(3/2)Δ(G) for γ⩾4.We conclude this subsection with some remarks. Graphs which are minimal or critical with respect to a given property or parameter frequently play an important role in the investigation of that property or parameter. Not only are such graphs of considerable interest in their own right, but also a knowledge of their structure often aids in the development of the general theory. In particular, when investigating any finite structure, a great number of results are proven by induction. Consequently, it is desirable to learn as much as possible about those graphs that are critical with respect to a given property or parameter so as to aid and abet such investigations.In this subsection, we survey some results on the bondage number forγ-critical graphs. Although these results are not very perfect, they provides a feasible method to approach the bondage number from different viewpoints. In particular, the methods given in Teschner [26] worth further exploration and development.The following proposition is maybe useful for us to further investigate the bondage number of aγ-critical graph.Proposition 47 (Brigham et al. [24], 1988).
IfG has a nonisolated vertex x such that the subgraph induced by NG(x) is a complete graph, then G is not γ-critical.This simple fact shows that anyγ-critical graph contains no vertices of degree one.


### 3.5. Bounds Implied by Domination

In the preceding subsection, we introduced some upper bounds on the bondage numbers forγ-critical graphs by consideration of dominations. In this subsection, we introduce related results for a general graph with given domination number.Theorem 48 (Fink et al. [8], 1990).
For any connected graphG of order n(⩾2),(a)
b(G)⩽n-1;(b)
b(G)⩽Δ(G)+1 if γ(G)=2;(c)
b(G)⩽n-γ(G)+1.While the upper bound ofn-1 on b(G) is not particularly good for many classes of graphs (e.g., trees and cycles), it is an attainable bound. For example, if G is a complete t-partite graph Kt(2) for t=n/2 and n⩽4 an even integer, then the three bounds on b(G) in Theorem 48 are sharp.Teschner [26] consider a graph with γ(G)=1 or γ(G)=2. The next result is almost trivial but useful.Lemma 49.
LetG be a graph with order n and γ(G)=1, t the number of vertices of degree n-1. Then b(G)=⌈t/2⌉.Sincet⩽Δ(G) clearly, Lemma 49 yields the following result immediately.Theorem 50 (Teschner [26], 1995).
b
(
G
)
⩽
(
1
/
2
)
Δ
+
1 for any graph G with γ(G)=1.For a complete graphK2k+1, b(K2k+1)=k+1=(1/2)Δ+1, which shows that the upper bound given in Theorem 50 can be attained. For a graph G with γ(G)=2, by Theorem 59 later, the upper bound given in Theorem 48 (b) can be also attained by a 2-critical graph (see Proposition 37).


### 3.6. Two Conjectures

In 1990, when Fink  et al. [8] introduced the concept of the bondage number; they proposed the following conjecture.Conjecture 51.
b
(
G
)
⩽
Δ
(
G
)
+
1 for any nonempty graph G.Although some results partially support Conjecture51, Teschner [28] in 1993 found a counterexample to this conjecture, the cartesian product K3×K3, which shows that b(G)=Δ(G)+2.If a graphG is a counterexample to Conjecture 51, it must be a γ-critical graph by Theorem 13. That is why the vertex domination-critical graphs are of special interest in the literature.Now, we return to Conjecture51. Hartnell and Rall [17] and Teschner [29], independently, proved that b(G) can be much greater than Δ(G) by showing the following result.Theorem 52 (Hartnell and Rall [17], 1994; Teschner [29]. 1996).
For an integern⩾3, let Gn be the cartesian product Kn×Kn. Then b(Gn)=3(n-1)=(3/2)Δ(Gn).This theorem shows that there exist no upper bounds of the formb(G)⩽Δ(G)+c for any integer c. Teschner [26] proved that b(G)⩽(3/2)Δ(G) for any graph G with γ(G)⩽2 (see Theorems 50 and 48) and for γ-critical graphs with γ(G)=3 and proposed the following conjecture.Conjecture 53 (Teschner [26], 1995).
b
(
G
)

⩽

(
3
/
2
)
Δ
(
G
) for any graph G.We believe that this conjecture is true, but so far no much work about it has been known.


## 3.1. Most Basic Upper Bounds

We start this subsection with a simple observation.Observation 1 (Teschner [10], 1997).
LetH be a spanning subgraph obtained from a graph G by removing k edges. Then b(G)⩽b(H)+k.If we select a spanning subgraphH such that b(H)=1, then Observation 1 yields some upper bounds on the bondage number of a graph G. For example, take H=G-Ex+e and k=dG(x)-1, where e∈Ex, the following result can be obtained.Theorem 13 (Bauer et al. [7], 1983).
If there exists at least one vertexx in a graph G such that γ(G-x)⩾γ(G), then b(G)⩽dG(x)⩽Δ(G).The following early result obtained can be derived from Observation1 by taking H=G-Exy and k=d(x)+d(y)-2.Theorem 14 (Bauer et al. [7], 1983; Fink et al. [8], 1990).
b
(
G
)
⩽
d
(
x
)
+
d
(
y
)
-
1 for any two adjacent vertices x and y in a graph G; that is,
(4)b(G)⩽minxy∈E(G){dG(x)+dG(y)-1}.This theorem gives a natural corollary obtained by several authors.Corollary 15 (Bauer et al. [7], 1983; Fink et al. [8], 1990).
IfG is a graph without isolated vertices, then b(G)⩽Δ(G)+δ(G)-1.In 1999, Hartnell and Rall [11] extended Theorem 14 to the following more general case, which can be also derived from Observation 1 by taking H=G-Ex-Ey+(x,z,y) if dG(x,y)=2, where (x,z,y) is a path of length 2 in G.Theorem 16 (Hartnell and Rall [11], 1999).
b
(
G
)
⩽
d
(
x
)
+
d
(
y
)
-
1 for any distinct two vertices x and y in a graph G with dG(x,y)⩽2; that is,
(5)b(G)⩽mindG(x,y)⩽2{dG(x)+dG(y)-1}.Corollary 17 (Fink et al. [8], 1990).
If a vertex of a graphG is adjacent with two or more vertices of degree one, then b(G)=1.We remark that the bounds stated in Corollary15 and Theorem 16 are sharp. As indicated by Theorem 1, one class of graphs in which the bondage number achieves these bounds is the class of cycles whose orders are congruent to 1 modulo 3.On the other hand, Hartnell and Rall [17] sharpened the upper bound in Theorem 14 as follows, which can be also derived from Observation 1.Theorem 18 (Hartnell and Rall [17], 1994).
b
(
G
)
⩽
d
G
(
x
)
+
d
G
(
y
)
-
1
-
|
N
G
(
x
)
∩
N
G
(
y
)
| for any two adjacent vertices x and y in a graph G; that is,
(6)b(G)⩽minxy∈E(G){dG(x)+dG(y)-1-|NG(x)∩NG(y)|}.These results give simple but important upper bounds on the bondage number of a graph, and is also the foundation of almost all results on bondage numbers upper bounds obtained till now.By careful consideration of the nature of the edges from the neighbors ofx and y, Wang [18] further refined the bound in Theorem 18. For any edge xy∈E(G), NG(y) contains the following four subsets:(1)
T1(x,y)=NG[x]∩NG(y);(2)
T2(x,y)={w∈NG(y):NG(w)⊆NG(y)-x};(3)
T3(x,y)={w∈NG(y):NG(w)⊆NG(z)-x for some z∈NG(x)∩NG(y)};(4)
T4(x,y)=NG(y)∖(T1(x,y)∪T2(x,y)∪T3(x,y)).The illustrations ofT1(x,y), T2(x,y), T3(x,y), and T4(x,y) are shown in Figure 2 (corresponding vertices pointed by dashed arrows).Figure 2
Illustration ofTi(x,y) for i=1,2,3,4.Theorem 19 (Wang [18], 1996).
For any nonempty graphG,
(7)b(G)⩽minxy∈E(G){dG(x)+|T4(x,y)|}.The graph in Figure2 shows that the upper bound given in Theorem 19 is better than that in Theorems 16 and 18, for the upper bounds obtained from these two theorems are dG(x)+dG(y)-1=11 and dG(x)+dG(y)-|NG(x)∩NG(y)|=9, respectively, while the upper bound given by Theorem 19 is dG(x)+|T4(x,y)|=6.The following result is also an improvement of Theorem14, in which t=2.Theorem 20 (Teschner [10], 1997).
IfG contains a complete subgraph Kt with t⩾2, then b(G)⩽minxy∈E(Kt){dG(x)+dG(y)-t+1}.Following Fricke  et al. [19], a vertex x of a graph G is γ-good if x belongs to some γ-set of G and γ-bad if x belongs to no γ-set of G. Let A(G) be the set of γ-good vertices, and let B(G) be the set of γ-bad vertices in G. Clearly, {A(G),B(G)} is a partition of V(G). Note there exists some x∈A such that γ(G-x)=γ(G), say, one end-vertex of P5. Samodivkin [20] presented some sharp upper bounds for b(G) in terms of γ-good and γ-bad vertices of G.Theorem 21 (Samodivkin [20], 2008).
LetG be a graph.(a)
LetC(G)={x∈V(G):γ(G-x)⩾γ(G)}. If C(G)≠∅, then
(8)b(G)⩽min{dG(x)+γ(G)-γ(G-x):x∈C(G)}.(b)
IfB≠∅, then
(9)b(G)⩽min{|NG(x)∩A|:x∈B(G)}.Theorem 22 (Samodivkin [20], 2008).
LetG be a graph. If A+(G)={x∈A(G):dG(x)⩾1  and γ(G-x)<γ(G)}≠∅, then
(10)b(G)⩽minx∈A+(G),y∈B(G-x){dG(x)+|NG(y)∩A(G-x)|}.Proposition 23 (Samodivkin [20], 2008).
Under the notation of Theorem19, if x∈A+(G), then (T1(x,y)-{x})∪T2(x,y)∪T3(x,y)⊆NG(y)∖B(G-x).By Proposition23, if x∈A+(G), then
(11)dG(x)+miny∈NG(x){|T4(x,y)|}⩾dG(x)+miny∈NG(x){|NG(y)∩A(G-x)|}⩾dG(x)+miny∈B(G-x){|NG(y)∩A(G-x)|}.
Hence, Theorem 19 can be seen to follow from Theorem 22. Any graph G with b(G) achieving the upper bound in Theorem 19 can be used to show that the bound in Theorem 22 is sharp.Lett⩾2 be an integer. Samodivkin [20] constructed a very interesting graph Gt to show that the upper bound in Theorem 22 is better than the known bounds. Let H0,H1,H2,…,Ht+1 be mutually vertex-disjoint graphs such that H0≅K2, Ht+1≅Kt+3 and Hi≅Kt+3-e for each i=1,2,…,t. Let V(H0)={x,y}, xt+1∈V(Ht+1) and xi1,xi2∈V(Hi),xi1xi2∉E(Hi) for each i=1,2,…,t. The graph Gt is defined as follows:
(12)V(Gt)=⋃k=0t+1V(Hk),E(Gt)=(⋃k=0t+1E(Hk))∪(⋃i=1t{xxi1,xxi2})∪{xxt+1}.
Such a constructed graph Gt is shown in Figure 3 when t=2.Figure 3
The graphG2.Observe thatγ(Gt)=t+2, A(Gt)=V(Gt), dGt(x)=2t+2, dGt(xt+1)=t+3, dGt(y)=1, and dGt(z)=t+2 for each z∈V(Gt-{x,y,xt+1}). Moreover, γ(G-y)<γ(G) and γ(Gt-z)=γ(Gt) for any z∈V(Gt)-{y}. Hence, each of the bounds stated in Theorems 13–20 is greater than or equals t+2.Consider the graphGt-xy. Clearly, γ(Gt-xy)=γ(Gt) and
(13)B(Gt-xy)=B(Gt-y)={x}∪V(Ht+1-xt+1)∪(⋃k=1t{xk1,xk2}).
Therefore, NGt(x)∩G(Gt-y)={xt+1} which implies that the upper bound stated in Theorem 22 is equal to dGt(y)+|{xt+1}|=2. Clearly, b(Gt)=2, and hence this bound is sharp for Gt.From the graphGt, we obtain the following statement immediately.Proposition 24.
For every integert⩾2, there is a graph G such that the difference between any upper bound stated in Theorems 13–20 and the upper bound in Theorem 22 is equal to t.Although Theorem22 supplies us with the upper bound that is closer to b(G) for some graph G than what any one of Theorems 13–20 provides, it is not easy to determine the sets A+(G) and B(G) mentioned in Theorem 22 for an arbitrary graph G. Thus, the upper bound given in Theorem 22 is of theoretical importance, but not applied since, until now, we have not found a new class of graphs whose bondage numbers are determined by Theorem 22.The above-mentioned upper bounds on the bondage number are involved in only degrees of two vertices. Hartnell and Rall [11] established an upper bound on b(G) in terms of the numbers of vertices and edges of G with order n. For any connected graph G, let δ-(G) represent the average degree of vertices in G; that is, δ-(G)=(1/n)∑x∈VdG(x). Hartnell and Rall first discovered the following proposition.Proposition 25.
For any connected graphG, there exist two vertices x and y with distance at most two and with the property that dG(x)+dG(y)⩽2δ-(G).Using Proposition25 and Theorem 16, Hartnell and Rall gave the following bound.Theorem 26 (Hartnell and Rall [11], 1999).
b
(
G
)
⩽
2
δ
-
(
G
)
-
1 for any connected graph G.Note that2ε=nδ-(G) for any graph G with order n and size ε. Theorem 26 implies the following bound in terms of order n and size ε.Corollary 27.
b
(
G
)
⩽
(
4
ε
/
n
)
-
1 for any connected graph G with order n and size ε.A lower bound onε in terms of order n and the bondage number is obtained from Corollary 28 immediately.Corollary 28.
ε
⩾
(
n
/
4
)
(
b
(
G
)
+
1
) for any connected graph G with order n and size ε.Hartnell and Rall [11] gave some graphs G with order n to show that for each value of b(G); the lower bound on ε(G) given in the Corollary 28 is sharp for some values of n.


## 3.2. Bounds Implied by Connectivity

Useκ(G) and λ(G) to denote the vertex-connectivity and the edge-connectivity of a connected graph G, respectively, which are the minimum numbers of vertices and edges whose removal result in G disconnected. The famous Whitney inequality is stated as κ(G)⩽λ(G)⩽δ(G) for any graph or digraph G. Corollary 15 is improved by several authors as follows.Theorem 29 (Hartnell and Rall [17], 1994; Teschner [10], 1997).
IfG is a connected graph, then b(G)⩽λ(G)+Δ(G)-1.The upper bound given in Theorem29 can be attained. For example, a cycle C3k+1 with k⩾1, b(C3k+1)=3 by Theorem 1. Since κ(C3k+1)=λ(C3k+1)=2, we have κ(C3k+1)+λ(C3k+1)-1=2+2-1=3=b(C3k+1).Motivated by Corollary15, Theorems 29, and the Whitney inequality, Dunbar  et al. [21] naturally proposed the following conjecture.Conjecture 30.
IfG is a connected graph, then b(G)⩽Δ(G)+κ(G)-1.However, Liu and Sun [22] presented a counterexample to this conjecture. They first constructed a graph H showed in Figure 4 with γ(H)=3 and b(H)=5. Then, let G be the disjoint union of two copies of H by identifying two vertices of degree two. They proved that b(G)⩾5. Clearly, G is a 4-regular graph with κ(G)=1 and λ(G)=2, and so b(G)⩽5 by Theorem 29. Thus, b(G)=5>4=Δ(G)+κ(G)-1.Figure 4
A graphH with γ(H)=3 and b(H)=5.With a suspicion of the relationship between the bondage number and the vertex-connectivity of a graph, the following conjecture is proposed.Conjecture 31 (Liu and Sun [22], 2003).
For any positive integerr, there exists a connected graph G such that b(G)⩾Δ(G)+κ(G)+r.To the knowledge of the author, until now no results have been known about this conjecture.We conclude this subsection with the following remarks. From Theorem29, if Conjecture 31 holds for some connected graph G, then λ(G)>κ(G)+r, which implies that G is of large edge-connectivity and small vertex-connectivity. Use ξ(G) to denote the minimum edge-degree of G; that is,
(14)ξ(G)=minxy∈E(G){dG(x)+dG(y)-2}.
Theorem 14 implies the following result.Proposition 32.
b
(
G
)
⩽
ξ
(
G
)
+
1 for any graph G.Useλ′(G) to denote the restricted edge-connectivity of a connected graph G, which is the minimum number of edges whose removal result in G disconnected and no isolated vertices.Proposition 33 (Esfahanian and Hakimi [23], 1988).
IfG is neither K1,n nor K3, then λ′(G)⩽ξ(G).Combining Propositions32 and 33, we propose a conjecture.Conjecture 34.
If a connectedG is neither K1,n nor K3, then b(G)⩽δ(G)+λ′(G)-1.A cycleC3k+1 also satisfies b(C3k+1)=3=δ(C3k+1)+λ′(C3k+1)-1 since λ′(C3k+1)=δ(C3k+1)=2 for any integer k⩾1.For the graphH shown in Figure 4, λ′(H)=4 and δ(H)=2, and so b(H)=5=δ(H)+λ′(H)-1.For the4-regular graph G constructed by Liu and Sun [22] obtained from the disjoint union of two copies of the graph H showed in Figure 4 by identifying two vertices of degree two, we have b(G)⩾5. Clearly, λ′(G)=2. Thus, b(G)=5=δ(G)+λ′(G)-1.For the4-regular graph Gt constructed by Samodivkin [20], see Figure 3 for t=2, b(Gt)=2. Clearly, δ(Gt)=1 and λ′(G)=2. Thus, b(G)=2=δ(G)+λ′(G)-1.These examples show that if Conjecture34 is true then the given upper bound is tight.


## 3.3. Bounds Implied by Degree Sequence

Now let us return to Theorem16, from which Teschner [10] obtained some other bounds in terms of the degree sequences. The degree sequenceπ(G) of a graph G with vertex-set V={x1,x2,…,xn} is the sequence π=(d1,d2,…,dn) with d1⩽d2⩽⋯⩽dn, where di=dG(xi) for each i=1,2,…,n. The following result is essentially a corollary of Theorem 16.Theorem 35 (Teschner [10], 1997).
LetG be a nonempty graph with degree sequence π(G). If α2(G)=t, then b(G)⩽dt+dt+1-1.Combining Theorem35 with Proposition 10 (i.e., α2(G)⩽γ(G)), we have the following corollary.Corollary 36 (Teschner [10], 1997).
LetG be a nonempty graph with the degree sequence π(G). If γ(G)=γ, then b(G)⩽dγ+dγ+1-1.In [10], Teschner showed that these two bounds are sharp for arbitrarily many graphs. Let H=C3k+1+{x1x4,x1x3k-1}, where C3k+1 is a cycle (x1,x2,…,x3k+1,x1) for any integer k⩾2. Then γ(H)=k+1 and so b(H)⩽2+2-1=3 by Corollary 36. Since C3k+1 is a spanning subgraph of H and γ(G)=γ(H), Observation 1 yields that b(H)⩾b(C3k+1)=3, and so b(H)=3.Although various upper bounds have been established as the above, we find that the appearance of these bounds is essentially based upon the local structures of a graph, precisely speaking, the structures of the neighborhoods of two vertices within distance 2. Even if these bounds can be achieved by some special graphs, it is more often not the case. The reason lies essentially in the definition of the bondage number, which is the minimum value among all bondage sets, an integral property of a graph. While it easy to find upper bounds just by choosing some bondage set, the gap between the exact value of the bondage number and such a bound obtained only from local structures of a graph is often large. For example, a starK1,Δ, however large Δ is, b(K1,Δ)=1. Therefore, one has been longing for better bounds upon some integral parameters. However, as what we will see below, it is difficult to establish such upper bounds.


## 3.4. Bounds inγ-Critical Graphs

A graphG is called a vertex domination-critical graph (vc-graph or γ-critical for short) if γ(G-x)<γ(G) for any x∈V(G), proposed by Brigham et al. [24] in 1988. Several families of graphs are known to be γ-critical. From definition, it is clear that if G is a γ-critical graph, then γ(G)⩾2. The class of γ-critical graphs with γ=2 is characterized as follows.Proposition 37 (Brigham et al.  [24], 1988).
A graphG with γ(G)=2 is a γ-critical graph if and only if G is a complete graph K2t (t⩾2) with a perfect matching removed.A more interesting family is composed of then-critical graphs Gm,n defined for m,n⩾2 by the circulant undirected graph G(N,±S), where N=(m+1)(n-1)+1 and S={1,2,…,⌊m/2⌋}, in which V(G(N,±S))=N and E(G(N,±S))={ij:|j-i|≡s(modN),s∈S}.The reason whyγ-critical graphs are of special interest in this context is easy to see that they play an important role in study of the bondage number. For instance, it immediately follows from Theorem 13 that if b(G)>Δ(G) then G is a γ-critical graph. The γ-critical graphs are defined exactly in this way. In order to find graphs G with a high bondage number (i.e., higher than Δ(G)) and beyond its general upper bounds for the bondage number, we, therefore, have to look at γ-critical graphs.The bondage numbers of someγ-critical graphs have been examined by several authors; see, for example, [10, 20, 25, 26]. From Theorem 13, we know that the bondage number of a graph G is bounded from above by Δ(G) if G is not a γ-critical graph. For γ-critical graphs, it is more difficult to find an upper bound. We will see that the bondage numbers of γ-critical graphs in general are not even bounded from above by Δ+c for any fixed natural number c.In this subsection, we introduce some upper bounds for the bondage number of aγ-critical graph. By Proposition 37, we easily obtain the following result.Theorem 38.
IfG is a γ-critical graph with γ(G)=2, then b(G)⩽Δ+1.In Section4, by Theorem 59, we will see that the equality in Theorem 38 holds; that is, b(G)=Δ+1 if G is a γ-critical graph with γ(G)=2.Theorem 39 (Teschner [10], 1997).
LetG be a γ-critical graph with degree sequence π(G). Then b(G)⩽max{Δ(G)+1,d1+d2+⋯+dγ-1}, where γ=γ(G).As we mentioned above, ifG is a γ-critical graph with γ(G)=2, then b(G)=Δ+1, which shows that the bound given in Theorem 39 can be attained for γ=2. However, we have not known whether this bound is tight for general γ⩾3. Theorem 39 gives the following corollary immediately.Corollary 40 (Teschner [10], 1997).
LetG be a γ-critical graph with degree sequence π(G). If γ(G)=3, then b(G)⩽max{Δ(G)+1,δ(G)+d2}.From Theorem38 and Corollary 40, we have b(G)⩽2Δ(G) if G is a γ-critical graph with γ(G)⩽3. The following result shows that this bound is not tight.Theorem 41 (Teschner [26], 1995).
LetG be a γ-critical graph graph with γ(G)⩽3. Then b(G)⩽(3/2)Δ(G).Until now, we have not known whether the bound given in Theorem41 is tight or not. We state two conjectures on γ-critical graphs proposed by Samodivkin [20]. The first of them is motivated by Theorems 22 and 19.Conjecture 42 (Samodivkin [20], 2008).
For every connected nontrivialγ-critical graph G,
(15)minx∈A+(G),y∈B(G-x){dG(x)+|NG(y)∩A(G-x)|}⩽32Δ(G).To state the second conjecture, we need the following result onγ-critical graphs.Proposition 43.
IfG is a γ-critical graph, then υ(G)⩽(Δ(G)+1)(γ(G)-1)+1; moreover, if the equality holds, then G is regular.The upper bound in Proposition43 is sharp in the sense that equality holds for the infinite class of γ-critical graphs Gm,n defined in the beginning of this subsection. In Proposition 43, the first result is due to Brigham et al. [24] in 1988; the second is due to Fulman et al. [27] in 1995.For aγ-critical graph G with γ=3, by Proposition 43, υ(G)⩽2Δ(G)+3.Theorem 44 (Teschner [26], 1995).
IfG is a γ-critical graph with γ=3 and υ(G)=2Δ(G)+3, then b(G)⩽Δ+1.We have not known yet whether the equality in Theorem44 holds or not. However, Samodivkin proposed the following conjecture.Conjecture 45 (Samodivkin [20], 2008).
IfG is a γ-critical graph with (Δ(G)+1)(γ-1)+1 vertices, then b(G)=Δ(G)+1.In general, based on Theorem41, Teschner proposed the following conjecture.Conjecture 46 (Teschner [26], 1995).
IfG is a γ-critical graph, then b(G)⩽(3/2)Δ(G) for γ⩾4.We conclude this subsection with some remarks. Graphs which are minimal or critical with respect to a given property or parameter frequently play an important role in the investigation of that property or parameter. Not only are such graphs of considerable interest in their own right, but also a knowledge of their structure often aids in the development of the general theory. In particular, when investigating any finite structure, a great number of results are proven by induction. Consequently, it is desirable to learn as much as possible about those graphs that are critical with respect to a given property or parameter so as to aid and abet such investigations.In this subsection, we survey some results on the bondage number forγ-critical graphs. Although these results are not very perfect, they provides a feasible method to approach the bondage number from different viewpoints. In particular, the methods given in Teschner [26] worth further exploration and development.The following proposition is maybe useful for us to further investigate the bondage number of aγ-critical graph.Proposition 47 (Brigham et al. [24], 1988).
IfG has a nonisolated vertex x such that the subgraph induced by NG(x) is a complete graph, then G is not γ-critical.This simple fact shows that anyγ-critical graph contains no vertices of degree one.


## 3.5. Bounds Implied by Domination

In the preceding subsection, we introduced some upper bounds on the bondage numbers forγ-critical graphs by consideration of dominations. In this subsection, we introduce related results for a general graph with given domination number.Theorem 48 (Fink et al. [8], 1990).
For any connected graphG of order n(⩾2),(a)
b(G)⩽n-1;(b)
b(G)⩽Δ(G)+1 if γ(G)=2;(c)
b(G)⩽n-γ(G)+1.While the upper bound ofn-1 on b(G) is not particularly good for many classes of graphs (e.g., trees and cycles), it is an attainable bound. For example, if G is a complete t-partite graph Kt(2) for t=n/2 and n⩽4 an even integer, then the three bounds on b(G) in Theorem 48 are sharp.Teschner [26] consider a graph with γ(G)=1 or γ(G)=2. The next result is almost trivial but useful.Lemma 49.
LetG be a graph with order n and γ(G)=1, t the number of vertices of degree n-1. Then b(G)=⌈t/2⌉.Sincet⩽Δ(G) clearly, Lemma 49 yields the following result immediately.Theorem 50 (Teschner [26], 1995).
b
(
G
)
⩽
(
1
/
2
)
Δ
+
1 for any graph G with γ(G)=1.For a complete graphK2k+1, b(K2k+1)=k+1=(1/2)Δ+1, which shows that the upper bound given in Theorem 50 can be attained. For a graph G with γ(G)=2, by Theorem 59 later, the upper bound given in Theorem 48 (b) can be also attained by a 2-critical graph (see Proposition 37).


## 3.6. Two Conjectures

In 1990, when Fink  et al. [8] introduced the concept of the bondage number; they proposed the following conjecture.Conjecture 51.
b
(
G
)
⩽
Δ
(
G
)
+
1 for any nonempty graph G.Although some results partially support Conjecture51, Teschner [28] in 1993 found a counterexample to this conjecture, the cartesian product K3×K3, which shows that b(G)=Δ(G)+2.If a graphG is a counterexample to Conjecture 51, it must be a γ-critical graph by Theorem 13. That is why the vertex domination-critical graphs are of special interest in the literature.Now, we return to Conjecture51. Hartnell and Rall [17] and Teschner [29], independently, proved that b(G) can be much greater than Δ(G) by showing the following result.Theorem 52 (Hartnell and Rall [17], 1994; Teschner [29]. 1996).
For an integern⩾3, let Gn be the cartesian product Kn×Kn. Then b(Gn)=3(n-1)=(3/2)Δ(Gn).This theorem shows that there exist no upper bounds of the formb(G)⩽Δ(G)+c for any integer c. Teschner [26] proved that b(G)⩽(3/2)Δ(G) for any graph G with γ(G)⩽2 (see Theorems 50 and 48) and for γ-critical graphs with γ(G)=3 and proposed the following conjecture.Conjecture 53 (Teschner [26], 1995).
b
(
G
)

⩽

(
3
/
2
)
Δ
(
G
) for any graph G.We believe that this conjecture is true, but so far no much work about it has been known.


## 4. Lower Bounds

Since the bondage number is defined as the smallest number of edges whose removal results in an increase of domination number, each constructive method that creates a concrete bondage set leads to an upper bound on the bondage number. For that reason, it is hard to find lower bounds. Nevertheless, there are still a few lower bounds.


### 4.1. Bounds Implied by Subgraphs

The first lower bound on the bondage number is gotten in terms of its spanning subgraph.Theorem 54 (Teschner [10], 1997).
LetH be a spanning subgraph of a nonempty graph G. If γ(H)=γ(G), then b(H)⩽b(G).By Theorem1, b(Cn)=3 if n≡1(mod3) and b(Cn)=2, otherwise b(Pn)=2 if n≡1(mod3) and b(Pn)=1 otherwise. From these results and Theorem 54, we get the following two corollaries.Corollary 55.
IfG is hamiltonian with order n⩾3 and γ(G)=⌈n/3⌉, then b(G)⩾2 and in addition b(G)⩾3 if n≡1(mod3).Corollary 56.
IfG with order n⩾2 has a hamiltonian path and γ(G)=⌈n/3⌉, then b(G)⩾2 if n≡1(mod3).


### 4.2. Other Bounds

Thevertex covering numberβ(G) of G is the minimum number of vertices that are incident with all edges in G. If G has no isolated vertices, then γ(G)⩽β(G) clearly. In [30], Volkmann gave a lot of graphs with β=γ.Theorem 57 (Teschner [10], 1997).
LetG be a graph. If γ(G)=β(G), then(a)
b(G)⩾δ(G);(b)
b(G)⩾δ(G)+1 if G is a γ-critical graph.The graph shown in Figure5 shows that the bound given in Theorem 57(b) is sharp. For the graph G, it is a γ-critical graph and γ(G)=β(G)=4. By Theorem 57, we have b(G)⩾3. On the other hand, b(G)⩽3 by Theorem 16. Thus, b(G)=3.Figure 5
Aγ-critical graph with β=γ=4,δ=2, and b=3.Proposition 58 (Sanchis [31], 1991).
LetG be a graph G of order n(⩾6) and size ε. If G has no isolated vertices and 3⩽γ(G)⩽n/2, then ε⩽(n-γ(G)+12).Using the idea in the proof of Theorem57, every upper bound for γ(G) can lead to a lower bound for b(G). In this way, Teschner [10] obtained another lower bound from Proposition 58.Theorem 59 (Teschner [10], 1997).
LetG be a graph G of order n(⩾6) and size ε. If 2⩽γ(G)⩽n/2-1, then(a)
b(G)⩾min{δ(G),ε-(n-γ(G)2)};(b)
b(G)⩾min{δ(G)+1,ε-(n-γ(G)2)} if G is a γ-critical graph.The lower bound in Theorem59(b) is sharp for a class of γ-critical graphs with domination number 2. Let G be the graph obtained from complete graph K2t (t⩾2) by removing a perfect matching. By Proposition 37, G is a γ-critical graph with γ(G)=2. Then b(G)⩾δ(G)+1=Δ(G)+1 by Theorem 59 and b(G)⩽Δ(G)+1 by Theorem 38, and so b(G)=Δ(G)+1=2t-1.As far as the author knows, there are no more lower bounds in the present literature. In view of applications of the bondage number, a network is vulnerable if its bondage number is small while it is stable if its bondage number is large. Therefore, better lower bounds let us learn better about the stability of networks from this point of view. Thus, it is of great significance to seek more lower bounds for various classes of graphs.


## 4.1. Bounds Implied by Subgraphs

The first lower bound on the bondage number is gotten in terms of its spanning subgraph.Theorem 54 (Teschner [10], 1997).
LetH be a spanning subgraph of a nonempty graph G. If γ(H)=γ(G), then b(H)⩽b(G).By Theorem1, b(Cn)=3 if n≡1(mod3) and b(Cn)=2, otherwise b(Pn)=2 if n≡1(mod3) and b(Pn)=1 otherwise. From these results and Theorem 54, we get the following two corollaries.Corollary 55.
IfG is hamiltonian with order n⩾3 and γ(G)=⌈n/3⌉, then b(G)⩾2 and in addition b(G)⩾3 if n≡1(mod3).Corollary 56.
IfG with order n⩾2 has a hamiltonian path and γ(G)=⌈n/3⌉, then b(G)⩾2 if n≡1(mod3).


## 4.2. Other Bounds

Thevertex covering numberβ(G) of G is the minimum number of vertices that are incident with all edges in G. If G has no isolated vertices, then γ(G)⩽β(G) clearly. In [30], Volkmann gave a lot of graphs with β=γ.Theorem 57 (Teschner [10], 1997).
LetG be a graph. If γ(G)=β(G), then(a)
b(G)⩾δ(G);(b)
b(G)⩾δ(G)+1 if G is a γ-critical graph.The graph shown in Figure5 shows that the bound given in Theorem 57(b) is sharp. For the graph G, it is a γ-critical graph and γ(G)=β(G)=4. By Theorem 57, we have b(G)⩾3. On the other hand, b(G)⩽3 by Theorem 16. Thus, b(G)=3.Figure 5
Aγ-critical graph with β=γ=4,δ=2, and b=3.Proposition 58 (Sanchis [31], 1991).
LetG be a graph G of order n(⩾6) and size ε. If G has no isolated vertices and 3⩽γ(G)⩽n/2, then ε⩽(n-γ(G)+12).Using the idea in the proof of Theorem57, every upper bound for γ(G) can lead to a lower bound for b(G). In this way, Teschner [10] obtained another lower bound from Proposition 58.Theorem 59 (Teschner [10], 1997).
LetG be a graph G of order n(⩾6) and size ε. If 2⩽γ(G)⩽n/2-1, then(a)
b(G)⩾min{δ(G),ε-(n-γ(G)2)};(b)
b(G)⩾min{δ(G)+1,ε-(n-γ(G)2)} if G is a γ-critical graph.The lower bound in Theorem59(b) is sharp for a class of γ-critical graphs with domination number 2. Let G be the graph obtained from complete graph K2t (t⩾2) by removing a perfect matching. By Proposition 37, G is a γ-critical graph with γ(G)=2. Then b(G)⩾δ(G)+1=Δ(G)+1 by Theorem 59 and b(G)⩽Δ(G)+1 by Theorem 38, and so b(G)=Δ(G)+1=2t-1.As far as the author knows, there are no more lower bounds in the present literature. In view of applications of the bondage number, a network is vulnerable if its bondage number is small while it is stable if its bondage number is large. Therefore, better lower bounds let us learn better about the stability of networks from this point of view. Thus, it is of great significance to seek more lower bounds for various classes of graphs.


## 5. Results on Graph Operations

Generally speaking, it is quite difficult to determine the exact value of the bondage number for a given graph since it strongly depends on the dominating number of the graph. Thus, determining bondage numbers for some special graphs is interesting if the dominating numbers of those graphs are known or can be easily determined. In this section, we will introduce some known results on bondage numbers for some special classes of graphs obtained by some graph operations.


### 5.1. Cartesian Product Graphs

LetG1=(V1,E1) and G2=(V2,E2) be two graphs. The Cartesian product of G1 and G2 is an undirected graph, denoted by G1×G2, where V(G1×G2)=V1×V2; two distinct vertices x1x2 and y1y2, where x1,y1∈V(G1) and x2,y2∈V(G2), are linked by an edge in G1×G2 if and only if either x1=y1 and x2y2∈E(G2), or x2=y2 and x1y1∈E(G1). The Cartesian product is a very effective method for constructing a larger graph from several specified small graphs.Theorem 60 (Dunbar et al. [21], 1998).
Forn⩾3,
(16)b(Cn×K2)={2ifn≡0or1(mod4),3ifn≡3(mod4),4ifn≡2(mod4).For the Cartesian productCn×Cm of two cycles Cn and Cm, where n⩾4 and m⩾3, Klavžar and Seifter [32] determined γ(Cn×Cm) for some n and m. For example, γ(Cn×C4)=n for n⩾3 and γ(Cn×C3)=n-⌊n/4⌋ for n⩾4. Kim [33] determined b(C3×C3)=6 and b(C4×C4)=4. For a general n⩾4, the exact values of the bondage numbers of Cn×C3 and Cn×C4 are determined as follows.Theorem 61 (Sohn et al. [34], 2007).
Forn⩾4,
(17)b(Cn×C3)={2ifn≡0(mod4),4ifn≡1or2(mod4),5ifn≡3(mod4).Theorem 62 (Kang et al. [35], 2005).
b
(
C
n
×
C
4
)
=
4 for n⩾4.For largerm and n, Huang and Xu [36] obtained the following result; see Theorem 197 for more details.Theorem 63 (Huang and Xu [36], 2008).
b
(
C
5
i
×
C
5
j
)
=
3 for any positive integers i and j.Xiang et al. [37] determined that for n⩾5,
(18)b(Cn×C5){=3ifn≡0or1(mod5),=4ifn≡2or4(mod5),⩽7ifn≡3(mod5).For the Cartesian productPn×Pm of two paths Pn and Pm, Jacobson and Kinch [38] determined γ(Pn×P2)=⌈(n+1)/2⌉, γ(Pn×P3)=n-⌊(n-1)/4⌋, and γ(Pn×P4)=n+1 if n=1,2,3,5,6,9, and n otherwise. The bondage number of Pn×Pm for n⩾4 and 2⩽m⩽4 is determined as follows (Li [39] also determined b(Pn×P2)).Theorem 64 (Hu and Xu [40], 2012).
Forn⩾4,
(19)b(Pn×P2)={1,ifn≡1(mod2)2,ifn≡0(mod2);b(Pn×P3)={1,ifn≡1or2(mod4)2,ifn≡0or3(mod4),b(Pn×P4)=1forn⩾14.From the proof of Theorem64, we find that if Pn={0,1,…,n-1} and Pm={0,1,…,m-1}, then the removal of the vertex (0,0) in Pn×Pm does not change the domination number. If m increases, the effect of (0,0) for the domination number will be smaller and smaller from the probability. Therefore, we expect it is possible that γ(Pn×Pm-(0,0))=γ(Pn×Pm) for m⩾5 and give the following conjecture.Conjecture 65.
b
(
P
n
×
P
m
)
⩽
2 for m⩾5 and n⩾4.


### 5.2. Block Graphs and Cactus Graphs

In this subsection, we introduce some results for corona graphs, block graphs, and cactus graphs.ThecoronaG1∘G2, proposed by Frucht and Harary [41], is the graph formed from a copy of G1 and υ(G1) copies of G2 by joining the ith vertex of G1 to the ith copy of G2. In particular, we are concerned with the corona H∘K1, the graph formed by adding a new vertex vi, and a new edge uivi for every vertex ui in H.Theorem 66 (Carlson and Develin [42], 2006).
b
(
H
∘
K
1
)
=
δ
(
H
)
+
1.This is a very important result, which is often used to construct a graph with required bondage number. In other words, this result implies that for any given positive integerb there is a graph G such that b(G)=b.Ablock graph is a graph whose blocks are complete graphs. Each block in a cactus graph is either a cycle or a K2. If each block of a graph is either a complete graph or a cycle, then we call this graph a block-cactus graph.Theorem 67 (Teschner [43], 1997).
b
(
G
)
≤
Δ
(
G
) for any block graph G.Teschner [43] characterized all block graphs with b(G)=Δ(G). In the same paper, Teschner found that γ-critical graphs are instrumental in determining bounds for the bondage number of cactus and block graphs and obtained the following result.Theorem 68 (Teschner [43], 1997).
b
(
G
)
⩽
3 for any nontrivial cactus graph G.This bound can be achieved byH∘K1 where H is a nontrivial cactus graph without vertices of degree one by Theorem 66. In 1998, Dunbar  et al. [21] proposed the following problem.Problem 2.
Characterize all cactus graphs with bondage number 3.Some upper bounds for block-cactus graphs were also obtained.Theorem 69 (Dunbar et al. [21], 1998).
LetG be a connected block-cactus graph with at least two blocks. Then b(G)⩽Δ(G).Theorem 70 (Dunbar et al.  [21], 1998).
LetG be a connected block-cactus graph which is neither a cactus graph nor a block graph. Then b(G)⩽Δ(G)-1.


### 5.3. Edge-Deletion and Edge-Contraction

In order to obtain further results of the bondage number, we may consider how the bondage number changes under some operations of a graphG, which remain the domination number unchanged or preserve some property of G, such as planarity. Two simple operations satisfying these requirements are the edge-deletion and the edge-contraction.Theorem 71 (Huang and Xu [44], 2012).
LetG be any graph and e∈E(G). Then b(G-e)⩾b(G)-1. Moreover, b(G-e)⩽b(G) if γ(G-e)=γ(G).From Theorem1, b(Cn-e)=b(Pn)=b(Cn)-1 for any e in Cn, which shows that the lower bound on b(G-e) is sharp. The upper bound can reach for any graph G with b(G)⩾2.Next, we consider the effect of the edge-contraction on the bondage number. Given a graphG, the  contraction of G by the edge e=xy, denoted by G/xy, is the graph obtained from G by contracting two vertices x and y to a new vertex and then deleting all multiedges. It is easy to observe that for any graph G, γ(G)-1⩽γ(G/xy)⩽γ(G) for any edge xy of G.Theorem 72 (Huang and Xu [44], 2012).
LetG be any graph and xy be any edge in G. If NG(x)∩NG(y)=∅ and γ(G/xy)=γ(G), then b(G/xy)⩾b(G).We can use examplesCn and Kn to show that the conditions of Theorem 72 are necessary and the lower bound in Theorem 72 is tight. Clearly, γ(Cn)=⌈n/3⌉ and γ(Kn)=1; for any edge xy, Cn/xy=Cn-1 and Kn/xy=Kn-1. By Theorem 1, if n≡1(mod 3), then γ(Cn/xy)<γ(G) and b(Cn/xy)=2<3=b(Cn). Thus, the result in Theorem 72 is generally invalid without the hypothesis γ(G/xy)=γ(G). Furthermore, the condition NG(x)∩NG(y)=∅ cannot be omitted even if γ(G/xy)=γ(G), since for odd n, b(Kn/xy)=⌈(n-1)/2⌉<⌈n/2⌉=b(Kn), by Theorem 1.On the other hand,b(Cn/xy)=b(Cn)=2 if n≡0(mod 3) and b(Kn/xy)=b(Kn) if n is even, which shows that the equality in b(G/xy)⩾b(G) may hold. Thus, the bound in Theorem 72 is tight. However, provided all the conditions, b(G/xy) can be arbitrarily larger than b(G). Given a graph H, let G be the graph formed from H∘K1 by adding a new vertex x and joining it to an vertex y of degree one in H∘K1. Then G/xy=H∘K1, γ(G)=γ(G/xy), and NG(x)∩NG(y)=∅. But b(G)=1 since γ(G-xy)=γ(G/xy)+1, and b(G/xy)=δ(H)+1 by Theorem 66. The gap between b(G) and b(G/xy) is δ(H).


## 5.1. Cartesian Product Graphs

LetG1=(V1,E1) and G2=(V2,E2) be two graphs. The Cartesian product of G1 and G2 is an undirected graph, denoted by G1×G2, where V(G1×G2)=V1×V2; two distinct vertices x1x2 and y1y2, where x1,y1∈V(G1) and x2,y2∈V(G2), are linked by an edge in G1×G2 if and only if either x1=y1 and x2y2∈E(G2), or x2=y2 and x1y1∈E(G1). The Cartesian product is a very effective method for constructing a larger graph from several specified small graphs.Theorem 60 (Dunbar et al. [21], 1998).
Forn⩾3,
(16)b(Cn×K2)={2ifn≡0or1(mod4),3ifn≡3(mod4),4ifn≡2(mod4).For the Cartesian productCn×Cm of two cycles Cn and Cm, where n⩾4 and m⩾3, Klavžar and Seifter [32] determined γ(Cn×Cm) for some n and m. For example, γ(Cn×C4)=n for n⩾3 and γ(Cn×C3)=n-⌊n/4⌋ for n⩾4. Kim [33] determined b(C3×C3)=6 and b(C4×C4)=4. For a general n⩾4, the exact values of the bondage numbers of Cn×C3 and Cn×C4 are determined as follows.Theorem 61 (Sohn et al. [34], 2007).
Forn⩾4,
(17)b(Cn×C3)={2ifn≡0(mod4),4ifn≡1or2(mod4),5ifn≡3(mod4).Theorem 62 (Kang et al. [35], 2005).
b
(
C
n
×
C
4
)
=
4 for n⩾4.For largerm and n, Huang and Xu [36] obtained the following result; see Theorem 197 for more details.Theorem 63 (Huang and Xu [36], 2008).
b
(
C
5
i
×
C
5
j
)
=
3 for any positive integers i and j.Xiang et al. [37] determined that for n⩾5,
(18)b(Cn×C5){=3ifn≡0or1(mod5),=4ifn≡2or4(mod5),⩽7ifn≡3(mod5).For the Cartesian productPn×Pm of two paths Pn and Pm, Jacobson and Kinch [38] determined γ(Pn×P2)=⌈(n+1)/2⌉, γ(Pn×P3)=n-⌊(n-1)/4⌋, and γ(Pn×P4)=n+1 if n=1,2,3,5,6,9, and n otherwise. The bondage number of Pn×Pm for n⩾4 and 2⩽m⩽4 is determined as follows (Li [39] also determined b(Pn×P2)).Theorem 64 (Hu and Xu [40], 2012).
Forn⩾4,
(19)b(Pn×P2)={1,ifn≡1(mod2)2,ifn≡0(mod2);b(Pn×P3)={1,ifn≡1or2(mod4)2,ifn≡0or3(mod4),b(Pn×P4)=1forn⩾14.From the proof of Theorem64, we find that if Pn={0,1,…,n-1} and Pm={0,1,…,m-1}, then the removal of the vertex (0,0) in Pn×Pm does not change the domination number. If m increases, the effect of (0,0) for the domination number will be smaller and smaller from the probability. Therefore, we expect it is possible that γ(Pn×Pm-(0,0))=γ(Pn×Pm) for m⩾5 and give the following conjecture.Conjecture 65.
b
(
P
n
×
P
m
)
⩽
2 for m⩾5 and n⩾4.


## 5.2. Block Graphs and Cactus Graphs

In this subsection, we introduce some results for corona graphs, block graphs, and cactus graphs.ThecoronaG1∘G2, proposed by Frucht and Harary [41], is the graph formed from a copy of G1 and υ(G1) copies of G2 by joining the ith vertex of G1 to the ith copy of G2. In particular, we are concerned with the corona H∘K1, the graph formed by adding a new vertex vi, and a new edge uivi for every vertex ui in H.Theorem 66 (Carlson and Develin [42], 2006).
b
(
H
∘
K
1
)
=
δ
(
H
)
+
1.This is a very important result, which is often used to construct a graph with required bondage number. In other words, this result implies that for any given positive integerb there is a graph G such that b(G)=b.Ablock graph is a graph whose blocks are complete graphs. Each block in a cactus graph is either a cycle or a K2. If each block of a graph is either a complete graph or a cycle, then we call this graph a block-cactus graph.Theorem 67 (Teschner [43], 1997).
b
(
G
)
≤
Δ
(
G
) for any block graph G.Teschner [43] characterized all block graphs with b(G)=Δ(G). In the same paper, Teschner found that γ-critical graphs are instrumental in determining bounds for the bondage number of cactus and block graphs and obtained the following result.Theorem 68 (Teschner [43], 1997).
b
(
G
)
⩽
3 for any nontrivial cactus graph G.This bound can be achieved byH∘K1 where H is a nontrivial cactus graph without vertices of degree one by Theorem 66. In 1998, Dunbar  et al. [21] proposed the following problem.Problem 2.
Characterize all cactus graphs with bondage number 3.Some upper bounds for block-cactus graphs were also obtained.Theorem 69 (Dunbar et al. [21], 1998).
LetG be a connected block-cactus graph with at least two blocks. Then b(G)⩽Δ(G).Theorem 70 (Dunbar et al.  [21], 1998).
LetG be a connected block-cactus graph which is neither a cactus graph nor a block graph. Then b(G)⩽Δ(G)-1.


## 5.3. Edge-Deletion and Edge-Contraction

In order to obtain further results of the bondage number, we may consider how the bondage number changes under some operations of a graphG, which remain the domination number unchanged or preserve some property of G, such as planarity. Two simple operations satisfying these requirements are the edge-deletion and the edge-contraction.Theorem 71 (Huang and Xu [44], 2012).
LetG be any graph and e∈E(G). Then b(G-e)⩾b(G)-1. Moreover, b(G-e)⩽b(G) if γ(G-e)=γ(G).From Theorem1, b(Cn-e)=b(Pn)=b(Cn)-1 for any e in Cn, which shows that the lower bound on b(G-e) is sharp. The upper bound can reach for any graph G with b(G)⩾2.Next, we consider the effect of the edge-contraction on the bondage number. Given a graphG, the  contraction of G by the edge e=xy, denoted by G/xy, is the graph obtained from G by contracting two vertices x and y to a new vertex and then deleting all multiedges. It is easy to observe that for any graph G, γ(G)-1⩽γ(G/xy)⩽γ(G) for any edge xy of G.Theorem 72 (Huang and Xu [44], 2012).
LetG be any graph and xy be any edge in G. If NG(x)∩NG(y)=∅ and γ(G/xy)=γ(G), then b(G/xy)⩾b(G).We can use examplesCn and Kn to show that the conditions of Theorem 72 are necessary and the lower bound in Theorem 72 is tight. Clearly, γ(Cn)=⌈n/3⌉ and γ(Kn)=1; for any edge xy, Cn/xy=Cn-1 and Kn/xy=Kn-1. By Theorem 1, if n≡1(mod 3), then γ(Cn/xy)<γ(G) and b(Cn/xy)=2<3=b(Cn). Thus, the result in Theorem 72 is generally invalid without the hypothesis γ(G/xy)=γ(G). Furthermore, the condition NG(x)∩NG(y)=∅ cannot be omitted even if γ(G/xy)=γ(G), since for odd n, b(Kn/xy)=⌈(n-1)/2⌉<⌈n/2⌉=b(Kn), by Theorem 1.On the other hand,b(Cn/xy)=b(Cn)=2 if n≡0(mod 3) and b(Kn/xy)=b(Kn) if n is even, which shows that the equality in b(G/xy)⩾b(G) may hold. Thus, the bound in Theorem 72 is tight. However, provided all the conditions, b(G/xy) can be arbitrarily larger than b(G). Given a graph H, let G be the graph formed from H∘K1 by adding a new vertex x and joining it to an vertex y of degree one in H∘K1. Then G/xy=H∘K1, γ(G)=γ(G/xy), and NG(x)∩NG(y)=∅. But b(G)=1 since γ(G-xy)=γ(G/xy)+1, and b(G/xy)=δ(H)+1 by Theorem 66. The gap between b(G) and b(G/xy) is δ(H).


## 6. Results on Planar Graphs

From Section2, we have seen that the bondage number for a tree has been completely solved. Moreover, a linear time algorithm to compute the bondage number of a tree is designed by Hartnell et al. [15]. It is quite natural to consider the bondage number for a planar graph. In this section, we state some results and problems on the bondage number for a planar graph.


### 6.1. Conjecture on Bondage Number

As mentioned in Section3, the bondage number can be much larger than the maximum degree. But for a planar graph G, the bondage number b(G) cannot exceed Δ(G) too much. It is clear that b(G)⩽Δ(G)+4 by Corollary 15 since δ(G)⩽5 for any planar graph G. In 1998, Dunbar  et al. [21] posed the following conjecture.Conjecture 73.
IfG is a planar graph, then b(G)⩽Δ(G)+1.Because of its attraction, it immediately became the focus of attention when this conjecture is proposed. In fact, the main aim concerning the research of the bondage number for a planar graph is focused on this conjecture.It has been mentioned in Theorems1 and 60 that b(C3k+1)=3=Δ+1, and b(C4k+2×K2)=4=Δ+1. It is known that b(K6-M)=5=Δ+1, where M is a perfect matching of the complete graph K6. These examples show that if Conjecture 73 is true, then the upper bound is sharp for 2⩽Δ⩽4.Here, we note that it is sufficient to prove this conjecture for connected planar graphs, since the bondage number of a disconnected graph is simply the minimum of the bondage numbers of its components.The first paper attacking this conjecture is due to Kang and Yuan [45], which confirmed the conjecture for every connected planar graph G with Δ⩾7. The proofs are mainly based on Theorems 16 and 18.Theorem 74 (Kang and Yuan [45], 2000).
IfG is a connected planar graph, then b(G)⩽min{8,Δ(G)+2}.Obviously, in view of Theorem74, Conjecture 73 is true for any connected planar graph with Δ⩾7.


### 6.2. Bounds Implied by Degree Conditions

As we have seen from Theorem74, to attack Conjecture 73, we only need to consider connected planar graphs with maximum Δ⩽6. Thus, studying the bondage number of planar graphs by degree conditions is of significance. The first result on bounds implied by degree conditions is obtained by Kang and Yuan [45].Theorem 75 (Kang and Yuan [45], 2000).
IfG is a connected planar graph without vertices of degree 5, then b(G)⩽7.Fischermann et al. [46] generalized Theorem 75 as follows.Theorem 76 (Fischermann et al. [46], 2003).
LetG be a connected planar graph and X the set of vertices of degree 5 which have distance at least 3 to vertices of degrees 1, 2, and 3. If all vertices in X not adjacent with vertices of degree 4 are independent and not adjacent to vertices of degree 6, then b(G)⩽7.Clearly, ifG has no vertices of degree 5, then X=∅. Thus, Theorem 76 yields Theorem 75.Useni to denote the number of vertices of degree i in G for each i=1,2,…,Δ(G). Using Theorem 18, Fischermann  et al. obtained the following two theorems.Theorem 77 (Fischermann et al. [46], 2003).
For any connected planar graphG,(1)
b(G)⩽7 if n5<2n2+3n3+2n4+12;(2)
b(G)⩽6 if G contains no vertices of degrees 4 and 5.Theorem 78 (Fischermann et al. [46], 2003).
For any connected planar graphG, b(G)⩽Δ(G)+1 if(1)
Δ(G)=6 and every edge e=xy with dG(x)=5 and dG(y)=6 is contained in at most one triangle;(2)
Δ(G)=5 and no triangle contains an edge e=xy with dG(x)=5 and 4⩽dG(y)⩽5.


### 6.3. Bounds Implied by Girth Conditions

The girthg(G) of a graph G is the length of the shortest cycle in G. If G has no cycles, we define g(G)=∞.Combining Theorem74 with Theorem 78, we find that if a planar graph contains no triangles and has maximum degree Δ⩾5, then Conjecture 73 holds. This fact motivated Fischermann  et al.’s [46] attempt to attack Conjecture 73 by girth restraints.Theorem 79 (Fischermann et al. [46], 2003).
For any connected planar graphG,
(20)b(G)⩽{6ifg(G)⩾4,5ifg(G)⩾5,4ifg(G)⩾6,3ifg(G)⩾8.The first result in Theorem79 shows that Conjecture 73 is valid for all connected planar graphs with g(G)⩾4 and Δ(G)⩾5. It is easy to verify that the second result in Theorem 79 implies that Conjecture 73 is valid for all not 3-regular graphs of girth g(G)⩾5, which is stated in the following corollary.Corollary 80.
For any connected planar graphG, if G is not 3-regular and g(G)⩾5, then b(G)⩽Δ(G)+1.The first result in Theorem79 also implies that if G is a connected planar graph with no cycles of length 3, then b(G)⩽6. Hou et al. [47] improved this result as follows.Theorem 81 (Hou et al. [47], 2011).
For any connected planar graphG, if G contains no cycles of length i(4⩽i⩽6), then b(G)⩽6.Sinceb(C3k+1)=3 for k⩾3 (see Theorem 1), the last bound in Theorem 79 is tight. Whether other bounds in Theorem 79 are tight remains open. In 2003, Fischermann  et al. [46] posed the following conjecture.Conjecture 82.
For any connected planar graphG, b(G)⩽7, and
(21)b(G)⩽{5,ifg(G)⩾4,4,ifg(G)⩾5.We conclude this subsection with a question on bondage numbers of planar graphs.Question 1 (Fischermann et al. [46], 2003).
Is there a planar graphG with 6⩽b(G)⩽8?In 2006, Carlson and Develin [42] showed that the corona G=H∘K1 for a planar graph H with δ(H)=5 has the bondage number b(G)=δ(H)+1=6 (see Theorem 66). Since the minimum degree of planar graphs is at most 5, then b(G) can attach 6. If we take H as the graph of the icosahedron, then G=H∘K1 is such an example. The question for the existence of planar graphs with bondage number 7 or 8 remains open.


### 6.4. Comments on the Conjectures

Conjecture73 is true for all connected planar graphs with minimum degree δ⩽2 by Theorem 16, or maximum degree Δ⩾7 by Theorem 74, or not γ-critical planar graphs by Theorem 13. Thus, to attack Conjecture 73, we only need to consider connected critical planar graphs with degree-restriction 3⩽δ⩽Δ⩽6.Recalling and anatomizing the proofs of all results mentioned in the preceding subsections on the bondage number for connected planar graphs, we find that the proofs of these results strongly depend upon Theorem16 or Theorem 18. In other words, a basic way used in the proofs is to find two vertices x and y with distance at most two in a considered planar graph G such that
(22)dG(x)+dG(y)ordG(x)+dG(y)-|NG(x)∩NG(y)|,
which bounds b(G), is as small as possible. Very recently, Huang and Xu [44] have considered the following parameter
(23)B(G)=minx,y∈V(G){{dxy:1⩽dG(x,y)⩽2}∪{dxy-nxy:d(x,y)=1}},
where dxy=dG(x)+dG(y)-1 and nxy=|NG(x)∩NG(y)|.It follows from Theorems16 and 18 that
(24)b(G)⩽B(G).
The proofs given in Theorems 74 and 79 indeed imply the following stronger results.Theorem 83.
IfG is a connected planar graph, then
(25)B(G)⩽{min{8,Δ(G)+2}6ifg(G)⩾4,5ifg(G)⩾5,4ifg(G)⩾6,3ifg(G)⩾8.Thus, using Theorem16 or Theorem 18, if we can prove Conjectures 73 and 82, then we can prove the following statement.Statement.
IfG is a connected planar graph, then
(26)B(G)⩽{Δ(G)+1,7,5,ifg(G)⩾4,4,ifg(G)⩾5.
It follows from (24) that Statement implies Conjectures 73 and 82. However, Huang and Xu [44] gave examples to show that none of conclusions in Statement is true. As a result, they stated the following conclusion.Theorem 84 (Huang and Xu [44], 2012).
It is not possible to prove Conjectures73 and 82, if they are right, using Theorems 16 and 18.Therefore, a new method is needed to prove or disprove these conjectures. At the present time, one cannot prove these conjectures, and may consider to disprove them. If one of these conjectures is invalid, then there exists aminimum counterexampleG with respect to υ(G)+ε(G). In order to obtain a minimum counterexample, one may consider two simple operations satisfying these requirements, the edge-deletion and the edge-contraction, which decrease υ(G)+ε(G) and preserve planarity. However, applying Theorems 71 and 72, Huang and Xu [44] presented the following results.Theorem 85 (Huang and Xu [44], 2012).
It is not possible to construct minimum counterexamples to Conjectures73 and 82 by the operation of an edge-deletion or an edge-contraction.


## 6.1. Conjecture on Bondage Number

As mentioned in Section3, the bondage number can be much larger than the maximum degree. But for a planar graph G, the bondage number b(G) cannot exceed Δ(G) too much. It is clear that b(G)⩽Δ(G)+4 by Corollary 15 since δ(G)⩽5 for any planar graph G. In 1998, Dunbar  et al. [21] posed the following conjecture.Conjecture 73.
IfG is a planar graph, then b(G)⩽Δ(G)+1.Because of its attraction, it immediately became the focus of attention when this conjecture is proposed. In fact, the main aim concerning the research of the bondage number for a planar graph is focused on this conjecture.It has been mentioned in Theorems1 and 60 that b(C3k+1)=3=Δ+1, and b(C4k+2×K2)=4=Δ+1. It is known that b(K6-M)=5=Δ+1, where M is a perfect matching of the complete graph K6. These examples show that if Conjecture 73 is true, then the upper bound is sharp for 2⩽Δ⩽4.Here, we note that it is sufficient to prove this conjecture for connected planar graphs, since the bondage number of a disconnected graph is simply the minimum of the bondage numbers of its components.The first paper attacking this conjecture is due to Kang and Yuan [45], which confirmed the conjecture for every connected planar graph G with Δ⩾7. The proofs are mainly based on Theorems 16 and 18.Theorem 74 (Kang and Yuan [45], 2000).
IfG is a connected planar graph, then b(G)⩽min{8,Δ(G)+2}.Obviously, in view of Theorem74, Conjecture 73 is true for any connected planar graph with Δ⩾7.


## 6.2. Bounds Implied by Degree Conditions

As we have seen from Theorem74, to attack Conjecture 73, we only need to consider connected planar graphs with maximum Δ⩽6. Thus, studying the bondage number of planar graphs by degree conditions is of significance. The first result on bounds implied by degree conditions is obtained by Kang and Yuan [45].Theorem 75 (Kang and Yuan [45], 2000).
IfG is a connected planar graph without vertices of degree 5, then b(G)⩽7.Fischermann et al. [46] generalized Theorem 75 as follows.Theorem 76 (Fischermann et al. [46], 2003).
LetG be a connected planar graph and X the set of vertices of degree 5 which have distance at least 3 to vertices of degrees 1, 2, and 3. If all vertices in X not adjacent with vertices of degree 4 are independent and not adjacent to vertices of degree 6, then b(G)⩽7.Clearly, ifG has no vertices of degree 5, then X=∅. Thus, Theorem 76 yields Theorem 75.Useni to denote the number of vertices of degree i in G for each i=1,2,…,Δ(G). Using Theorem 18, Fischermann  et al. obtained the following two theorems.Theorem 77 (Fischermann et al. [46], 2003).
For any connected planar graphG,(1)
b(G)⩽7 if n5<2n2+3n3+2n4+12;(2)
b(G)⩽6 if G contains no vertices of degrees 4 and 5.Theorem 78 (Fischermann et al. [46], 2003).
For any connected planar graphG, b(G)⩽Δ(G)+1 if(1)
Δ(G)=6 and every edge e=xy with dG(x)=5 and dG(y)=6 is contained in at most one triangle;(2)
Δ(G)=5 and no triangle contains an edge e=xy with dG(x)=5 and 4⩽dG(y)⩽5.


## 6.3. Bounds Implied by Girth Conditions

The girthg(G) of a graph G is the length of the shortest cycle in G. If G has no cycles, we define g(G)=∞.Combining Theorem74 with Theorem 78, we find that if a planar graph contains no triangles and has maximum degree Δ⩾5, then Conjecture 73 holds. This fact motivated Fischermann  et al.’s [46] attempt to attack Conjecture 73 by girth restraints.Theorem 79 (Fischermann et al. [46], 2003).
For any connected planar graphG,
(20)b(G)⩽{6ifg(G)⩾4,5ifg(G)⩾5,4ifg(G)⩾6,3ifg(G)⩾8.The first result in Theorem79 shows that Conjecture 73 is valid for all connected planar graphs with g(G)⩾4 and Δ(G)⩾5. It is easy to verify that the second result in Theorem 79 implies that Conjecture 73 is valid for all not 3-regular graphs of girth g(G)⩾5, which is stated in the following corollary.Corollary 80.
For any connected planar graphG, if G is not 3-regular and g(G)⩾5, then b(G)⩽Δ(G)+1.The first result in Theorem79 also implies that if G is a connected planar graph with no cycles of length 3, then b(G)⩽6. Hou et al. [47] improved this result as follows.Theorem 81 (Hou et al. [47], 2011).
For any connected planar graphG, if G contains no cycles of length i(4⩽i⩽6), then b(G)⩽6.Sinceb(C3k+1)=3 for k⩾3 (see Theorem 1), the last bound in Theorem 79 is tight. Whether other bounds in Theorem 79 are tight remains open. In 2003, Fischermann  et al. [46] posed the following conjecture.Conjecture 82.
For any connected planar graphG, b(G)⩽7, and
(21)b(G)⩽{5,ifg(G)⩾4,4,ifg(G)⩾5.We conclude this subsection with a question on bondage numbers of planar graphs.Question 1 (Fischermann et al. [46], 2003).
Is there a planar graphG with 6⩽b(G)⩽8?In 2006, Carlson and Develin [42] showed that the corona G=H∘K1 for a planar graph H with δ(H)=5 has the bondage number b(G)=δ(H)+1=6 (see Theorem 66). Since the minimum degree of planar graphs is at most 5, then b(G) can attach 6. If we take H as the graph of the icosahedron, then G=H∘K1 is such an example. The question for the existence of planar graphs with bondage number 7 or 8 remains open.


## 6.4. Comments on the Conjectures

Conjecture73 is true for all connected planar graphs with minimum degree δ⩽2 by Theorem 16, or maximum degree Δ⩾7 by Theorem 74, or not γ-critical planar graphs by Theorem 13. Thus, to attack Conjecture 73, we only need to consider connected critical planar graphs with degree-restriction 3⩽δ⩽Δ⩽6.Recalling and anatomizing the proofs of all results mentioned in the preceding subsections on the bondage number for connected planar graphs, we find that the proofs of these results strongly depend upon Theorem16 or Theorem 18. In other words, a basic way used in the proofs is to find two vertices x and y with distance at most two in a considered planar graph G such that
(22)dG(x)+dG(y)ordG(x)+dG(y)-|NG(x)∩NG(y)|,
which bounds b(G), is as small as possible. Very recently, Huang and Xu [44] have considered the following parameter
(23)B(G)=minx,y∈V(G){{dxy:1⩽dG(x,y)⩽2}∪{dxy-nxy:d(x,y)=1}},
where dxy=dG(x)+dG(y)-1 and nxy=|NG(x)∩NG(y)|.It follows from Theorems16 and 18 that
(24)b(G)⩽B(G).
The proofs given in Theorems 74 and 79 indeed imply the following stronger results.Theorem 83.
IfG is a connected planar graph, then
(25)B(G)⩽{min{8,Δ(G)+2}6ifg(G)⩾4,5ifg(G)⩾5,4ifg(G)⩾6,3ifg(G)⩾8.Thus, using Theorem16 or Theorem 18, if we can prove Conjectures 73 and 82, then we can prove the following statement.Statement.
IfG is a connected planar graph, then
(26)B(G)⩽{Δ(G)+1,7,5,ifg(G)⩾4,4,ifg(G)⩾5.
It follows from (24) that Statement implies Conjectures 73 and 82. However, Huang and Xu [44] gave examples to show that none of conclusions in Statement is true. As a result, they stated the following conclusion.Theorem 84 (Huang and Xu [44], 2012).
It is not possible to prove Conjectures73 and 82, if they are right, using Theorems 16 and 18.Therefore, a new method is needed to prove or disprove these conjectures. At the present time, one cannot prove these conjectures, and may consider to disprove them. If one of these conjectures is invalid, then there exists aminimum counterexampleG with respect to υ(G)+ε(G). In order to obtain a minimum counterexample, one may consider two simple operations satisfying these requirements, the edge-deletion and the edge-contraction, which decrease υ(G)+ε(G) and preserve planarity. However, applying Theorems 71 and 72, Huang and Xu [44] presented the following results.Theorem 85 (Huang and Xu [44], 2012).
It is not possible to construct minimum counterexamples to Conjectures73 and 82 by the operation of an edge-deletion or an edge-contraction.


## 7. Results on Crossing Number Restraints

It is quite natural to generalize the known results on the bondage number for planar graphs to for more general graphs in terms of graph-theoretical parameters. In this section, we consider graphs with crossing number restraints.Thecrossing numbercr(G) of G is the smallest number of pairwise intersections of its edges when G is drawn in the plane. If cr(G)=0, then G is a planar graph.


### 7.1. General Methods

Useni to denote the number of vertices of degree i in G for i=1,2,…,Δ(G). Huang and Xu obtained the following results.Theorem 86 (Huang and Xu [48], 2007).
For any connected graphG,
(27)b(G)⩽{6ifg(G)⩾4and2cr(G)<12a1;5ifg(G)⩾5and6cr(G)<16a2;4ifg(G)⩾6and4cr(G)<14a3;3ifg(G)⩾8and6cr(G)<16a4,
where a1=n1+2n2+2n3+∑i=8Δ‍(i-7)ni+8; a2=3n1+6n2+5n3+∑i=7Δ‍(3i-18)ni+20; a3=n1+2n2+∑i=6Δ‍(2i-10)ni+12; and a4=∑i=5Δ‍(3i-12)ni+16.Simplifying the conditions in Theorem86, we obtain the following corollaries immediately.Corollary 87 (Huang and Xu [48], 2007).
For any connected graphG,
(28)b(G)⩽{6,ifg(G)⩾4andcr(G)⩽3,5,ifg(G)⩾5andcr(G)⩽4,4,ifg(G)⩾6andcr(G)⩽2,3,ifg(G)⩾8andcr(G)⩽2.Corollary 88 (Huang and Xu [48], 2007).
For any connected graphG,(a)
b(G)⩽6 if G is not 4-regular, cr(G)=4 and g(G)⩾4;(b)
b(G)⩽Δ(G)+1 if G is not 3-regular, cr(G)⩽4 and g(G)⩾5;(c)
b(G)⩽4 if G is not 3-regular, cr(G)=3 and g(G)⩾6;(d)
b(G)⩽3 if cr(G)=3, g(G)⩾8 and Δ(G)⩾5.These corollaries generalize some known results for planar graphs. For example, Corollary87 contains Theorem 79; Corollary 88 (b) contains Corollary 80.Theorem 89 (Huang and Xu [48], 2007).
For any connected graphG, if cr(G)⩽n3(G)+n4(G)+3, then b(G)⩽8.Corollary 90 (Huang and Xu [48], 2007).
For any connected graphG, if cr(G)⩽3, then b(G)⩽8.Perhaps being unaware of this result, in 2010, Ma  et al. [49] proved that b(G)⩽12 for any graph G with cr(G)=1.Theorem 91 (Huang and Xu [48], 2007).
LetG be a connected graph, and I={x∈V(G):dG(x)=5,dG(x,y)⩾3 if dG(y)⩽3, and dG(y)≠4 for every y∈NG(x)}. If I is independent, no vertices adjacent to vertices of degree 6 and
(29)cr(G)<max{5n3+|I|-2n4+2811,7n3+4016},
then b(G)⩽7.Corollary 92 (Huang and Xu [48], 2007).
LetG be a connected graph with cr(G)⩽2. If I={x∈V(G):dG(x)=5,dG(y,x)⩾3 if dG(y)⩽3 and dG(y)≠4 for every y∈NG(x)} is independent, and no vertices adjacent to vertices of degree 6, then b(G)⩽7.Theorem 93 (Huang and Xu [48], 2007).
LetG be a connected graph. If G satisfies(a)
5cr(G)+n5<2n2+3n3+2n4+12 or(b)
7cr(G)+2n5<3n2+4n4+24,then b(G)⩽7.Proposition 94 (Huang and Xu [48], 2007).
LetG be a connected graph with no vertices of degrees four and five. If cr(G)⩽2, then b(G)⩽6.Theorem 95 (Huang and Xu [48], 2007).
IfG is a connected graph with cr(G)⩽4 and not 4-regular when cr(G)=4, then b(G)⩽Δ(G)+2.The above results generalize some known results for planar graphs. For example, Corollary90 and Theorem 95 contain Theorem 74; the first condition in Theorem 93 contains the second condition in Theorem 77.From Corollary88 and Theorem 95, we suggest the following questions.Question 2.
Is there a(a)
4-regular graph G with cr(G)=4 such that b(G)⩾7?(b)
3-regular graph G with cr⩽4 and g(G)⩾5 such that b(G)=5?(c)
3-regular graph G with cr=3 and g(G)=6 or 7 such that b(G)=5?


### 7.2. Carlson-Develin Methods

In this subsection, we introduce an elegant method presented by Carlson and Develin [42] to obtain some upper bounds for the bondage number of a graph.Suppose thatG is a connected graph. We say that G has genusρ if G can be embedded in a surface S with ρ handles such that edges are pairwise disjoint except possibly for end-vertices. Let G~ be an embedding of G in surface S, and let ϕ(G) denote the number of regions in G~. The boundary of every region contains at least three edges and every edge is on the boundary of at most two regions (the two regions are identical when e is a cut-edge). For any edge e of G, let rG1(e) and rG2(e) be the numbers of edges comprising the regions in G~ which the edge e borders. It is clear that every e=xy∈E(G),
(30)rG2(e)⩾rG1(e)⩾4if|NG(x)∩NG(y)|=0,rG2(e)⩾4,rG1(e)⩾3if|NG(x)∩NG(y)|=1,rG2(e)⩾rG1(e)⩾3if|NG(x)∩NG(y)|⩾2.
Following Carlson and Develin [42], for any edge e=xy of G, we define
(31)DG(e)=1dG(x)+1dG(y)+1rG1(e)+1rG2(e)-1.
By the well-known Euler's formula
(32)υ(G)-ε(G)+ϕ(G)=2-2ρ(G),
it is easy to see that
(33)∑e∈E(G)‍DG(e)=υ(G)-ε(G)+ϕ(G)=2-2ρ(G).
If G is a planar graph, that is, ρ(G)=0, then
(34)∑e∈E(G)‍DG(e)=υ(G)-ε(G)+ϕ(G)=2.Combining these formulas with Theorem18, Carlson and Develin [42] gave a simple and intuitive proof of Theorem 74 and obtained the following result.Theorem 96 (Carlson and Develin [42], 2006).
LetG be a connected graph which can be embedded on a torus. Then b(G)⩽Δ(G)+3.Recently, Hou and Liu [50] improved Theorem 96 as follows.Theorem 97 (Hou and Liu [50], 2012).
LetG be a connected graph which can be embedded on a torus. Then b(G)⩽9. Moreover, if Δ(G)≠6, then b(G)⩽8.By the way, Cao et al. [51] generalized the result in Theorem 79 to a connected graph G that can be embedded on a torus; that is,
(35)b(G)≤{6,ifg(G)⩾4andGisnot4-regular,5,ifg(G)⩾5,4,ifg(G)⩾6andGisnot3-regular,3,ifg(G)⩾8.Several authors used this method to obtain some results on the bondage number. For example, Fischermann  et al. [46] used this method to prove the second conclusion in Theorem 78. Recently, Cao et al. [52] have used this method to deal with more general graphs with small crossing numbers. First, they found the following property.Lemma 98.
δ
(
G
)
⩽
5 for any graph G with cr(G)⩽5.This result implies thatb(G)⩽Δ(G)+4 by Corollary 15 for any graph G with cr(G)⩽5. Cao  et al. established the following relation in terms of maximum planar subgraphs.Lemma 99 (Cao et al. [52]).
LetG be a connected graph with crossing number cr(G). For any maximum planar subgraph H of G,
(36)∑e∈E(H)‍DG(e)⩾2-2cr(G)δ(G).Using Carlson-Develin method and combining Lemma98 with Lemma 99, Cao  et al. proved the following results.Theorem 100 (Cao et al. [52]).
For any connected graphG, b(G)⩽Δ(G)+2 if G satisfies one of the following conditions:(a)
cr(G)⩽3;(b)
cr(G)=4 and G is not 4-regular;(c)
cr(G)=5 and G contains no vertices of degree 4.Theorem 101 (Cao et al. [52]).
LetG be a connected graph with Δ(G)=5 and cr(G)⩽4. If no triangles contain two vertices of degree 5, then b(G)⩽6=Δ(G)+1.Theorem 102 (Cao et al. [52]).
LetG be a connected graph with Δ(G)⩾6 and cr(G)⩽3. If Δ(G)⩾7 or if Δ(G)=6, δ(G)≠3 and every edge e=xy with dG(x)=5 and dG(y)=6 is contained in at most one triangle, then b(G)⩽min{8,Δ(G)+1}.Using Carlson-Develin method, it can be proved thatb(G)⩽Δ(G)+2 if cr(G)⩽3 (see the first conclusion in Theorem 100), and not yet proved that b(G)⩽8 if cr(G)⩽3, although it has been proved by using other method (see Corollary 90).By using Carlson-Develin method, Samodivkin [25] obtained some results on the bondage number for graphs with some given properties.Kim [53] showed that b(G)⩽Δ(G)+2 for a connected graph G with genus 1, Δ(G)⩽5 and having a toroidal embedding of which at least one region is not 4-sided. Recently, Gagarin and Zverovich [54] further have extended Carlson-Develin ideas to establish a nice upper bound for arbitrary graphs that can be embedded on orientable or nonorientable topological surface.Theorem 103 (Gagarin and Zverovich [54], 2012).
LetG be a graph embeddable on an orientable surface of genus h and a nonorientable surface of genus k. Then b(G)⩽min{Δ(G)+h+2,Δ(G)+k+1}.This result generalizes the corresponding upper bounds in Theorems74 and 96 for any orientable or nonorientable topological surface. By investigating the proof of Theorem 103, Huang [55] found that the issue of the orientability can be avoided by using the Euler characteristic χ(=υ(G)-ε(G)+ϕ(G)) instead of the genera h and k; the relations are χ=2-2h and χ=2-k. To obtain the best result from Theorem 103, one wants h and k as small as possible; this is equivalent to having χ as large as possible.According to Theorem103, if G is planar (h=0,χ=2) or can be embedded on the real projective plane (k=1,χ=1), then b(G)⩽Δ(G)+2. In all other cases, Huang [55] had the following improvement for Theorem 103; the proof is based on the technique developed by Carlson-Develin and Gagarin-Zverovich and includes some elementary calculus as a new ingredient, mainly the intermediate-value theorem and the mean-value theorem.Theorem 104 (Huang [55], 2012).
LetG be a graph embeddable on a surface whose Euler characteristic χ is as large as possible. If χ⩽0, then b(G)⩽Δ(G)+⌊r⌋, where r is the largest real root of the following cubic equation in z:
(37)z3+2z2+(6χ-7)z+18χ-24=0.
In addition, if χ decreases, then r increases.The following result is asymptotically equivalent to Theorem104.Theorem 105 (Huang [55], 2012).
LetG be a graph embeddable on a surface whose Euler characteristic χ is as large as possible. If χ⩽0, then b(G)<Δ(G)+12-6χ+1/2, or equivalently, b(G)⩽Δ(G)+⌈12-6χ-1/2⌉.Also, Gagarin and Zverovich [54] indicated that the upper bound in Theorem 103 can be improved for larger values of the genera h and k by adjusting the proofs and stated the following general conjecture.Conjecture 106 (Gagarin and Zverovich [54], 2012).
For a connected graph G of orientable genush and nonorientable genus k,
(38)b(G)⩽min{ch,ck′,Δ(G)+o(h),Δ(G)+o(k)},
where ch and ck′ are constants depending, respectively, on the orientable and nonorientable genera of G.In the recent paper, Gagarin and Zverovich [56] provided constant upper bounds for the bondage number of graphs on topological surfaces, which can be used as the first estimation for the constants ch and ck′ of Conjecture 106.Theorem 107 (Gagarin and Zverovich [56], 2013).
LetG be a connected graph of order n. If G can be embedded on the surface of its orientable or nonorientable genus of the Euler characteristic χ, then(a)
χ⩾1 implies b(G)⩽10;(b)
χ⩽0 and n>-12χ imply b(G)⩽11;(c)
χ⩽-1 and n⩽-12χ imply b(G)⩽11+3χ(17-8χ-3)/(χ-1)=11+O(-χ).Theorem79 shows that a connected planar triangle-free graph G has b(G)⩽6. The following result generalizes to it all the other topological surfaces.Theorem 108 (Gagarin and Zverovich [56], 2013).
LetG be a connected triangle-free graph of order n. If G can be embedded on the surface of its orientable or nonorientable genus of the Euler characteristic χ, then(a)
χ⩾1 implies b(G)⩽6;(b)
χ⩽0 and n>-8χ imply b(G)⩽7;(c)
χ⩽-1 and n⩽-8χ imply b(G)⩽7-4χ/(1+2-χ).In [56], the authors also explicitly improved upper bounds in Theorem 103 and gave tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus. The interested reader is referred to the original paper for details. The following result is interesting although its proof is easy.Theorem 109 (Samodivkin [57]).
LetG be a graph with order n and girth g. If G is embeddable on a surface whose Euler characteristic χ is as large as possible, then
(39)b(G)⩽3+8g-2-4χgn(g-2).IfG is a planar graph with girth g⩾4+i for any i∈{0,1,2}, then Theorem 109 leads to b(G)⩽6-i, which is the result in Theorem 79 obtained by Fischermann  et al. [46]. Also, in many cases the bound stated in Theorem 109 is better than those given by Theorems 103 and 105.


## 7.1. General Methods

Useni to denote the number of vertices of degree i in G for i=1,2,…,Δ(G). Huang and Xu obtained the following results.Theorem 86 (Huang and Xu [48], 2007).
For any connected graphG,
(27)b(G)⩽{6ifg(G)⩾4and2cr(G)<12a1;5ifg(G)⩾5and6cr(G)<16a2;4ifg(G)⩾6and4cr(G)<14a3;3ifg(G)⩾8and6cr(G)<16a4,
where a1=n1+2n2+2n3+∑i=8Δ‍(i-7)ni+8; a2=3n1+6n2+5n3+∑i=7Δ‍(3i-18)ni+20; a3=n1+2n2+∑i=6Δ‍(2i-10)ni+12; and a4=∑i=5Δ‍(3i-12)ni+16.Simplifying the conditions in Theorem86, we obtain the following corollaries immediately.Corollary 87 (Huang and Xu [48], 2007).
For any connected graphG,
(28)b(G)⩽{6,ifg(G)⩾4andcr(G)⩽3,5,ifg(G)⩾5andcr(G)⩽4,4,ifg(G)⩾6andcr(G)⩽2,3,ifg(G)⩾8andcr(G)⩽2.Corollary 88 (Huang and Xu [48], 2007).
For any connected graphG,(a)
b(G)⩽6 if G is not 4-regular, cr(G)=4 and g(G)⩾4;(b)
b(G)⩽Δ(G)+1 if G is not 3-regular, cr(G)⩽4 and g(G)⩾5;(c)
b(G)⩽4 if G is not 3-regular, cr(G)=3 and g(G)⩾6;(d)
b(G)⩽3 if cr(G)=3, g(G)⩾8 and Δ(G)⩾5.These corollaries generalize some known results for planar graphs. For example, Corollary87 contains Theorem 79; Corollary 88 (b) contains Corollary 80.Theorem 89 (Huang and Xu [48], 2007).
For any connected graphG, if cr(G)⩽n3(G)+n4(G)+3, then b(G)⩽8.Corollary 90 (Huang and Xu [48], 2007).
For any connected graphG, if cr(G)⩽3, then b(G)⩽8.Perhaps being unaware of this result, in 2010, Ma  et al. [49] proved that b(G)⩽12 for any graph G with cr(G)=1.Theorem 91 (Huang and Xu [48], 2007).
LetG be a connected graph, and I={x∈V(G):dG(x)=5,dG(x,y)⩾3 if dG(y)⩽3, and dG(y)≠4 for every y∈NG(x)}. If I is independent, no vertices adjacent to vertices of degree 6 and
(29)cr(G)<max{5n3+|I|-2n4+2811,7n3+4016},
then b(G)⩽7.Corollary 92 (Huang and Xu [48], 2007).
LetG be a connected graph with cr(G)⩽2. If I={x∈V(G):dG(x)=5,dG(y,x)⩾3 if dG(y)⩽3 and dG(y)≠4 for every y∈NG(x)} is independent, and no vertices adjacent to vertices of degree 6, then b(G)⩽7.Theorem 93 (Huang and Xu [48], 2007).
LetG be a connected graph. If G satisfies(a)
5cr(G)+n5<2n2+3n3+2n4+12 or(b)
7cr(G)+2n5<3n2+4n4+24,then b(G)⩽7.Proposition 94 (Huang and Xu [48], 2007).
LetG be a connected graph with no vertices of degrees four and five. If cr(G)⩽2, then b(G)⩽6.Theorem 95 (Huang and Xu [48], 2007).
IfG is a connected graph with cr(G)⩽4 and not 4-regular when cr(G)=4, then b(G)⩽Δ(G)+2.The above results generalize some known results for planar graphs. For example, Corollary90 and Theorem 95 contain Theorem 74; the first condition in Theorem 93 contains the second condition in Theorem 77.From Corollary88 and Theorem 95, we suggest the following questions.Question 2.
Is there a(a)
4-regular graph G with cr(G)=4 such that b(G)⩾7?(b)
3-regular graph G with cr⩽4 and g(G)⩾5 such that b(G)=5?(c)
3-regular graph G with cr=3 and g(G)=6 or 7 such that b(G)=5?


## 7.2. Carlson-Develin Methods

In this subsection, we introduce an elegant method presented by Carlson and Develin [42] to obtain some upper bounds for the bondage number of a graph.Suppose thatG is a connected graph. We say that G has genusρ if G can be embedded in a surface S with ρ handles such that edges are pairwise disjoint except possibly for end-vertices. Let G~ be an embedding of G in surface S, and let ϕ(G) denote the number of regions in G~. The boundary of every region contains at least three edges and every edge is on the boundary of at most two regions (the two regions are identical when e is a cut-edge). For any edge e of G, let rG1(e) and rG2(e) be the numbers of edges comprising the regions in G~ which the edge e borders. It is clear that every e=xy∈E(G),
(30)rG2(e)⩾rG1(e)⩾4if|NG(x)∩NG(y)|=0,rG2(e)⩾4,rG1(e)⩾3if|NG(x)∩NG(y)|=1,rG2(e)⩾rG1(e)⩾3if|NG(x)∩NG(y)|⩾2.
Following Carlson and Develin [42], for any edge e=xy of G, we define
(31)DG(e)=1dG(x)+1dG(y)+1rG1(e)+1rG2(e)-1.
By the well-known Euler's formula
(32)υ(G)-ε(G)+ϕ(G)=2-2ρ(G),
it is easy to see that
(33)∑e∈E(G)‍DG(e)=υ(G)-ε(G)+ϕ(G)=2-2ρ(G).
If G is a planar graph, that is, ρ(G)=0, then
(34)∑e∈E(G)‍DG(e)=υ(G)-ε(G)+ϕ(G)=2.Combining these formulas with Theorem18, Carlson and Develin [42] gave a simple and intuitive proof of Theorem 74 and obtained the following result.Theorem 96 (Carlson and Develin [42], 2006).
LetG be a connected graph which can be embedded on a torus. Then b(G)⩽Δ(G)+3.Recently, Hou and Liu [50] improved Theorem 96 as follows.Theorem 97 (Hou and Liu [50], 2012).
LetG be a connected graph which can be embedded on a torus. Then b(G)⩽9. Moreover, if Δ(G)≠6, then b(G)⩽8.By the way, Cao et al. [51] generalized the result in Theorem 79 to a connected graph G that can be embedded on a torus; that is,
(35)b(G)≤{6,ifg(G)⩾4andGisnot4-regular,5,ifg(G)⩾5,4,ifg(G)⩾6andGisnot3-regular,3,ifg(G)⩾8.Several authors used this method to obtain some results on the bondage number. For example, Fischermann  et al. [46] used this method to prove the second conclusion in Theorem 78. Recently, Cao et al. [52] have used this method to deal with more general graphs with small crossing numbers. First, they found the following property.Lemma 98.
δ
(
G
)
⩽
5 for any graph G with cr(G)⩽5.This result implies thatb(G)⩽Δ(G)+4 by Corollary 15 for any graph G with cr(G)⩽5. Cao  et al. established the following relation in terms of maximum planar subgraphs.Lemma 99 (Cao et al. [52]).
LetG be a connected graph with crossing number cr(G). For any maximum planar subgraph H of G,
(36)∑e∈E(H)‍DG(e)⩾2-2cr(G)δ(G).Using Carlson-Develin method and combining Lemma98 with Lemma 99, Cao  et al. proved the following results.Theorem 100 (Cao et al. [52]).
For any connected graphG, b(G)⩽Δ(G)+2 if G satisfies one of the following conditions:(a)
cr(G)⩽3;(b)
cr(G)=4 and G is not 4-regular;(c)
cr(G)=5 and G contains no vertices of degree 4.Theorem 101 (Cao et al. [52]).
LetG be a connected graph with Δ(G)=5 and cr(G)⩽4. If no triangles contain two vertices of degree 5, then b(G)⩽6=Δ(G)+1.Theorem 102 (Cao et al. [52]).
LetG be a connected graph with Δ(G)⩾6 and cr(G)⩽3. If Δ(G)⩾7 or if Δ(G)=6, δ(G)≠3 and every edge e=xy with dG(x)=5 and dG(y)=6 is contained in at most one triangle, then b(G)⩽min{8,Δ(G)+1}.Using Carlson-Develin method, it can be proved thatb(G)⩽Δ(G)+2 if cr(G)⩽3 (see the first conclusion in Theorem 100), and not yet proved that b(G)⩽8 if cr(G)⩽3, although it has been proved by using other method (see Corollary 90).By using Carlson-Develin method, Samodivkin [25] obtained some results on the bondage number for graphs with some given properties.Kim [53] showed that b(G)⩽Δ(G)+2 for a connected graph G with genus 1, Δ(G)⩽5 and having a toroidal embedding of which at least one region is not 4-sided. Recently, Gagarin and Zverovich [54] further have extended Carlson-Develin ideas to establish a nice upper bound for arbitrary graphs that can be embedded on orientable or nonorientable topological surface.Theorem 103 (Gagarin and Zverovich [54], 2012).
LetG be a graph embeddable on an orientable surface of genus h and a nonorientable surface of genus k. Then b(G)⩽min{Δ(G)+h+2,Δ(G)+k+1}.This result generalizes the corresponding upper bounds in Theorems74 and 96 for any orientable or nonorientable topological surface. By investigating the proof of Theorem 103, Huang [55] found that the issue of the orientability can be avoided by using the Euler characteristic χ(=υ(G)-ε(G)+ϕ(G)) instead of the genera h and k; the relations are χ=2-2h and χ=2-k. To obtain the best result from Theorem 103, one wants h and k as small as possible; this is equivalent to having χ as large as possible.According to Theorem103, if G is planar (h=0,χ=2) or can be embedded on the real projective plane (k=1,χ=1), then b(G)⩽Δ(G)+2. In all other cases, Huang [55] had the following improvement for Theorem 103; the proof is based on the technique developed by Carlson-Develin and Gagarin-Zverovich and includes some elementary calculus as a new ingredient, mainly the intermediate-value theorem and the mean-value theorem.Theorem 104 (Huang [55], 2012).
LetG be a graph embeddable on a surface whose Euler characteristic χ is as large as possible. If χ⩽0, then b(G)⩽Δ(G)+⌊r⌋, where r is the largest real root of the following cubic equation in z:
(37)z3+2z2+(6χ-7)z+18χ-24=0.
In addition, if χ decreases, then r increases.The following result is asymptotically equivalent to Theorem104.Theorem 105 (Huang [55], 2012).
LetG be a graph embeddable on a surface whose Euler characteristic χ is as large as possible. If χ⩽0, then b(G)<Δ(G)+12-6χ+1/2, or equivalently, b(G)⩽Δ(G)+⌈12-6χ-1/2⌉.Also, Gagarin and Zverovich [54] indicated that the upper bound in Theorem 103 can be improved for larger values of the genera h and k by adjusting the proofs and stated the following general conjecture.Conjecture 106 (Gagarin and Zverovich [54], 2012).
For a connected graph G of orientable genush and nonorientable genus k,
(38)b(G)⩽min{ch,ck′,Δ(G)+o(h),Δ(G)+o(k)},
where ch and ck′ are constants depending, respectively, on the orientable and nonorientable genera of G.In the recent paper, Gagarin and Zverovich [56] provided constant upper bounds for the bondage number of graphs on topological surfaces, which can be used as the first estimation for the constants ch and ck′ of Conjecture 106.Theorem 107 (Gagarin and Zverovich [56], 2013).
LetG be a connected graph of order n. If G can be embedded on the surface of its orientable or nonorientable genus of the Euler characteristic χ, then(a)
χ⩾1 implies b(G)⩽10;(b)
χ⩽0 and n>-12χ imply b(G)⩽11;(c)
χ⩽-1 and n⩽-12χ imply b(G)⩽11+3χ(17-8χ-3)/(χ-1)=11+O(-χ).Theorem79 shows that a connected planar triangle-free graph G has b(G)⩽6. The following result generalizes to it all the other topological surfaces.Theorem 108 (Gagarin and Zverovich [56], 2013).
LetG be a connected triangle-free graph of order n. If G can be embedded on the surface of its orientable or nonorientable genus of the Euler characteristic χ, then(a)
χ⩾1 implies b(G)⩽6;(b)
χ⩽0 and n>-8χ imply b(G)⩽7;(c)
χ⩽-1 and n⩽-8χ imply b(G)⩽7-4χ/(1+2-χ).In [56], the authors also explicitly improved upper bounds in Theorem 103 and gave tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus. The interested reader is referred to the original paper for details. The following result is interesting although its proof is easy.Theorem 109 (Samodivkin [57]).
LetG be a graph with order n and girth g. If G is embeddable on a surface whose Euler characteristic χ is as large as possible, then
(39)b(G)⩽3+8g-2-4χgn(g-2).IfG is a planar graph with girth g⩾4+i for any i∈{0,1,2}, then Theorem 109 leads to b(G)⩽6-i, which is the result in Theorem 79 obtained by Fischermann  et al. [46]. Also, in many cases the bound stated in Theorem 109 is better than those given by Theorems 103 and 105.


## 8. Conditional Bondage Numbers

Since the concept of the bondage number is based upon the domination, all sorts of dominations, which are variations of the normal domination by adding restricted conditions to the normal dominating set, can develop a new “bondage number” as long as a variation of domination number is given. In this section, we survey results on the bondage number under some restricted conditions.


### 8.1. Total Bondage Numbers

A dominating setS of a graph G without isolated vertices is called total if the subgraph induced by S contains no isolated vertices. The minimum cardinality of a total dominating set is called the total domination number of G and denoted by γT(G). It is clear that γ(G)⩽γT(G)⩽2γ(G) for any graph G without isolated vertices.The total domination in graphs was introduced by Cockayne  et al. [58] in 1980. Pfaff  et al. [59, 60] in 1983 showed that the problem determining total domination number for general graphs is NP-complete, even for bipartite graphs and chordal graphs. Even now, total domination in graphs has been extensively studied in the literature. In 2009, Henning [61] gave a survey of selected recent results on total domination in graphs.Thetotal bondage number of G, denoted by bT(G), is the smallest cardinality of a subset B⊆E(G) with the property that G-B contains no isolated vertices and γT(G-B)>γT(G).From definition,bT(G) may not exist for some graphs, for example, G=K1,n. We put bT(G)=∞ if bT(G) does not exist. It is easy to see that bT(G) is finite for any connected graph G other than K1,K2,K3, and K1,n. In fact, for such a graph G, since there is a path of length 3 in G, we can find B1⊆E(G) such that G-B1 is a spanning tree T of G, containing a path of length 3. So γT(T)=γT(G-B1)⩾γT(G). For the tree T, we find B2⊆E(T) such that γT(T-B2)>γT(T)⩾γT(G). Thus, we have γT(G-B2-B1)>γT(G), and so bT(G)⩽|B1|+|B2|. In the following discussion, we always assume that bT(G) exists when a graph G is mentioned.In 1991, Kulli and Patwari [62] first studied the total bondage number of a graph and calculated the exact values of bT(G) for some standard graphs.Theorem 110 (Kulli and Patwari [62], 1991).
Forn⩾4,
(40)bT(Cn)={3ifn≡2(mod4),2otherwise,bT(Pn)={2ifn≡2(mod4),1otherwise,bT(Km,n)=mwith2⩽m⩽n,bT(Kn)={4forn=4,2n-5forn⩾5.Recently, Hu et al. [63] have obtained some results on the total bondage number of the Cartesian product Pm×Pn of two paths Pm and Pn.Theorem 111 (Hu et al. [63], 2012).
For the Cartesian productPm×Pn of two paths Pm and Pn,
(41)bT(P2×Pn)={1ifn≡0(mod3),2ifn≡2(mod3),3ifn≡1(mod3),bT(P3×Pn)=1,bT(P4×Pn){=1ifn≡1(mod5),=2ifn≡4(mod5),⩽3ifn≡2(mod5),⩽4ifn≡0,3(mod5).Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied recently. By constructing a family of minimum total dominating sets, Cao  et al. [64] determined the total bondage number of the generalized Petersen graphs.From Theorem6, we know that b(T)⩽2 for a nontrivial tree T. But given any positive integer k, Sridharan  et al. [65] constructed a tree T for which bT(T)=k. Let Hk be the tree obtained from a star K1,k+1 by subdividing k edges twice. The tree H7 is shown in Figure 6. It can be easily verified that bT(Hk)=k. This fact can be stated as the following theorem.Figure 6
H
7.Theorem 112 (Sridharan et al. [65], 2007).
For any positive integerk, there exists a tree T with bT(T)=k.Combining Theorem1 with Theorem 112, we have what follows.Corollary 113 (Sridharan et al. [65], 2007).
The bondage number and the total bondage number are unrelated, even for trees.However, Sridharan  et al. [65] gave an upper bound on the total bondage number of a tree in terms of its maximum degree. For any tree T of order n, if T≠K1,n-1, then bT(T)=min{Δ(T),(1/3)(n-1)}. Rad and Raczek [66] improved this upper bound and gave a constructive characterization of a certain class of trees attaching the upper bound.Theorem 114 (Rad and Raczek [66], 2011).
b
T
(
T
)
⩽
Δ
(
T
)
-
1  for any tree T with maximum degree at least three.In general, the decision problem forbT(G) is NP-complete for any graph G. We state the decision problem for the total bondage as follows.Problem 3.
Consider the decision problem:Total Bondage ProblemInstance: a graphG and a positive integer b.Question: isbT(G)⩽b?Theorem 115 (Hu and Xu [16], 2012).
The total bondage problem is NP-complete.Consequently, in view of its computational hardness, it is significative to establish some sharp bounds on the total bondage number of a graph in terms of other graphic parameters. In 1991, Kulli and Patwari [62] showed that bT(G)⩽2n-5 for any graph G with order n⩾5. Sridharan  et al. [65] improved this result as follows.Theorem 116 (Sridharan et al. [65], 2007).
For any graphG with order n, if n⩾5, then
(42)bT(G)⩽{13(n-1)ifGcontainsnocycles,n-1ifg(G)⩾5,n-2ifg(G)=4.Rad and Raczek [66] also established some upper bounds on bT(G) for a general graph G. In particular, they gave an upper bound on bT(G) in terms of the girth of G.Theorem 117 (Rad and Raczek [66], 2011).
b
T
(
G
)

⩽

4
Δ
(
G
)
-
5 for any graph G with g(G)⩾4.


### 8.2. Paired Bondage Numbers

A dominating setS of G is called to be paired if the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γP(G), is the minimum cardinality of a paired dominating set of G. Clearly, γT(G)⩽γP(G) for every connected graph G with order at least two, where γT(G) is the total domination number of G, and γP(G)⩽2γ(G) for any graph G without isolated vertices. Paired domination was introduced by Haynes and Slater [67, 68] and further studied in [69–72].Thepaired bondage number of G with δ(G)⩾1, denoted by bP(G), is the minimum cardinality among all sets of edges B⊆E such that δ(G-B)⩾1 and γP(G-B)>γP(G).The concept of the paired bondage number was first proposed by Raczek [73] in 2008. The following observations follow immediately from the definition of the paired bondage number.Observation 2.
LetG be a graph with δ(G)⩾1.(a)
IfH is a subgraph of G such that δ(H)⩾1, then bP(H)⩽bP(G).(b)
IfH is a subgraph of G such that bP(H)=1 and k is the number of edges removed to form H, then 1⩽bP(G)⩽k+1.(c)
Ifxy∈E(G) such that dG(x),dG(y)>1, and xy belongs to each perfect matching of each minimum paired dominating set of G, then bP(G)=1.Based on these observations,bP(Pn)⩽2. In fact, the paired bondage number of a path has been determined.Theorem 118 (Raczek [73], 2008).
For any positive integerk, if n⩾2, then
(43)bP(Pn)={0ifn=2,3,or5,1ifn=4k,4k+3,or4k+6,2otherwise.For a cycleCn of order n⩾3, since γP(Cn)=γP(Pn), from Theorem 118 the following result holds immediately.Corollary 119 (Raczek [73], 2008).
For any positive integerk, if n⩾3, then
(44)bP(Cn)={0ifn=3or5,2ifn=4k,4k+3,or4k+6,3otherwise.A wheelWn, where n⩾4, is a graph with n vertices, formed by connecting a single vertex to all vertices of a cycle Cn-1. Of course γP(Wn)=2.Theorem 120 (Raczek [73], 2008).
For positive integersn and m,
(45)bP(Km,n)=mfor1<m⩽n,bP(Wn)={4ifn=4,3ifn=5,2otherwise.Theorem16 shows that if T is a nontrivial tree, then b(T)⩽2. However, no similar result exists for paired bondage. For any nonnegative integer k, let Tk be a tree obtained by subdividing all but one edge of a star K1,k+1 (as shown in Figure 7). It is easy to see that bP(Tk)=k. We state this fact as the following theorem, which is similar to Theorem 112.Figure 7
A treeT with bP(T)=k.Theorem 121 (Raczek [73], 2008).
For any nonnegative integerk, there exists a tree T with bP(T)=k.Consider the tree defined in Figure5 for k=3. Then b(T3)⩽2 and bP(T3)=3. On the other hand, b(P4)=2 and bP(P4)=1. Thus, we have what follows, which is similar to Corollary 113.Corollary 122.
The bondage number and the paired bondage number are unrelated, even for trees.A constructive characterization of trees withb(T)=2 is given by Hartnell and Rall in [12]. Raczek [73] provided a constructive characterization of trees with bP(T)=0. In order to state the characterization, we define a labeling and three simple operations on a tree T. Let y∈V(T) and let ℓ(y) be the label assigned to y.Operation𝒯1. If ℓ(y)=B, add a vertex x and the edge yx, and let ℓ(x)=A.Operation𝒯2. If ℓ(y)=C, add a path (x1,x2) and the edge yx1, and let ℓ(x1)=B, ℓ(x2)=A.Operation𝒯3. If ℓ(y)=B, add a path (x1,x2,x3) and the edge yx1, and let ℓ(x1)=C,ℓ(x2)=B, and ℓ(x3)=A.LetP2=(u,v) with ℓ(u)=A and ℓ(v)=B. Let 𝒯 be the class of all trees obtained from the labeled P2 by a finite sequence of operations 𝒯1, 𝒯2, 𝒯3.A treeT in Figure 8 belongs to the family 𝒯.Figure 8
A treeT belong to the family 𝒯.Raczek [73] obtained the following characterization of all trees T with bP(T)=0.Theorem 123 (Raczek [73], 2008).
For a treeT, bP(T)=0 if and only if T is in 𝒯.We state the decision problem for the paired bondage as follows.Problem 4.
Consider the decision problem:Paired Bondage ProblemInstance: a graphG and a positive integer b.Question: isbP(G)⩽b?Conjecture 124.
The paired bondage problem is NP-complete.


### 8.3. Restrained Bondage Numbers

A dominating setS of G is called to berestrained if the subgraph induced by S- contains no isolated vertices, where S-=V(G)∖S. The restrained domination number of G, denoted by γR(G), is the smallest cardinality of a restrained dominating set of G. It is clear that γR(G) exists and γ(G)⩽γR(G) for any nonempty graph G.The concept of restrained domination was introduced by Telle and Proskurowski [74] in 1997, albeit indirectly, as a vertex partitioning problem. Concerning the study of the restrained domination numbers, the reader is referred to [74–79].In 2008, Hattingh and Plummer [80] defined the restrained bondage numberbR(G) of a nonempty graph G to be the minimum cardinality among all subsets B⊆E(G) for which γR(G-B)>γR(G).For some simple graphs, their restrained domination numbers can be easily determined, and so restrained bondage numbers have been also determined. For example, it is clear thatγR(Kn)=1. Domke  et al. [77] showed that γR(Cn)=n-2⌊n/3⌋ for n⩾3, and γR(Pn)=n-2⌊(n-1)/3⌋ for n⩾1. Using these results, Hattingh and Plummer [80] obtained the restricted bondage numbers for Kn,Cn,Pn, and G=Kn1,n2,…,nt as follows.Theorem 125 (Hattingh and Plummer [80], 2008).
Forn⩾3,
(46)bR(Kn)={1ifn=3,⌈n2⌉otherwise,bR(Cn)={1ifn≡0(mod3),2otherwise,bR(Pn)=1,n⩾4,bR(G)={⌈m2⌉ifnm=1andnm+1⩾2(1⩽m<t),2t-2ifn1=n2=⋯=nt=2(t⩾2),2ifn1=2andn2⩾3(t=2),∑i=1t-1‍ni-1otherwise.Theorem 126 (Hattingh and Plummer [80], 2008).
For a treeT of order n(⩾4), T≇K1,n-1 if and only if bR(T)=1.Theorem126 shows that the restrained bondage number of a tree can be computed in constant time. However, the decision problem for bR(G) is NP-complete even for bipartite graphs.Problem 5.
Consider the decision problem:Restrained Bondage ProblemInstance: a graphG and a positive integer b.Question: isbR(G)⩽b?Theorem 127 (Hattingh and Plummer [80], 2008).
The restrained bondage problem is NP-complete, even for bipartite graphs.Consequently, in view of its computational hardness, it is significative to establish some sharp bounds on the restrained bondage number of a graph in terms of other graphic parameters.Theorem 128 (Hattingh and Plummer [80], 2008).
For any graphG with δ(G)⩾2,
(47)bR(G)⩽minxy∈E(G){dG(x)+dG(y)-2}.Corollary 129.
b
R
(
G
)
⩽
Δ
(
G
)
+
δ
(
G
)
-
2 for any graph G with δ(G)⩾2.Notice that the bounds stated in Theorem128 and Corollary 129 are sharp. Indeed the class of cycles whose orders are congruent to 1, 2 (mod 3) have a restrained bondage number achieving these bounds (see Theorem 125).Theorem128 is an analogue of Theorem 14. A quite natural problem is whether or not, for restricted bondage number, there are analogues of Theorem 16, Theorem 18, Theorem 29, and so on. Indeed, we should consider all results for the bondage number whether or not there are analogues for restricted bondage number.Theorem 130 (Hattingh and Plummer [80], 2008).
For any graphG with γR(G)=2,
(48)bR(G)⩽Δ(G)+1.We now consider the relation betweenbR(G) and b(G).Theorem 131 (Hattingh and Plummer [80], 2008).
IfγR(G)=γ(G) for some graph G, then bR(G)⩽b(G).Corollary129 and Theorem 131 provide a possibility to attack Conjecture 73 by characterizing planar graphs with γR=γ and bR=b when 3⩽Δ⩽6.However, we do not havebR(G)=b(G) for any graph G even if γR(G)=γ(G). Observe that γR(K3)=γ(K3), yet bR(K3)=1 and b(K3)=2. We still may not claim that bR(G)=b(G) even in the case that every γ-set is a γR-set. The example K3 again demonstrates this.Theorem 132 (Hattingh and Plummer [80], 2008).
There is an infinite class of graphs in which each graphG satisfies b(G)<bR(G).In fact, such an infinite class of graphs can be obtained as follows. LetH be a connected graph, BC(H) a graph obtained from H by attaching ℓ(⩾2) vertices of degree 1 to each vertex in H, and ℬ={G:G=BC(H) for some graph H such that δ(H)⩾2}. By Theorem 3, we can easily check that b(G)=1<2⩽min{δ(H),ℓ}=bR(G) for any G∈ℬ. Moreover, there exists a graph G∈ℬ such that bR(G) can be much larger than b(G), which is stated as the following theorem.Theorem 133 (Hattingh and Plummer [80], 2008).
For each positive integerk, there is a graph G such that k=bR(G)-b(G).Combining Theorem133 with Theorem 132, we have the following corollary.Corollary 134.
The bondage number and the restrained bondage number are unrelated.Very recently, Jafari Rad et al. [81] have considered the total restrained bondage in graphs based on both total dominating sets and restrained dominating sets and obtained several properties, exact values, and bounds for the total restrained bondage number of a graph.A restrained dominating setS of a graph G without isolated vertices is called to be a total restrained dominating set if S is a total dominating set. The total restrained domination number of G, denoted by γTR(G), is the minimum cardinality of a total restrained dominating set of G. For references on this domination in graphs, see [3, 61, 82–85]. The total restrained bondage numberbTR(G) of a graph G with no isolated vertex, is the cardinality of a smallest set of edges B⊆E(G) for which G-B has no isolated vertex and γTR(G-B)>γTR(G). In the case that there is no such subset B, we define bTR(G)=∞.Ma  et al. [84] determined that γTR(Pn)=n-2⌊(n-2)/4⌋ for n⩾3, γTR(Cn)=n-2⌊n/4⌋ for n⩾3, γTR(K3)=3 and γTR(Kn)=2 for n≠3, and γTR(K1,n)=1+n and γTR(Km,n)=2 for 2⩽m⩽n. According to these results, Jafari Rad  et al. [81] determined the exact values of total restrained bondage numbers for the corresponding graphs.Theorem 135 (Jafari Rad et al. [81]).
For an integern,
(49)bTR(Pn)={∞if2⩽n⩽5,1,ifn⩾5bTR(Cn)={∞ifn=3,1,if3<n,n≡0,1(mod4)2,if3<n,n≡2,3(mod4)bTR(Wn)=2forn⩾6,bTR(Kn)=n-1forn⩾4,bTR(Km,n)=m-1for2⩽m⩽n.bTR(Kn)=n-1 shows the fact that for any integer n⩾3 there exists a connected graph, namely, Kn+1 such that bTR(Kn+1)=n; that is, the total restrained bondage number is unbounded from the above.A vertex is said to be asupport vertex if it is adjacent to a vertex of degree one. Let 𝒜 be the family of all connected graphs such that G belongs to 𝒜 if and only if every edge of G is incident to a support vertex or G is a cycle of length three.Proposition 136 (Cyman and Raczek [82], 2006).
For a connected graphG of order n, γTR(G)=n if and only if G∈𝒜.Hence, ifG∈𝒜, then the removal of any subset of edges of G cannot increase the total restrained domination number of G and thus bTR(G)=∞. When G∉𝒜, a result similar to Theorem 6 is obtained.Theorem 137 (Jafari Rad et al. [81]).
For any treeT∉𝒜, bTR(T)⩽2. This bound is sharp.In the same paper, the authors provided a characterization for treesT∉𝒜 with bTR(T)=1 or 2. The following result is similar to Observation 1.Observation 3 (Jafari Rad et al. [81]).
Ifk edges can be removed from a graph G to obtain a graph H without an isolated vertex and with bTR(H)=t, then bTR(G)⩽k+t.Applying Theorem137 and Observation 3, Jafari Rad  et al. characterized all connected graphs G with bTR(G)=∞.Theorem 138 (Jafari Rad et al. [81]).
For a connected graphG, bTR(G)=∞ if and only if G∈𝒜.


### 8.4. Other Conditional Bondage Numbers

A subsetI⊆V(G) is called an independent set if no two vertices in I are adjacent in G. The maximum cardinality among all independent sets is called the independence number of G, denoted by α(G).A dominating setS of a graph G is called to be independent if S is an independent set of G. The minimum cardinality among all independent dominating set is called the independence domination number of G and denoted by γI(G).Since an independent dominating set is not only a dominating set but also an independent set,γ(G)⩽γI(G)⩽α(G) for any graph G.It is clear that a maximal independent set is certainly a dominating set. Thus, an independent set is maximal if and only if it is an independent dominating set, and soγI(G) is the minimum cardinality among all maximal independent sets of G. This graph-theoretical invariant has been well studied in the literature; see, for example, Haynes et al. [3] for early results, Goddard and Henning [86] for recent results on independent domination in graphs.In 2003, Zhang et al. [87] defined the independence bondage numberbI(G) of a nonempty graph G to be the minimum cardinality among all subsets B⊆E(G) for which γI(G-B)>γI(G). For some ordinary graphs, their independence domination numbers can be easily determined, and so independence bondage numbers have been also determined. Clearly, bI(Kn)=1 if n⩾2.Theorem 139 (Zhang et al. [87], 2003).
For any integern⩾4,
(50)bI(Cn)={1ifn≡1(mod2),2ifn≡0(mod2),bI(Pn)={1ifn≡0(mod2),2ifn≡1(mod2),bI(Km,n)=nform⩽n.Apart from the above-mentioned results, as far as we find no other results on the independence bondage number in the present literature, we never knew much of any result on this parameter for a tree.A subsetS of V(G) is called an equitable dominating set if for every y∈V(G-S) there exists a vertex x∈S such that xy∈E(G) and |dG(x)-dG(y)|⩽1 proposed by Dharmalingam [88]. The minimum cardinality of such a dominating set is called the equitable domination number and is denoted by γE(G). Deepak  et al. [89] defined the equitable bondage numberbE(G) of a graph G to be the cardinality of a smallest set B⊆E(G) of edges for which γE(G-B)>γE(G) and determined bE(G) for some special graphs.Theorem 140 (Deepak et al. [89], 2011).
For any integern⩾2,
(51)bE(Kn)=⌈n2⌉,bE(Km,n)=mfor0⩽n-m⩽1,bE(Cn)={3ifn≡1(mod3)2otherwise,bE(Pn)={2ifn≡1(mod3)1otherwise,bE(T)⩽2foranynontrivialtreeT,bE(G)⩽n-1foranyconnectedgraphGofordern.As far as we know, there are no more results on the equitable bondage number of graphs in the present literature.There are other variations of the normal domination by adding restricted conditions to the normal dominating set. For example, theconnected domination set of a graph G, proposed by Sampathkumar and Walikar [90], is a dominating set S such that the subgraph induced by S is connected. The problem of finding a minimum connected domination set in a graph is equivalent to the problem of finding a spanning tree with maximum number of vertices of degree one [91], and has some important applications in wireless networks [92]; thus, it has received much research attention. However, for such an important domination, there is no result on its bondage number. We believe that the topic is of significance for future research.


## 8.1. Total Bondage Numbers

A dominating setS of a graph G without isolated vertices is called total if the subgraph induced by S contains no isolated vertices. The minimum cardinality of a total dominating set is called the total domination number of G and denoted by γT(G). It is clear that γ(G)⩽γT(G)⩽2γ(G) for any graph G without isolated vertices.The total domination in graphs was introduced by Cockayne  et al. [58] in 1980. Pfaff  et al. [59, 60] in 1983 showed that the problem determining total domination number for general graphs is NP-complete, even for bipartite graphs and chordal graphs. Even now, total domination in graphs has been extensively studied in the literature. In 2009, Henning [61] gave a survey of selected recent results on total domination in graphs.Thetotal bondage number of G, denoted by bT(G), is the smallest cardinality of a subset B⊆E(G) with the property that G-B contains no isolated vertices and γT(G-B)>γT(G).From definition,bT(G) may not exist for some graphs, for example, G=K1,n. We put bT(G)=∞ if bT(G) does not exist. It is easy to see that bT(G) is finite for any connected graph G other than K1,K2,K3, and K1,n. In fact, for such a graph G, since there is a path of length 3 in G, we can find B1⊆E(G) such that G-B1 is a spanning tree T of G, containing a path of length 3. So γT(T)=γT(G-B1)⩾γT(G). For the tree T, we find B2⊆E(T) such that γT(T-B2)>γT(T)⩾γT(G). Thus, we have γT(G-B2-B1)>γT(G), and so bT(G)⩽|B1|+|B2|. In the following discussion, we always assume that bT(G) exists when a graph G is mentioned.In 1991, Kulli and Patwari [62] first studied the total bondage number of a graph and calculated the exact values of bT(G) for some standard graphs.Theorem 110 (Kulli and Patwari [62], 1991).
Forn⩾4,
(40)bT(Cn)={3ifn≡2(mod4),2otherwise,bT(Pn)={2ifn≡2(mod4),1otherwise,bT(Km,n)=mwith2⩽m⩽n,bT(Kn)={4forn=4,2n-5forn⩾5.Recently, Hu et al. [63] have obtained some results on the total bondage number of the Cartesian product Pm×Pn of two paths Pm and Pn.Theorem 111 (Hu et al. [63], 2012).
For the Cartesian productPm×Pn of two paths Pm and Pn,
(41)bT(P2×Pn)={1ifn≡0(mod3),2ifn≡2(mod3),3ifn≡1(mod3),bT(P3×Pn)=1,bT(P4×Pn){=1ifn≡1(mod5),=2ifn≡4(mod5),⩽3ifn≡2(mod5),⩽4ifn≡0,3(mod5).Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied recently. By constructing a family of minimum total dominating sets, Cao  et al. [64] determined the total bondage number of the generalized Petersen graphs.From Theorem6, we know that b(T)⩽2 for a nontrivial tree T. But given any positive integer k, Sridharan  et al. [65] constructed a tree T for which bT(T)=k. Let Hk be the tree obtained from a star K1,k+1 by subdividing k edges twice. The tree H7 is shown in Figure 6. It can be easily verified that bT(Hk)=k. This fact can be stated as the following theorem.Figure 6
H
7.Theorem 112 (Sridharan et al. [65], 2007).
For any positive integerk, there exists a tree T with bT(T)=k.Combining Theorem1 with Theorem 112, we have what follows.Corollary 113 (Sridharan et al. [65], 2007).
The bondage number and the total bondage number are unrelated, even for trees.However, Sridharan  et al. [65] gave an upper bound on the total bondage number of a tree in terms of its maximum degree. For any tree T of order n, if T≠K1,n-1, then bT(T)=min{Δ(T),(1/3)(n-1)}. Rad and Raczek [66] improved this upper bound and gave a constructive characterization of a certain class of trees attaching the upper bound.Theorem 114 (Rad and Raczek [66], 2011).
b
T
(
T
)
⩽
Δ
(
T
)
-
1  for any tree T with maximum degree at least three.In general, the decision problem forbT(G) is NP-complete for any graph G. We state the decision problem for the total bondage as follows.Problem 3.
Consider the decision problem:Total Bondage ProblemInstance: a graphG and a positive integer b.Question: isbT(G)⩽b?Theorem 115 (Hu and Xu [16], 2012).
The total bondage problem is NP-complete.Consequently, in view of its computational hardness, it is significative to establish some sharp bounds on the total bondage number of a graph in terms of other graphic parameters. In 1991, Kulli and Patwari [62] showed that bT(G)⩽2n-5 for any graph G with order n⩾5. Sridharan  et al. [65] improved this result as follows.Theorem 116 (Sridharan et al. [65], 2007).
For any graphG with order n, if n⩾5, then
(42)bT(G)⩽{13(n-1)ifGcontainsnocycles,n-1ifg(G)⩾5,n-2ifg(G)=4.Rad and Raczek [66] also established some upper bounds on bT(G) for a general graph G. In particular, they gave an upper bound on bT(G) in terms of the girth of G.Theorem 117 (Rad and Raczek [66], 2011).
b
T
(
G
)

⩽

4
Δ
(
G
)
-
5 for any graph G with g(G)⩾4.


## 8.2. Paired Bondage Numbers

A dominating setS of G is called to be paired if the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γP(G), is the minimum cardinality of a paired dominating set of G. Clearly, γT(G)⩽γP(G) for every connected graph G with order at least two, where γT(G) is the total domination number of G, and γP(G)⩽2γ(G) for any graph G without isolated vertices. Paired domination was introduced by Haynes and Slater [67, 68] and further studied in [69–72].Thepaired bondage number of G with δ(G)⩾1, denoted by bP(G), is the minimum cardinality among all sets of edges B⊆E such that δ(G-B)⩾1 and γP(G-B)>γP(G).The concept of the paired bondage number was first proposed by Raczek [73] in 2008. The following observations follow immediately from the definition of the paired bondage number.Observation 2.
LetG be a graph with δ(G)⩾1.(a)
IfH is a subgraph of G such that δ(H)⩾1, then bP(H)⩽bP(G).(b)
IfH is a subgraph of G such that bP(H)=1 and k is the number of edges removed to form H, then 1⩽bP(G)⩽k+1.(c)
Ifxy∈E(G) such that dG(x),dG(y)>1, and xy belongs to each perfect matching of each minimum paired dominating set of G, then bP(G)=1.Based on these observations,bP(Pn)⩽2. In fact, the paired bondage number of a path has been determined.Theorem 118 (Raczek [73], 2008).
For any positive integerk, if n⩾2, then
(43)bP(Pn)={0ifn=2,3,or5,1ifn=4k,4k+3,or4k+6,2otherwise.For a cycleCn of order n⩾3, since γP(Cn)=γP(Pn), from Theorem 118 the following result holds immediately.Corollary 119 (Raczek [73], 2008).
For any positive integerk, if n⩾3, then
(44)bP(Cn)={0ifn=3or5,2ifn=4k,4k+3,or4k+6,3otherwise.A wheelWn, where n⩾4, is a graph with n vertices, formed by connecting a single vertex to all vertices of a cycle Cn-1. Of course γP(Wn)=2.Theorem 120 (Raczek [73], 2008).
For positive integersn and m,
(45)bP(Km,n)=mfor1<m⩽n,bP(Wn)={4ifn=4,3ifn=5,2otherwise.Theorem16 shows that if T is a nontrivial tree, then b(T)⩽2. However, no similar result exists for paired bondage. For any nonnegative integer k, let Tk be a tree obtained by subdividing all but one edge of a star K1,k+1 (as shown in Figure 7). It is easy to see that bP(Tk)=k. We state this fact as the following theorem, which is similar to Theorem 112.Figure 7
A treeT with bP(T)=k.Theorem 121 (Raczek [73], 2008).
For any nonnegative integerk, there exists a tree T with bP(T)=k.Consider the tree defined in Figure5 for k=3. Then b(T3)⩽2 and bP(T3)=3. On the other hand, b(P4)=2 and bP(P4)=1. Thus, we have what follows, which is similar to Corollary 113.Corollary 122.
The bondage number and the paired bondage number are unrelated, even for trees.A constructive characterization of trees withb(T)=2 is given by Hartnell and Rall in [12]. Raczek [73] provided a constructive characterization of trees with bP(T)=0. In order to state the characterization, we define a labeling and three simple operations on a tree T. Let y∈V(T) and let ℓ(y) be the label assigned to y.Operation𝒯1. If ℓ(y)=B, add a vertex x and the edge yx, and let ℓ(x)=A.Operation𝒯2. If ℓ(y)=C, add a path (x1,x2) and the edge yx1, and let ℓ(x1)=B, ℓ(x2)=A.Operation𝒯3. If ℓ(y)=B, add a path (x1,x2,x3) and the edge yx1, and let ℓ(x1)=C,ℓ(x2)=B, and ℓ(x3)=A.LetP2=(u,v) with ℓ(u)=A and ℓ(v)=B. Let 𝒯 be the class of all trees obtained from the labeled P2 by a finite sequence of operations 𝒯1, 𝒯2, 𝒯3.A treeT in Figure 8 belongs to the family 𝒯.Figure 8
A treeT belong to the family 𝒯.Raczek [73] obtained the following characterization of all trees T with bP(T)=0.Theorem 123 (Raczek [73], 2008).
For a treeT, bP(T)=0 if and only if T is in 𝒯.We state the decision problem for the paired bondage as follows.Problem 4.
Consider the decision problem:Paired Bondage ProblemInstance: a graphG and a positive integer b.Question: isbP(G)⩽b?Conjecture 124.
The paired bondage problem is NP-complete.


## 8.3. Restrained Bondage Numbers

A dominating setS of G is called to berestrained if the subgraph induced by S- contains no isolated vertices, where S-=V(G)∖S. The restrained domination number of G, denoted by γR(G), is the smallest cardinality of a restrained dominating set of G. It is clear that γR(G) exists and γ(G)⩽γR(G) for any nonempty graph G.The concept of restrained domination was introduced by Telle and Proskurowski [74] in 1997, albeit indirectly, as a vertex partitioning problem. Concerning the study of the restrained domination numbers, the reader is referred to [74–79].In 2008, Hattingh and Plummer [80] defined the restrained bondage numberbR(G) of a nonempty graph G to be the minimum cardinality among all subsets B⊆E(G) for which γR(G-B)>γR(G).For some simple graphs, their restrained domination numbers can be easily determined, and so restrained bondage numbers have been also determined. For example, it is clear thatγR(Kn)=1. Domke  et al. [77] showed that γR(Cn)=n-2⌊n/3⌋ for n⩾3, and γR(Pn)=n-2⌊(n-1)/3⌋ for n⩾1. Using these results, Hattingh and Plummer [80] obtained the restricted bondage numbers for Kn,Cn,Pn, and G=Kn1,n2,…,nt as follows.Theorem 125 (Hattingh and Plummer [80], 2008).
Forn⩾3,
(46)bR(Kn)={1ifn=3,⌈n2⌉otherwise,bR(Cn)={1ifn≡0(mod3),2otherwise,bR(Pn)=1,n⩾4,bR(G)={⌈m2⌉ifnm=1andnm+1⩾2(1⩽m<t),2t-2ifn1=n2=⋯=nt=2(t⩾2),2ifn1=2andn2⩾3(t=2),∑i=1t-1‍ni-1otherwise.Theorem 126 (Hattingh and Plummer [80], 2008).
For a treeT of order n(⩾4), T≇K1,n-1 if and only if bR(T)=1.Theorem126 shows that the restrained bondage number of a tree can be computed in constant time. However, the decision problem for bR(G) is NP-complete even for bipartite graphs.Problem 5.
Consider the decision problem:Restrained Bondage ProblemInstance: a graphG and a positive integer b.Question: isbR(G)⩽b?Theorem 127 (Hattingh and Plummer [80], 2008).
The restrained bondage problem is NP-complete, even for bipartite graphs.Consequently, in view of its computational hardness, it is significative to establish some sharp bounds on the restrained bondage number of a graph in terms of other graphic parameters.Theorem 128 (Hattingh and Plummer [80], 2008).
For any graphG with δ(G)⩾2,
(47)bR(G)⩽minxy∈E(G){dG(x)+dG(y)-2}.Corollary 129.
b
R
(
G
)
⩽
Δ
(
G
)
+
δ
(
G
)
-
2 for any graph G with δ(G)⩾2.Notice that the bounds stated in Theorem128 and Corollary 129 are sharp. Indeed the class of cycles whose orders are congruent to 1, 2 (mod 3) have a restrained bondage number achieving these bounds (see Theorem 125).Theorem128 is an analogue of Theorem 14. A quite natural problem is whether or not, for restricted bondage number, there are analogues of Theorem 16, Theorem 18, Theorem 29, and so on. Indeed, we should consider all results for the bondage number whether or not there are analogues for restricted bondage number.Theorem 130 (Hattingh and Plummer [80], 2008).
For any graphG with γR(G)=2,
(48)bR(G)⩽Δ(G)+1.We now consider the relation betweenbR(G) and b(G).Theorem 131 (Hattingh and Plummer [80], 2008).
IfγR(G)=γ(G) for some graph G, then bR(G)⩽b(G).Corollary129 and Theorem 131 provide a possibility to attack Conjecture 73 by characterizing planar graphs with γR=γ and bR=b when 3⩽Δ⩽6.However, we do not havebR(G)=b(G) for any graph G even if γR(G)=γ(G). Observe that γR(K3)=γ(K3), yet bR(K3)=1 and b(K3)=2. We still may not claim that bR(G)=b(G) even in the case that every γ-set is a γR-set. The example K3 again demonstrates this.Theorem 132 (Hattingh and Plummer [80], 2008).
There is an infinite class of graphs in which each graphG satisfies b(G)<bR(G).In fact, such an infinite class of graphs can be obtained as follows. LetH be a connected graph, BC(H) a graph obtained from H by attaching ℓ(⩾2) vertices of degree 1 to each vertex in H, and ℬ={G:G=BC(H) for some graph H such that δ(H)⩾2}. By Theorem 3, we can easily check that b(G)=1<2⩽min{δ(H),ℓ}=bR(G) for any G∈ℬ. Moreover, there exists a graph G∈ℬ such that bR(G) can be much larger than b(G), which is stated as the following theorem.Theorem 133 (Hattingh and Plummer [80], 2008).
For each positive integerk, there is a graph G such that k=bR(G)-b(G).Combining Theorem133 with Theorem 132, we have the following corollary.Corollary 134.
The bondage number and the restrained bondage number are unrelated.Very recently, Jafari Rad et al. [81] have considered the total restrained bondage in graphs based on both total dominating sets and restrained dominating sets and obtained several properties, exact values, and bounds for the total restrained bondage number of a graph.A restrained dominating setS of a graph G without isolated vertices is called to be a total restrained dominating set if S is a total dominating set. The total restrained domination number of G, denoted by γTR(G), is the minimum cardinality of a total restrained dominating set of G. For references on this domination in graphs, see [3, 61, 82–85]. The total restrained bondage numberbTR(G) of a graph G with no isolated vertex, is the cardinality of a smallest set of edges B⊆E(G) for which G-B has no isolated vertex and γTR(G-B)>γTR(G). In the case that there is no such subset B, we define bTR(G)=∞.Ma  et al. [84] determined that γTR(Pn)=n-2⌊(n-2)/4⌋ for n⩾3, γTR(Cn)=n-2⌊n/4⌋ for n⩾3, γTR(K3)=3 and γTR(Kn)=2 for n≠3, and γTR(K1,n)=1+n and γTR(Km,n)=2 for 2⩽m⩽n. According to these results, Jafari Rad  et al. [81] determined the exact values of total restrained bondage numbers for the corresponding graphs.Theorem 135 (Jafari Rad et al. [81]).
For an integern,
(49)bTR(Pn)={∞if2⩽n⩽5,1,ifn⩾5bTR(Cn)={∞ifn=3,1,if3<n,n≡0,1(mod4)2,if3<n,n≡2,3(mod4)bTR(Wn)=2forn⩾6,bTR(Kn)=n-1forn⩾4,bTR(Km,n)=m-1for2⩽m⩽n.bTR(Kn)=n-1 shows the fact that for any integer n⩾3 there exists a connected graph, namely, Kn+1 such that bTR(Kn+1)=n; that is, the total restrained bondage number is unbounded from the above.A vertex is said to be asupport vertex if it is adjacent to a vertex of degree one. Let 𝒜 be the family of all connected graphs such that G belongs to 𝒜 if and only if every edge of G is incident to a support vertex or G is a cycle of length three.Proposition 136 (Cyman and Raczek [82], 2006).
For a connected graphG of order n, γTR(G)=n if and only if G∈𝒜.Hence, ifG∈𝒜, then the removal of any subset of edges of G cannot increase the total restrained domination number of G and thus bTR(G)=∞. When G∉𝒜, a result similar to Theorem 6 is obtained.Theorem 137 (Jafari Rad et al. [81]).
For any treeT∉𝒜, bTR(T)⩽2. This bound is sharp.In the same paper, the authors provided a characterization for treesT∉𝒜 with bTR(T)=1 or 2. The following result is similar to Observation 1.Observation 3 (Jafari Rad et al. [81]).
Ifk edges can be removed from a graph G to obtain a graph H without an isolated vertex and with bTR(H)=t, then bTR(G)⩽k+t.Applying Theorem137 and Observation 3, Jafari Rad  et al. characterized all connected graphs G with bTR(G)=∞.Theorem 138 (Jafari Rad et al. [81]).
For a connected graphG, bTR(G)=∞ if and only if G∈𝒜.


## 8.4. Other Conditional Bondage Numbers

A subsetI⊆V(G) is called an independent set if no two vertices in I are adjacent in G. The maximum cardinality among all independent sets is called the independence number of G, denoted by α(G).A dominating setS of a graph G is called to be independent if S is an independent set of G. The minimum cardinality among all independent dominating set is called the independence domination number of G and denoted by γI(G).Since an independent dominating set is not only a dominating set but also an independent set,γ(G)⩽γI(G)⩽α(G) for any graph G.It is clear that a maximal independent set is certainly a dominating set. Thus, an independent set is maximal if and only if it is an independent dominating set, and soγI(G) is the minimum cardinality among all maximal independent sets of G. This graph-theoretical invariant has been well studied in the literature; see, for example, Haynes et al. [3] for early results, Goddard and Henning [86] for recent results on independent domination in graphs.In 2003, Zhang et al. [87] defined the independence bondage numberbI(G) of a nonempty graph G to be the minimum cardinality among all subsets B⊆E(G) for which γI(G-B)>γI(G). For some ordinary graphs, their independence domination numbers can be easily determined, and so independence bondage numbers have been also determined. Clearly, bI(Kn)=1 if n⩾2.Theorem 139 (Zhang et al. [87], 2003).
For any integern⩾4,
(50)bI(Cn)={1ifn≡1(mod2),2ifn≡0(mod2),bI(Pn)={1ifn≡0(mod2),2ifn≡1(mod2),bI(Km,n)=nform⩽n.Apart from the above-mentioned results, as far as we find no other results on the independence bondage number in the present literature, we never knew much of any result on this parameter for a tree.A subsetS of V(G) is called an equitable dominating set if for every y∈V(G-S) there exists a vertex x∈S such that xy∈E(G) and |dG(x)-dG(y)|⩽1 proposed by Dharmalingam [88]. The minimum cardinality of such a dominating set is called the equitable domination number and is denoted by γE(G). Deepak  et al. [89] defined the equitable bondage numberbE(G) of a graph G to be the cardinality of a smallest set B⊆E(G) of edges for which γE(G-B)>γE(G) and determined bE(G) for some special graphs.Theorem 140 (Deepak et al. [89], 2011).
For any integern⩾2,
(51)bE(Kn)=⌈n2⌉,bE(Km,n)=mfor0⩽n-m⩽1,bE(Cn)={3ifn≡1(mod3)2otherwise,bE(Pn)={2ifn≡1(mod3)1otherwise,bE(T)⩽2foranynontrivialtreeT,bE(G)⩽n-1foranyconnectedgraphGofordern.As far as we know, there are no more results on the equitable bondage number of graphs in the present literature.There are other variations of the normal domination by adding restricted conditions to the normal dominating set. For example, theconnected domination set of a graph G, proposed by Sampathkumar and Walikar [90], is a dominating set S such that the subgraph induced by S is connected. The problem of finding a minimum connected domination set in a graph is equivalent to the problem of finding a spanning tree with maximum number of vertices of degree one [91], and has some important applications in wireless networks [92]; thus, it has received much research attention. However, for such an important domination, there is no result on its bondage number. We believe that the topic is of significance for future research.


## 9. Generalized Bondage Numbers

There are various generalizations of the classical domination, such asp-domination, distance domination, fractional domination, Roman domination, and rainbow domination. Every such a generalization can lead to a corresponding bondage. In this section, we introduce some of them.


### 9.1.p-Bondage Numbers

In 1985, Fink and Jacobson [93] introduced the concept of p-domination. Let p be a positive integer. A subset S of V(G) is a p-dominating set of G if |S∩NG(y)|⩾p for every y∈S-. The p-domination numberγp(G) is the minimum cardinality among all p-dominating sets of G. Any p-dominating set of G with cardinality γp(G) is called a γp-set of G. Note that a γ1-set is a classic minimum dominating set. Notice that every graph has a p-dominating set since the vertex-set V(G) is such a set. We also note that a 1-dominating set is a dominating set, and so γ(G)=γ1(G). The p-domination number has received much research attention; see a state-of-the-art survey article by Chellali  et al. [94].It is clear from definition that everyp-dominating set of a graph certainly contains all vertices of degree at most p-1. By this simple observation, to avoid the trivial case occurrence, we always assume  that Δ(G)⩾p. For p⩾2, Lu  et al. [95] gave a constructive characterization of trees with unique minimum p-dominating sets.Recently, Lu and Xu [96] have introduced the concept to the p-bondage number of G, denoted by bp(G), as the minimum cardinality among all sets of edges B⊆E(G) such that γp(G-B)>γp(G). Clearly, b1(G)=b(G).Lu and Xu [96] established a lower bound and an upper bound on bp(T) for any integer p⩾2 and any tree T with Δ(T)⩾p and characterized all trees achieving the lower bound and the upper bound, respectively.Theorem 141 (Lu and Xu [96], 2011).
For any integerp⩾2 and any tree T with Δ(T)⩾p,
(52)1⩽bp(T)⩽Δ(T)-p+1.LetS be a given subset of V(G) and, for any x∈S, let
(53)Np(x,S,G)={y∈S¯∩NG(x):|NG(y)∩S|=p}.
Then, all trees achieving the lower bound 1 can be characterized as follows.Theorem 142 (Lu and Xu [96], 2011).
LetT be a tree with Δ(T)⩾p⩾2. Then bp(T)=1 if and only if for any γp-set S of T there exists an edge xy∈(S,S¯) such that y∈Np(x,S,T)The notationS(a,b) denotes a double star obtained by adding an edge between the central vertices of two stars K1,a-1 and K1,b-1. And the vertex with degree a (resp., b) in S(a,b) is called the L-central vertex (resp., R-central vertex) of S(a,b):To characterize all trees attaining the upper bound given in Theorem141, we define three types of operations on a tree T with Δ(T)=Δ⩾p+1:Type  1:
attach  a  pendant  edge  to  a  vertexy  with  dT(y)⩽p-2  in  T.Type  2:
attach  a  starK1,Δ-1  to  a  vertex y of  T  by  joining  its  central  vertex  to  y, where y in  a γp-set  of  T  and  dT(y)⩽Δ-1.Type  3:
attach  a  double  starS(p,Δ-1)  to  a  pendant  vertex  y  of  T  by  coinciding  its R-central vertex  with  y,  where  the  unique  neighbor  of  y  is  in  a  γp-set  of  T.Letℬ={T: a tree obtained from K1,Δ or S(p,Δ) by a finite sequence of operations of Types 1,2, and 3}.Theorem 143 (Lu and Xu [96], 2011).
A tree with the maximumΔ⩾p+1 has p-bondage number Δ-p+1 if and only if it belongs to ℬ.Theorem 144 (Lu and Xu [97], 2012).
LetGm,n=Pm×Pn. Then
(54)b2(G2,n)=1forn⩾2,b2(G3,n)={2ifn≡1(mod3),1otherwise.forn⩾2,b2(G4,n)={1ifn≡3(mod4),2otherwise.forn⩾7.Recently, Krzywkowski [98] has proposed the concept of the nonisolating 2-bondage of a graph. The nonisolating 2-bondage number of a graph G, denoted by b2′(G), is the minimum cardinality among all sets of edges B⊆E(G) such that G-B has no isolated vertices and γ2(G-B)>γ2(G). If for every B⊆E(G), either γ2(G-B)=γ2(G) or G-B has isolated vertices, then define b2′(G)=0, and say that G is a 2-nonisolatedly strongly stable graph. Krzywkowski presented some basic properties of nonisolating 2-bondage in graphs, showed that for every nonnegative integer k there exists a tree T such b2′(T)=k, characterized all 2-non-isolatedly strongly stable trees, and determined b2′(G) for several special graphs.Theorem 145 (Krzywkowski [98], 2012).
For any positive integersn and m with m⩽n,
(55)b2′(Kn)={0ifn=1,2,3⌊2n3⌋otherwise,b2′(Pn)={0ifn=1,2,31otherwise,b2′(Cn)={0ifn=31ifniseven2ifnisodd,b2′(Km,n)={3ifm=n=31ifm=n=42otherwise.


### 9.2. Distance Bondage Numbers

A subsetS of vertices of a graph G is said to be a distancek-dominating set for G if every vertex in G not in S is at distance at most k from some vertex of S. The minimum cardinality of all distance k-dominating sets is called the distancek-domination number of G and denoted by γk(G) (do not confuse with the above-mentioned γp(G)!). When k=1, a distance 1-dominating set is a normal dominating set, and so γ1(G)=γ(G) for any graph G. Thus, the distance k-domination is a generalization of the classical domination.The relation betweenγk and αk (the k-independence number, defined in Section 2.2) for a tree obtained by Meir and Moon [14], who proved that γk(T)=α2k(T) for any tree T (a special case for k=1 is stated in Proposition 10). The further research results can be found in Henning  et al. [99], Tian and Xu [100–103], and Liu  et al. [104].In 1998, Hartnell  et al. [15] defined the distancek-bondage number of G, denoted by bk(G), to be the cardinality of a smallest subset B of edges of G with the property that γk(G-B)>γk(G). From Theorem 6, it is clear that if T is a nontrivial tree, then 1⩽b1(T)⩽2. Hartnell  et al. [15] generalized this result to any integer k⩾1.Theorem 146 (Hartnell et al. [15], 1998).
For every nontrivial treeT and positive integer k, 1⩽bk(T)⩽2.Hartnell  et al. [15] and Topp and Vestergaard [13] also characterized the trees having distance k-bondage number 2. In particular, the class of trees for which b1(T)=2 are just those which have a unique maximum 2-independent set (see Theorem 11).Since, whenk=1, the distance 1-bondage number b1(G) is the classical bondage number b(G), Theorem 12 gives the NP-hardness of deciding the distance k-bondage number of general graphs.Theorem 147.
Given a nonempty undirected graphG and positive integers k and b with b⩽ε(G), determining wether or not bk(G)⩽b is NP-hard.For a vertexx in G, the openk-neighborhoodNk(x) of x is defined as Nk(x)={y∈V(G):1⩽dG(x,y)≤k}. The closedk-neighborhoodNk[x] of x in G is defined as Nk(x)∪{x}. Let
(56)Δk(G)=max{|Nk(x)|:foranyx∈V(G)}.
Clearly, Δ1(G)=Δ(G). The kthpower of a graph G is the graph Gk with vertex-set V(Gk)=V(G) and edge-set E(Gk)={xy:1⩽dG(x,y)⩽k}. The following lemma holds directly from the definition of Gk.Proposition 148 (Tian and Xu [101]).
Δ
(
G
k
)
=
Δ
k
(
G
) and γ(Gk)=γk(G) for any graph G and each k⩾1.A graphG is k-distance domination-critical, or γk-critical for short, if γk(G-x)<γk(G) for every vertex x in G, proposed by Henning et al. [105]Proposition 149 (Tian and Xu [101]).
For eachk⩾1, a graph G is γk-critical if and only if Gk is γk-critical.By the above facts, we suggest the following worthwhile problem.Problem 6.
Can we generalize the results on the bondage forG to Gk? In particular, do the following propositions hold?(a)
b(Gk)=bk(G) for any graph G and each k⩾1.(b)
b(Gk)⩽Δk(G) if G is not γk-critical.Letk and p be positive integers. A subset S of V(G) is defined to be a (k,p)-dominating set of G if, for any vertex x∈S¯, |Nk(x)∩S|⩾p. The (k,p)-domination number of G, denoted by γk,p(G), is the minimum cardinality among all (k,p)-dominating sets of G. Clearly, for a graph G, a (1,1)-dominating set is a classical dominating set, a (k,1)-dominating set is a distance k-dominating set, and a (1,p)-dominating set is the above-mentioned p-dominating set. That is, γ1,1(G)=γ(G), γk,1(G)=γk(G), and γ1,p(G)=γp(G).The concept of(k,p)-domination in a graph G is a generalized domination which combines distance k-domination and p-domination in G. So, the investigation of (k,p)-domination of G is more interesting and has received the attention of many researchers; see, for example, [106–109].More general, Li and Xu [110] proposed the concept of the (ℓ,w)-domination number of a w-connected graph. A subset S of V(G) is defined to be an (ℓ,w)-dominating set of G if, for any vertex x∈S¯, there are w internally disjoint paths of length at most ℓ from x to some vertex in S. The (ℓ,w)-domination number of G, denoted by γℓ,w(G), is the minimum cardinality among all (ℓ,w)-dominating sets of G. Clearly, γk,1(G)=γk(G) and γ1,p(G)=γp(G).It is quite natural to propose the concept of bondage number for(k,p)-domination or (ℓ,w)-domination. However, as far as we know, none has proposed this concept until today. This is a worthwhile topic for further research.


### 9.3. Fractional Bondage Numbers

Ifσ is a function mapping the vertex-set V into some set of real numbers, then for any subset S⊆V; let σ(S)=∑x∈Sσ(x). Also let |σ|=σ(V).A real-value functionσ:V→[0,1] is a dominating function of a graph G if for every x∈V(G), σ(NG[x])⩾1. Thus, if S is a dominating set of G, σ is a function, where
(57)σ(x)={1ifx∈S,0otherwise,
then σ is a dominating function of G. The fractional domination number of G, denoted by γF(G), is defined as follows.
(58)γF(G)=min{|σ|:σisadominationfunctionofG}.TheγF-bondage number of G, denoted by bF(G), is defined as the minimum cardinality of a subset B⊆E whose removal results in γF(G-B)>γF(G).Hedetniemi  et al. [111] are the first to study fractional domination although Farber [112] introduced the idea indirectly. The concept of the fractional domination number was proposed by Domke and Laskar [113] in 1997. The fractional domination numbers for some ordinary graphs are determined.Proposition 150 (Domke et al. [114], 1998; Domke and Laskar [113], 1997).
(
a
)  If G is a k-regular graph with order n, then γF(G)=n/k+1;
(
b
)
γ
F
(
C
n
)
=
n
/
3, γF(Pn)=⌈n/3⌉, γF(Kn)=1;
(
c
)
γ
F
(
G
)
=
1 if and only if Δ(G)=n-1;
(
d
)
γ
F
(
T
)
=
γ
(
T
) for any tree T;
(
e
)
γ
F
(
K
n
,
m
)
=
(
n
(
m
+
1
)
+
m
(
n
+
1
)
)
/
(
n
m
-
1
), where max{n,m}>1.The assertions (a)–(d) are due to Domke  et al. [114] and the assertion (e) is due to Domke and Laskar [113]. According to these results, Domke and Laskar [113] determined the γF-bondage numbers for these graphs.Theorem 151 (Domke and Laskar [113], 1997).
b
F
(
K
n
)
=
⌈
n
/
2
⌉;bF(Kn,m)=1 where max{n,m}>1,
(59)bF(Cn)={2ifn≡0(mod3),1otherwise,bF(Pn)={2ifn≡1(mod3),1otherwise,It is easy to see that for any treeT, bF(T)⩽2. In fact, since γF(T)=γ(T) for any tree T, γF(T′)=γ(T′) for any subgraph T′ of T. It follows that
(60)bF(T)=min{B⊆E(T):γF(T-B)>γF(T)}=min{B⊆E(T):γ(T-B)>γ(T)}=b(T)⩽2.Except for these, no results onbF(G) have been known as yet.


### 9.4. Roman Bondage Numbers

ARoman dominating function on a graph G is a labeling f:V→{0,1,2} such that every vertex with label 0 has at least one neighbor with label 2. The weight of a Roman dominating function f on G is the value
(61)f(G)=∑u∈V(G)‍f(u).
The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γRM(G).A Roman dominating functionf:V→{0,1,2} can be represented by the ordered partition (V0,V1,V2) (or (V0f,V1f,V2f) to refer to f) of V, where Vi={v∈V∣f(v)=i}. In this representation, its weight f(G)=|V1|+2|V2|. It is clear that V1f∪V2f is a dominating set of G, called the Roman dominating set, denoted by DRf=(V1,V2). Since V1f∪V2f is a dominating set when f is a Roman dominating function, and since placing weight 2 at the vertices of a dominating set yields a Roman dominating function, in [115], it is observed that
(62)γ(G)⩽γRM(G)⩽2γ(G).
A graph G is called to be Roman if γRM(G)=2γ(G).The definition of the Roman domination function is proposed implicitly by Stewart [116] and ReVelle and Rosing [117]. Roman dominating numbers have been deeply studied. In particular, Bahremandpour  et al. [118] showed that the problem determining the Roman domination number is NP-complete even for bipartite graphs.LetG be a graph with maximum degree at least two. The Roman bondage numberbRM(G) of G is the minimum cardinality of all sets E′⊆E for which γRM(G-E′)>γRM(G). Since in study of Roman bondage number the assumption Δ(G)⩾2 is necessary, we always assume that when we discuss bRM(G), all graphs involved satisfy Δ(G)⩾2. The Roman bondage number bRM(G) is introduced by Jafari Rad and Volkmann in [119].Recently, Bahremandpour  et al. [118] have shown that the problem determining the Roman bondage number is NP-hard even for bipartite graphs.Problem 7.
Consider the decision problem:Roman Bondage ProblemInstance: a nonempty bipartite graphG and a positive integer k.Question: isbRM(G)⩽k?Theorem 152 (Bahremandpour et al. [118], 2013).
The Roman bondage problem is NP-hard even for bipartite graphs.The exact value ofbRM(G) is known only for a few family of graphs including the complete graphs, cycles, and paths.Theorem 153 (Jafari Rad and Volkmann [119], 2011).
For any positive integersn and m with m⩽n,
(63)bRM(Pn)={2,ifn≡2(mod3),1,otherwise,bRM(Cn)={3,ifn=2(mod3),2,otherwise,bRM(Kn)=⌈n2⌉forn⩾3,bRM(Km,n)={1ifm=1andn≠1,4ifm=n=3,motherwise.Lemma 154 (Cockayne et al. [115], 2004).
IfG is a graph of order n and contains vertices of degree n-1, then γRM(G)=2.Using Lemma154, the third conclusion in Theorem 153 can be generalized to more general case, which is similar to Lemma 49.Theorem 155 (Jafari Rad and Volkmann [119], 2011).
LetG be a graph with order n≥3 and t the number of vertices of degree n-1 in G. If t⩾1, then bRM(G)=⌈t/2⌉.Ebadi and PushpaLatha [120] conjectured that bRM(G)⩽n-1 for any graph G of order n⩾3. Dehgardi et al. [121], Akbari and Qajar [122], independently, showed that this conjecture is true.Theorem 156.
b
RM
(
G
)
⩽
n
-
1 for any connected graph G of order n⩾3.For a completet-partite graph, we have the following result.Theorem 157 (Hu and Xu [123], 2011).
LetG=Km1,m2,…,mt be a complete t-partite graph with m1=⋯=mi<mi+1≤⋯⩽mt, t⩾2 and n=∑j=1tmj. Then
(64)bRM(G)={⌈i2⌉ifmi=1andn⩾3,2ifmi=2andi=1,iifmi=2andi⩾2,4ifmi=3andi=t=2,n-1ifmi=3andi=t⩾3,n-mtifmi⩾3andmt⩾4.Consider a completet-partite graph Kt(3) for t⩾3, bRM(Kt(3))=n-1 by Theorem 157, where n=3t, which shows that this upper bound of n-1 on bRM(G) in Theorem 156 is sharp. This fact and γR(Kt(3))=4 give a negative answer to the following two problems posed by Dehgardi et al. [121].Prove or Disprove: for any connected graph G of order n≥3,  (i) bRM(G)=n-1 if and only if G≅K3;  (ii) bRM(G)⩽n-γR(G)+1.Note that a completet-partite graph Kt(3) is (n-3)-regular and bRM(Kt(3))=n-1 for t⩾3, where n=3t. Hu and Xu further determined that bR(G)=n-2 for any (n-3)-regular graph G of order n⩽5 except Kt(3).Theorem 158 (Hu and Xu [123], 2011).
For any (n-3)-regular graph G of order n other than Kt(3), bRM(G)=n-2 for n⩾5.For a treeT with order n⩾3, Ebadi and PushpaLatha [120], and Jafari Rad and Volkmann [119], independently, obtained an upper bound on bRM(T).Theorem 159.
b
RM
(
T
)
⩽
3 for any tree T with order n⩾3.Theorem 160 (Bahremandpour et al. [118], 2013).
b
RM
(
P
2
×
P
n
)
=
2 for n⩾2.Theorem 161 (Jafari Rad and Volkmann [119], 2011).
LetG be a graph with order at least three.(a)
If(x,y,z) is a path of length 2 in G, then bRM(G)⩽dG(x)+dG(y)+dG(z)-3-|NG(x)∩NG(y)|.(b)
IfG is connected, then bRM(G)⩽λ(G)+2Δ(G)-3.Theorem161 (b) implies bRM(G)⩽δ(G)+2Δ(G)-3 for a connected graph G. Note that for a planar graph G, δ(G)⩽5; moreover, δ(G)⩽3 if the girth at least 4, and δ(G)⩽2 if the girth at least 6. These two facts show that bRM(G)⩽2Δ(G)+2 for a connected planar graph G. Jafari Rad and Volkmann [124] improved this bound.Theorem 162 (Jafari Rad and Volkmann [124], 2011).
For any connected planar graphG of order n⩾3 with girth g(G),
(65)bRM(G)⩽{2Δ(G),Δ(G)+6,Δ(G)+5ifGcontainsnoverticesofdegreefive,Δ(G)+4ifg(G)⩾4,Δ(G)+3ifg(G)⩾5,Δ(G)+2ifg(G)⩾6,Δ(G)+1ifg(G)⩾8.According to Theorem157, bRM(Cn)=3=Δ(Cn)+1 for a cycle Cn of length n⩾8 with n≡2(mod3), and therefore the last upper bound in Theorem 162 is sharp, at least for Δ=2.Combining the fact that every planar graphG with minimum degree 5 contains an edge xy with dG(x)=5 and dG(y)∈{5,6} with Theorem 161 (a), Akbari et al. [125] obtained the following result.Theorem 163 (Akbari et al. [125], 2012).
b
RM
(
G
)
⩽
15 for every planar graph G.It remains open to show whether the bound in Theorem163 is sharp or not. Though finding a planar graph G with bRM(G)=15 seems to be difficult, Akbari et al. [125] constructed an infinite family of planar graphs with Roman bondage number equal to 7 by proving the following result.Theorem 164 (Akbari et al. [125], 2012).
LetG be a graph of order n and G^ is the graph of order 5n obtained from G by attaching the central vertex of a copy of a path P5 to each vertex of G (see Figure 9). Then γRM(G^)=4n and bRM(G^)=δ(G)+2.Figure 9
The graphG^ is constructed from G.By Theorem164, infinite many planar graphs with Roman bondage number 7 can be obtained by considering any planar graph G with δ(G)=5 (e.g., the icosahedron graph).Conjecture 165 (Akbari et al. [125], 2012).
The Roman bondage number of every planar graph is at most 7.For general bounds, the following observation is directly obtained, which is similar to Observation1.Observation 4.
LetG be a graph of order n with maximum degree at least two. Assume that H is a spanning subgraph obtained from G by removing k edges. If γRM(H)=γRM(G), then bR(H)⩽bRM(G)⩽bRM(H)+k.Theorem 166 (Bahremandpour et al. [118], 2013).
For any connected graphG of order n, if n⩾3 and γRM(G)=γ(G)+1, then
(66)bRM(G)⩽min{b(G),nΔ},
where nΔ is the number of vertices with maximum degree Δ in G.Observation 5.
For any graphG, if γ(G)=γRM(G), then bRM(G)⩽b(G).Theorem 167 (Bahremandpour et al. [118], 2013).
For every Roman graphG,
(67)bRM(G)⩾b(G).
The bound is sharp for cycles on n vertices where n≡0(mod3).The strict inequality in Theorem167 can hold, for example, b(C3k+2)=2<3=bRM(C3k+2) by Theorem 157.A graphG is called to be vertex Roman domination-critical if γRM(G-x)<γRM(G) for every vertex x in G. If G has no isolated vertices, then γRM(G)⩽2γ(G)⩽2β(G). If γRM(G)=2β(G), then γRM(G)=2γ(G) and hence G is a Roman graph. In [30], Volkmann gave a lot of graphs with γ(G)=β(G). The following result is similar to Theorem 57.Theorem 168 (Bahremandpour et al. [118], 2013).
For any graphG, if γRM(G)=2β(G), then(a)
bRM(G)⩾δ(G);(b)
bRM(G)⩾δ(G)+1 if G is a vertex Roman domination-critical graph.IfγRM(G)=2, then obviously bRM(G)⩽δ(G). So we assume γRM(G)⩾3. Dehgardi et al. [121] proved bRM(G)⩽(γRM(G)-2)Δ(G)+1 and posed the following problem: if G is a connected graph of order n⩾4 with γRM(G)⩾3, then
(68)bRM(G)⩽(γRM(G)-2)Δ(G).Theorem161 (a) shows that the inequality (68) holds if γRM(G)⩾5. Thus, the bound in (68) is of interest only when γRM(G) is 3 or 4.Lemma 169 (Bahremandpour et al. [118], 2013).
For any nonempty graphG of order n⩾3, γRM(G)=3 if and only if Δ(G)=n-2.The following result shows that (68) holds for all graphs G of order n⩾4 with γRM(G)=3 or 4, which improves Theorem 161 (b).Theorem 170 (Bahremandpour et al. [118], 2013).
For any connected graphG of order n⩾4,
(69)bRM(G)≤{Δ(G)=n-2ifγRM(G)=3,Δ(G)+δ(G)-1ifγRM(G)=4
with the first equality if and only if G≅C4.Recently, Akbari and Qajar [122] have proved the following result.Theorem 171 (Akbari and Qajar [122]).
For any connected graphG of order n⩾3,
(70)bRM(G)⩽n-γRM(G)+5.We conclude this section with the following problems.Problem 8.
Characterize all connected graphsG of order n⩾3, for which bRM(G)=n-1.Problem 9.
Prove or disprove: ifG is a connected graph of order n⩾3, then
(71)bRM(G)⩽n-γRM(G)+3.Note thatγR(Kt(3))=4 and bRM(Kt(3))=n-1, where n=3t for t⩾3. The upper bound on bRM(G) given in Problem 9 is sharp if Problem 9 has positive answer.


### 9.5. Rainbow Bondage Numbers

For a positive integerk, a k-rainbow dominating function of a graph G is a function f from the vertex-set V(G) to the set of all subsets of the set {1,2,…,k} such that for any vertex x in G with f(x)=∅ the condition
(72)⋃y∈NG(x)‍f(y)={1,2,…,k}
is fulfilled. The weight of a k-rainbow dominating function f on G is the value
(73)f(G)=∑x∈V(G)‍|f(x)|.
The k-rainbow domination number of a graph G, denoted by γrk(G), is the minimum weight of a k-rainbow dominating function f of G.Note thatγr1(G) is the classical domination number γ(G). The k-rainbow domination number is introduced by Brešar et al. [126]. Rainbow domination of a graph G coincides with ordinary domination of the Cartesian product of G with the complete graph, in particular, γrk(G)=γ(G×Kk) for any positive integer k and any graph G [126]. Hartnell and Rall [127] proved that γ(T)<γr2(T) for any tree T, no graph has γ=γrk for k⩾3, for any k⩾2, and any graph G of order n:
(74)min{n,γ(G)+k-2}⩽γrk(G)⩽kγ(G).The introduction of rainbow domination is motivated by the study of paired domination in Cartesian products of graphs, where certain upper bounds can be expressed in terms of rainbow domination; that is, for any graphG and any graph H, if V(H) can be partitioned into kγP-sets, then γP(G×H)⩽(1/k)υ(H)γrk(G), proved by Brešar et al. [126].Dehgardi et al. [128] introduced the concept of k-rainbow bondage number of graphs. Let G be a graph with maximum degree at least two. The k-rainbow bondage number brk(G) of G is the minimum cardinality of all sets B⊆E(G) for which γrk(G-B)>γrk(G). Since in the study of k-rainbow bondage number the assumption Δ(G)⩾2 is necessary, we always assume that when we discuss brk(G), all graphs involved satisfy Δ(G)⩾2.The2-rainbow bondage number of some special families of graphs has been determined.Theorem 172 (Dehgardi et al. [128]).
For any integern⩾3,
(75)br2(Pn)=1forn⩾2,br2(Cn)={1ifn≡0(mod4),2otherwise,br2(Kn,n)={1ifn=2,3ifn=3,6ifn=4,mifn⩾5.Theorem 173 (Dehgardi et al. [128]).
For any connected graphG of order n⩾3, br2(G)⩽λ(G)+2Δ(G)-3.Theorem 174 (Dehgardi et al. [128]).
For any treeT of order n⩾3, br2(T)⩽2.Theorem 175 (Dehgardi et al. [128]).
IfG is a planar graph with maximum degree at least two, then br2(G)⩽15. Moreover, if the girth g(G)⩾4, then br2(G)⩽11 and if g(G)⩾6, then br2(G)⩽9.Theorem 176 (Dehgardi et al. [128]).
For a complete bipartite graphKp,q, if 2k+1⩽p⩽q, then brk(Kp,q)=p.Theorem 177 (Dehgardi et al. [128]).
For a complete graphKn, if n⩾k+1, then brk(Kn)=⌈kn/(k+1)⌉.The special casek=1 of Theorem 177 can be found in Theorem 1. The following is a simple observation similar to Observation 1.Observation 6 (Dehgardi et al. [128]).
LetG be a graph with maximum degree at least two, H a spanning subgraph obtained from G by removing k edges. If γrk(H)=γrk(G), then brk(H)⩽brk(G)⩽brk(H)+k.Theorem 178 (Dehgardi et al. [128]).
For every graphG with γrk(G)=kγ(G), brk(G)⩾b(G).A graphG is said to be vertexk-rainbow domination-critical if γrk(G-x)<γrk(G) for every vertex x in G. It is clear that if G has no isolated vertices, then γrk(G)⩽kγ(G)⩽kβ(G), where β(G) is the vertex-covering number of G. Thus, if γrk(G)=kβ(G), then γrk(G)=kγ(G).Theorem 179 (Dehgardi et al. [128]).
For any graphG, if γrk(G)=kβ(G), then(a)
brk(G)⩾δ(G);(b)
brk(G)⩾δ(G)+1 if G is vertex k-rainbow domination-critical.As far as we know, there are no more results on thek-rainbow bondage number of graphs in the literature.


## 9.1.p-Bondage Numbers

In 1985, Fink and Jacobson [93] introduced the concept of p-domination. Let p be a positive integer. A subset S of V(G) is a p-dominating set of G if |S∩NG(y)|⩾p for every y∈S-. The p-domination numberγp(G) is the minimum cardinality among all p-dominating sets of G. Any p-dominating set of G with cardinality γp(G) is called a γp-set of G. Note that a γ1-set is a classic minimum dominating set. Notice that every graph has a p-dominating set since the vertex-set V(G) is such a set. We also note that a 1-dominating set is a dominating set, and so γ(G)=γ1(G). The p-domination number has received much research attention; see a state-of-the-art survey article by Chellali  et al. [94].It is clear from definition that everyp-dominating set of a graph certainly contains all vertices of degree at most p-1. By this simple observation, to avoid the trivial case occurrence, we always assume  that Δ(G)⩾p. For p⩾2, Lu  et al. [95] gave a constructive characterization of trees with unique minimum p-dominating sets.Recently, Lu and Xu [96] have introduced the concept to the p-bondage number of G, denoted by bp(G), as the minimum cardinality among all sets of edges B⊆E(G) such that γp(G-B)>γp(G). Clearly, b1(G)=b(G).Lu and Xu [96] established a lower bound and an upper bound on bp(T) for any integer p⩾2 and any tree T with Δ(T)⩾p and characterized all trees achieving the lower bound and the upper bound, respectively.Theorem 141 (Lu and Xu [96], 2011).
For any integerp⩾2 and any tree T with Δ(T)⩾p,
(52)1⩽bp(T)⩽Δ(T)-p+1.LetS be a given subset of V(G) and, for any x∈S, let
(53)Np(x,S,G)={y∈S¯∩NG(x):|NG(y)∩S|=p}.
Then, all trees achieving the lower bound 1 can be characterized as follows.Theorem 142 (Lu and Xu [96], 2011).
LetT be a tree with Δ(T)⩾p⩾2. Then bp(T)=1 if and only if for any γp-set S of T there exists an edge xy∈(S,S¯) such that y∈Np(x,S,T)The notationS(a,b) denotes a double star obtained by adding an edge between the central vertices of two stars K1,a-1 and K1,b-1. And the vertex with degree a (resp., b) in S(a,b) is called the L-central vertex (resp., R-central vertex) of S(a,b):To characterize all trees attaining the upper bound given in Theorem141, we define three types of operations on a tree T with Δ(T)=Δ⩾p+1:Type  1:
attach  a  pendant  edge  to  a  vertexy  with  dT(y)⩽p-2  in  T.Type  2:
attach  a  starK1,Δ-1  to  a  vertex y of  T  by  joining  its  central  vertex  to  y, where y in  a γp-set  of  T  and  dT(y)⩽Δ-1.Type  3:
attach  a  double  starS(p,Δ-1)  to  a  pendant  vertex  y  of  T  by  coinciding  its R-central vertex  with  y,  where  the  unique  neighbor  of  y  is  in  a  γp-set  of  T.Letℬ={T: a tree obtained from K1,Δ or S(p,Δ) by a finite sequence of operations of Types 1,2, and 3}.Theorem 143 (Lu and Xu [96], 2011).
A tree with the maximumΔ⩾p+1 has p-bondage number Δ-p+1 if and only if it belongs to ℬ.Theorem 144 (Lu and Xu [97], 2012).
LetGm,n=Pm×Pn. Then
(54)b2(G2,n)=1forn⩾2,b2(G3,n)={2ifn≡1(mod3),1otherwise.forn⩾2,b2(G4,n)={1ifn≡3(mod4),2otherwise.forn⩾7.Recently, Krzywkowski [98] has proposed the concept of the nonisolating 2-bondage of a graph. The nonisolating 2-bondage number of a graph G, denoted by b2′(G), is the minimum cardinality among all sets of edges B⊆E(G) such that G-B has no isolated vertices and γ2(G-B)>γ2(G). If for every B⊆E(G), either γ2(G-B)=γ2(G) or G-B has isolated vertices, then define b2′(G)=0, and say that G is a 2-nonisolatedly strongly stable graph. Krzywkowski presented some basic properties of nonisolating 2-bondage in graphs, showed that for every nonnegative integer k there exists a tree T such b2′(T)=k, characterized all 2-non-isolatedly strongly stable trees, and determined b2′(G) for several special graphs.Theorem 145 (Krzywkowski [98], 2012).
For any positive integersn and m with m⩽n,
(55)b2′(Kn)={0ifn=1,2,3⌊2n3⌋otherwise,b2′(Pn)={0ifn=1,2,31otherwise,b2′(Cn)={0ifn=31ifniseven2ifnisodd,b2′(Km,n)={3ifm=n=31ifm=n=42otherwise.


## 9.2. Distance Bondage Numbers

A subsetS of vertices of a graph G is said to be a distancek-dominating set for G if every vertex in G not in S is at distance at most k from some vertex of S. The minimum cardinality of all distance k-dominating sets is called the distancek-domination number of G and denoted by γk(G) (do not confuse with the above-mentioned γp(G)!). When k=1, a distance 1-dominating set is a normal dominating set, and so γ1(G)=γ(G) for any graph G. Thus, the distance k-domination is a generalization of the classical domination.The relation betweenγk and αk (the k-independence number, defined in Section 2.2) for a tree obtained by Meir and Moon [14], who proved that γk(T)=α2k(T) for any tree T (a special case for k=1 is stated in Proposition 10). The further research results can be found in Henning  et al. [99], Tian and Xu [100–103], and Liu  et al. [104].In 1998, Hartnell  et al. [15] defined the distancek-bondage number of G, denoted by bk(G), to be the cardinality of a smallest subset B of edges of G with the property that γk(G-B)>γk(G). From Theorem 6, it is clear that if T is a nontrivial tree, then 1⩽b1(T)⩽2. Hartnell  et al. [15] generalized this result to any integer k⩾1.Theorem 146 (Hartnell et al. [15], 1998).
For every nontrivial treeT and positive integer k, 1⩽bk(T)⩽2.Hartnell  et al. [15] and Topp and Vestergaard [13] also characterized the trees having distance k-bondage number 2. In particular, the class of trees for which b1(T)=2 are just those which have a unique maximum 2-independent set (see Theorem 11).Since, whenk=1, the distance 1-bondage number b1(G) is the classical bondage number b(G), Theorem 12 gives the NP-hardness of deciding the distance k-bondage number of general graphs.Theorem 147.
Given a nonempty undirected graphG and positive integers k and b with b⩽ε(G), determining wether or not bk(G)⩽b is NP-hard.For a vertexx in G, the openk-neighborhoodNk(x) of x is defined as Nk(x)={y∈V(G):1⩽dG(x,y)≤k}. The closedk-neighborhoodNk[x] of x in G is defined as Nk(x)∪{x}. Let
(56)Δk(G)=max{|Nk(x)|:foranyx∈V(G)}.
Clearly, Δ1(G)=Δ(G). The kthpower of a graph G is the graph Gk with vertex-set V(Gk)=V(G) and edge-set E(Gk)={xy:1⩽dG(x,y)⩽k}. The following lemma holds directly from the definition of Gk.Proposition 148 (Tian and Xu [101]).
Δ
(
G
k
)
=
Δ
k
(
G
) and γ(Gk)=γk(G) for any graph G and each k⩾1.A graphG is k-distance domination-critical, or γk-critical for short, if γk(G-x)<γk(G) for every vertex x in G, proposed by Henning et al. [105]Proposition 149 (Tian and Xu [101]).
For eachk⩾1, a graph G is γk-critical if and only if Gk is γk-critical.By the above facts, we suggest the following worthwhile problem.Problem 6.
Can we generalize the results on the bondage forG to Gk? In particular, do the following propositions hold?(a)
b(Gk)=bk(G) for any graph G and each k⩾1.(b)
b(Gk)⩽Δk(G) if G is not γk-critical.Letk and p be positive integers. A subset S of V(G) is defined to be a (k,p)-dominating set of G if, for any vertex x∈S¯, |Nk(x)∩S|⩾p. The (k,p)-domination number of G, denoted by γk,p(G), is the minimum cardinality among all (k,p)-dominating sets of G. Clearly, for a graph G, a (1,1)-dominating set is a classical dominating set, a (k,1)-dominating set is a distance k-dominating set, and a (1,p)-dominating set is the above-mentioned p-dominating set. That is, γ1,1(G)=γ(G), γk,1(G)=γk(G), and γ1,p(G)=γp(G).The concept of(k,p)-domination in a graph G is a generalized domination which combines distance k-domination and p-domination in G. So, the investigation of (k,p)-domination of G is more interesting and has received the attention of many researchers; see, for example, [106–109].More general, Li and Xu [110] proposed the concept of the (ℓ,w)-domination number of a w-connected graph. A subset S of V(G) is defined to be an (ℓ,w)-dominating set of G if, for any vertex x∈S¯, there are w internally disjoint paths of length at most ℓ from x to some vertex in S. The (ℓ,w)-domination number of G, denoted by γℓ,w(G), is the minimum cardinality among all (ℓ,w)-dominating sets of G. Clearly, γk,1(G)=γk(G) and γ1,p(G)=γp(G).It is quite natural to propose the concept of bondage number for(k,p)-domination or (ℓ,w)-domination. However, as far as we know, none has proposed this concept until today. This is a worthwhile topic for further research.


## 9.3. Fractional Bondage Numbers

Ifσ is a function mapping the vertex-set V into some set of real numbers, then for any subset S⊆V; let σ(S)=∑x∈Sσ(x). Also let |σ|=σ(V).A real-value functionσ:V→[0,1] is a dominating function of a graph G if for every x∈V(G), σ(NG[x])⩾1. Thus, if S is a dominating set of G, σ is a function, where
(57)σ(x)={1ifx∈S,0otherwise,
then σ is a dominating function of G. The fractional domination number of G, denoted by γF(G), is defined as follows.
(58)γF(G)=min{|σ|:σisadominationfunctionofG}.TheγF-bondage number of G, denoted by bF(G), is defined as the minimum cardinality of a subset B⊆E whose removal results in γF(G-B)>γF(G).Hedetniemi  et al. [111] are the first to study fractional domination although Farber [112] introduced the idea indirectly. The concept of the fractional domination number was proposed by Domke and Laskar [113] in 1997. The fractional domination numbers for some ordinary graphs are determined.Proposition 150 (Domke et al. [114], 1998; Domke and Laskar [113], 1997).
(
a
)  If G is a k-regular graph with order n, then γF(G)=n/k+1;
(
b
)
γ
F
(
C
n
)
=
n
/
3, γF(Pn)=⌈n/3⌉, γF(Kn)=1;
(
c
)
γ
F
(
G
)
=
1 if and only if Δ(G)=n-1;
(
d
)
γ
F
(
T
)
=
γ
(
T
) for any tree T;
(
e
)
γ
F
(
K
n
,
m
)
=
(
n
(
m
+
1
)
+
m
(
n
+
1
)
)
/
(
n
m
-
1
), where max{n,m}>1.The assertions (a)–(d) are due to Domke  et al. [114] and the assertion (e) is due to Domke and Laskar [113]. According to these results, Domke and Laskar [113] determined the γF-bondage numbers for these graphs.Theorem 151 (Domke and Laskar [113], 1997).
b
F
(
K
n
)
=
⌈
n
/
2
⌉;bF(Kn,m)=1 where max{n,m}>1,
(59)bF(Cn)={2ifn≡0(mod3),1otherwise,bF(Pn)={2ifn≡1(mod3),1otherwise,It is easy to see that for any treeT, bF(T)⩽2. In fact, since γF(T)=γ(T) for any tree T, γF(T′)=γ(T′) for any subgraph T′ of T. It follows that
(60)bF(T)=min{B⊆E(T):γF(T-B)>γF(T)}=min{B⊆E(T):γ(T-B)>γ(T)}=b(T)⩽2.Except for these, no results onbF(G) have been known as yet.


## 9.4. Roman Bondage Numbers

ARoman dominating function on a graph G is a labeling f:V→{0,1,2} such that every vertex with label 0 has at least one neighbor with label 2. The weight of a Roman dominating function f on G is the value
(61)f(G)=∑u∈V(G)‍f(u).
The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γRM(G).A Roman dominating functionf:V→{0,1,2} can be represented by the ordered partition (V0,V1,V2) (or (V0f,V1f,V2f) to refer to f) of V, where Vi={v∈V∣f(v)=i}. In this representation, its weight f(G)=|V1|+2|V2|. It is clear that V1f∪V2f is a dominating set of G, called the Roman dominating set, denoted by DRf=(V1,V2). Since V1f∪V2f is a dominating set when f is a Roman dominating function, and since placing weight 2 at the vertices of a dominating set yields a Roman dominating function, in [115], it is observed that
(62)γ(G)⩽γRM(G)⩽2γ(G).
A graph G is called to be Roman if γRM(G)=2γ(G).The definition of the Roman domination function is proposed implicitly by Stewart [116] and ReVelle and Rosing [117]. Roman dominating numbers have been deeply studied. In particular, Bahremandpour  et al. [118] showed that the problem determining the Roman domination number is NP-complete even for bipartite graphs.LetG be a graph with maximum degree at least two. The Roman bondage numberbRM(G) of G is the minimum cardinality of all sets E′⊆E for which γRM(G-E′)>γRM(G). Since in study of Roman bondage number the assumption Δ(G)⩾2 is necessary, we always assume that when we discuss bRM(G), all graphs involved satisfy Δ(G)⩾2. The Roman bondage number bRM(G) is introduced by Jafari Rad and Volkmann in [119].Recently, Bahremandpour  et al. [118] have shown that the problem determining the Roman bondage number is NP-hard even for bipartite graphs.Problem 7.
Consider the decision problem:Roman Bondage ProblemInstance: a nonempty bipartite graphG and a positive integer k.Question: isbRM(G)⩽k?Theorem 152 (Bahremandpour et al. [118], 2013).
The Roman bondage problem is NP-hard even for bipartite graphs.The exact value ofbRM(G) is known only for a few family of graphs including the complete graphs, cycles, and paths.Theorem 153 (Jafari Rad and Volkmann [119], 2011).
For any positive integersn and m with m⩽n,
(63)bRM(Pn)={2,ifn≡2(mod3),1,otherwise,bRM(Cn)={3,ifn=2(mod3),2,otherwise,bRM(Kn)=⌈n2⌉forn⩾3,bRM(Km,n)={1ifm=1andn≠1,4ifm=n=3,motherwise.Lemma 154 (Cockayne et al. [115], 2004).
IfG is a graph of order n and contains vertices of degree n-1, then γRM(G)=2.Using Lemma154, the third conclusion in Theorem 153 can be generalized to more general case, which is similar to Lemma 49.Theorem 155 (Jafari Rad and Volkmann [119], 2011).
LetG be a graph with order n≥3 and t the number of vertices of degree n-1 in G. If t⩾1, then bRM(G)=⌈t/2⌉.Ebadi and PushpaLatha [120] conjectured that bRM(G)⩽n-1 for any graph G of order n⩾3. Dehgardi et al. [121], Akbari and Qajar [122], independently, showed that this conjecture is true.Theorem 156.
b
RM
(
G
)
⩽
n
-
1 for any connected graph G of order n⩾3.For a completet-partite graph, we have the following result.Theorem 157 (Hu and Xu [123], 2011).
LetG=Km1,m2,…,mt be a complete t-partite graph with m1=⋯=mi<mi+1≤⋯⩽mt, t⩾2 and n=∑j=1tmj. Then
(64)bRM(G)={⌈i2⌉ifmi=1andn⩾3,2ifmi=2andi=1,iifmi=2andi⩾2,4ifmi=3andi=t=2,n-1ifmi=3andi=t⩾3,n-mtifmi⩾3andmt⩾4.Consider a completet-partite graph Kt(3) for t⩾3, bRM(Kt(3))=n-1 by Theorem 157, where n=3t, which shows that this upper bound of n-1 on bRM(G) in Theorem 156 is sharp. This fact and γR(Kt(3))=4 give a negative answer to the following two problems posed by Dehgardi et al. [121].Prove or Disprove: for any connected graph G of order n≥3,  (i) bRM(G)=n-1 if and only if G≅K3;  (ii) bRM(G)⩽n-γR(G)+1.Note that a completet-partite graph Kt(3) is (n-3)-regular and bRM(Kt(3))=n-1 for t⩾3, where n=3t. Hu and Xu further determined that bR(G)=n-2 for any (n-3)-regular graph G of order n⩽5 except Kt(3).Theorem 158 (Hu and Xu [123], 2011).
For any (n-3)-regular graph G of order n other than Kt(3), bRM(G)=n-2 for n⩾5.For a treeT with order n⩾3, Ebadi and PushpaLatha [120], and Jafari Rad and Volkmann [119], independently, obtained an upper bound on bRM(T).Theorem 159.
b
RM
(
T
)
⩽
3 for any tree T with order n⩾3.Theorem 160 (Bahremandpour et al. [118], 2013).
b
RM
(
P
2
×
P
n
)
=
2 for n⩾2.Theorem 161 (Jafari Rad and Volkmann [119], 2011).
LetG be a graph with order at least three.(a)
If(x,y,z) is a path of length 2 in G, then bRM(G)⩽dG(x)+dG(y)+dG(z)-3-|NG(x)∩NG(y)|.(b)
IfG is connected, then bRM(G)⩽λ(G)+2Δ(G)-3.Theorem161 (b) implies bRM(G)⩽δ(G)+2Δ(G)-3 for a connected graph G. Note that for a planar graph G, δ(G)⩽5; moreover, δ(G)⩽3 if the girth at least 4, and δ(G)⩽2 if the girth at least 6. These two facts show that bRM(G)⩽2Δ(G)+2 for a connected planar graph G. Jafari Rad and Volkmann [124] improved this bound.Theorem 162 (Jafari Rad and Volkmann [124], 2011).
For any connected planar graphG of order n⩾3 with girth g(G),
(65)bRM(G)⩽{2Δ(G),Δ(G)+6,Δ(G)+5ifGcontainsnoverticesofdegreefive,Δ(G)+4ifg(G)⩾4,Δ(G)+3ifg(G)⩾5,Δ(G)+2ifg(G)⩾6,Δ(G)+1ifg(G)⩾8.According to Theorem157, bRM(Cn)=3=Δ(Cn)+1 for a cycle Cn of length n⩾8 with n≡2(mod3), and therefore the last upper bound in Theorem 162 is sharp, at least for Δ=2.Combining the fact that every planar graphG with minimum degree 5 contains an edge xy with dG(x)=5 and dG(y)∈{5,6} with Theorem 161 (a), Akbari et al. [125] obtained the following result.Theorem 163 (Akbari et al. [125], 2012).
b
RM
(
G
)
⩽
15 for every planar graph G.It remains open to show whether the bound in Theorem163 is sharp or not. Though finding a planar graph G with bRM(G)=15 seems to be difficult, Akbari et al. [125] constructed an infinite family of planar graphs with Roman bondage number equal to 7 by proving the following result.Theorem 164 (Akbari et al. [125], 2012).
LetG be a graph of order n and G^ is the graph of order 5n obtained from G by attaching the central vertex of a copy of a path P5 to each vertex of G (see Figure 9). Then γRM(G^)=4n and bRM(G^)=δ(G)+2.Figure 9
The graphG^ is constructed from G.By Theorem164, infinite many planar graphs with Roman bondage number 7 can be obtained by considering any planar graph G with δ(G)=5 (e.g., the icosahedron graph).Conjecture 165 (Akbari et al. [125], 2012).
The Roman bondage number of every planar graph is at most 7.For general bounds, the following observation is directly obtained, which is similar to Observation1.Observation 4.
LetG be a graph of order n with maximum degree at least two. Assume that H is a spanning subgraph obtained from G by removing k edges. If γRM(H)=γRM(G), then bR(H)⩽bRM(G)⩽bRM(H)+k.Theorem 166 (Bahremandpour et al. [118], 2013).
For any connected graphG of order n, if n⩾3 and γRM(G)=γ(G)+1, then
(66)bRM(G)⩽min{b(G),nΔ},
where nΔ is the number of vertices with maximum degree Δ in G.Observation 5.
For any graphG, if γ(G)=γRM(G), then bRM(G)⩽b(G).Theorem 167 (Bahremandpour et al. [118], 2013).
For every Roman graphG,
(67)bRM(G)⩾b(G).
The bound is sharp for cycles on n vertices where n≡0(mod3).The strict inequality in Theorem167 can hold, for example, b(C3k+2)=2<3=bRM(C3k+2) by Theorem 157.A graphG is called to be vertex Roman domination-critical if γRM(G-x)<γRM(G) for every vertex x in G. If G has no isolated vertices, then γRM(G)⩽2γ(G)⩽2β(G). If γRM(G)=2β(G), then γRM(G)=2γ(G) and hence G is a Roman graph. In [30], Volkmann gave a lot of graphs with γ(G)=β(G). The following result is similar to Theorem 57.Theorem 168 (Bahremandpour et al. [118], 2013).
For any graphG, if γRM(G)=2β(G), then(a)
bRM(G)⩾δ(G);(b)
bRM(G)⩾δ(G)+1 if G is a vertex Roman domination-critical graph.IfγRM(G)=2, then obviously bRM(G)⩽δ(G). So we assume γRM(G)⩾3. Dehgardi et al. [121] proved bRM(G)⩽(γRM(G)-2)Δ(G)+1 and posed the following problem: if G is a connected graph of order n⩾4 with γRM(G)⩾3, then
(68)bRM(G)⩽(γRM(G)-2)Δ(G).Theorem161 (a) shows that the inequality (68) holds if γRM(G)⩾5. Thus, the bound in (68) is of interest only when γRM(G) is 3 or 4.Lemma 169 (Bahremandpour et al. [118], 2013).
For any nonempty graphG of order n⩾3, γRM(G)=3 if and only if Δ(G)=n-2.The following result shows that (68) holds for all graphs G of order n⩾4 with γRM(G)=3 or 4, which improves Theorem 161 (b).Theorem 170 (Bahremandpour et al. [118], 2013).
For any connected graphG of order n⩾4,
(69)bRM(G)≤{Δ(G)=n-2ifγRM(G)=3,Δ(G)+δ(G)-1ifγRM(G)=4
with the first equality if and only if G≅C4.Recently, Akbari and Qajar [122] have proved the following result.Theorem 171 (Akbari and Qajar [122]).
For any connected graphG of order n⩾3,
(70)bRM(G)⩽n-γRM(G)+5.We conclude this section with the following problems.Problem 8.
Characterize all connected graphsG of order n⩾3, for which bRM(G)=n-1.Problem 9.
Prove or disprove: ifG is a connected graph of order n⩾3, then
(71)bRM(G)⩽n-γRM(G)+3.Note thatγR(Kt(3))=4 and bRM(Kt(3))=n-1, where n=3t for t⩾3. The upper bound on bRM(G) given in Problem 9 is sharp if Problem 9 has positive answer.


## 9.5. Rainbow Bondage Numbers

For a positive integerk, a k-rainbow dominating function of a graph G is a function f from the vertex-set V(G) to the set of all subsets of the set {1,2,…,k} such that for any vertex x in G with f(x)=∅ the condition
(72)⋃y∈NG(x)‍f(y)={1,2,…,k}
is fulfilled. The weight of a k-rainbow dominating function f on G is the value
(73)f(G)=∑x∈V(G)‍|f(x)|.
The k-rainbow domination number of a graph G, denoted by γrk(G), is the minimum weight of a k-rainbow dominating function f of G.Note thatγr1(G) is the classical domination number γ(G). The k-rainbow domination number is introduced by Brešar et al. [126]. Rainbow domination of a graph G coincides with ordinary domination of the Cartesian product of G with the complete graph, in particular, γrk(G)=γ(G×Kk) for any positive integer k and any graph G [126]. Hartnell and Rall [127] proved that γ(T)<γr2(T) for any tree T, no graph has γ=γrk for k⩾3, for any k⩾2, and any graph G of order n:
(74)min{n,γ(G)+k-2}⩽γrk(G)⩽kγ(G).The introduction of rainbow domination is motivated by the study of paired domination in Cartesian products of graphs, where certain upper bounds can be expressed in terms of rainbow domination; that is, for any graphG and any graph H, if V(H) can be partitioned into kγP-sets, then γP(G×H)⩽(1/k)υ(H)γrk(G), proved by Brešar et al. [126].Dehgardi et al. [128] introduced the concept of k-rainbow bondage number of graphs. Let G be a graph with maximum degree at least two. The k-rainbow bondage number brk(G) of G is the minimum cardinality of all sets B⊆E(G) for which γrk(G-B)>γrk(G). Since in the study of k-rainbow bondage number the assumption Δ(G)⩾2 is necessary, we always assume that when we discuss brk(G), all graphs involved satisfy Δ(G)⩾2.The2-rainbow bondage number of some special families of graphs has been determined.Theorem 172 (Dehgardi et al. [128]).
For any integern⩾3,
(75)br2(Pn)=1forn⩾2,br2(Cn)={1ifn≡0(mod4),2otherwise,br2(Kn,n)={1ifn=2,3ifn=3,6ifn=4,mifn⩾5.Theorem 173 (Dehgardi et al. [128]).
For any connected graphG of order n⩾3, br2(G)⩽λ(G)+2Δ(G)-3.Theorem 174 (Dehgardi et al. [128]).
For any treeT of order n⩾3, br2(T)⩽2.Theorem 175 (Dehgardi et al. [128]).
IfG is a planar graph with maximum degree at least two, then br2(G)⩽15. Moreover, if the girth g(G)⩾4, then br2(G)⩽11 and if g(G)⩾6, then br2(G)⩽9.Theorem 176 (Dehgardi et al. [128]).
For a complete bipartite graphKp,q, if 2k+1⩽p⩽q, then brk(Kp,q)=p.Theorem 177 (Dehgardi et al. [128]).
For a complete graphKn, if n⩾k+1, then brk(Kn)=⌈kn/(k+1)⌉.The special casek=1 of Theorem 177 can be found in Theorem 1. The following is a simple observation similar to Observation 1.Observation 6 (Dehgardi et al. [128]).
LetG be a graph with maximum degree at least two, H a spanning subgraph obtained from G by removing k edges. If γrk(H)=γrk(G), then brk(H)⩽brk(G)⩽brk(H)+k.Theorem 178 (Dehgardi et al. [128]).
For every graphG with γrk(G)=kγ(G), brk(G)⩾b(G).A graphG is said to be vertexk-rainbow domination-critical if γrk(G-x)<γrk(G) for every vertex x in G. It is clear that if G has no isolated vertices, then γrk(G)⩽kγ(G)⩽kβ(G), where β(G) is the vertex-covering number of G. Thus, if γrk(G)=kβ(G), then γrk(G)=kγ(G).Theorem 179 (Dehgardi et al. [128]).
For any graphG, if γrk(G)=kβ(G), then(a)
brk(G)⩾δ(G);(b)
brk(G)⩾δ(G)+1 if G is vertex k-rainbow domination-critical.As far as we know, there are no more results on thek-rainbow bondage number of graphs in the literature.


## 10. Results on Digraphs

Although domination has been extensively studied in undirected graphs, it is natural to think of a dominating set as a one-way relationship between vertices of the graph. Indeed, among the earliest literatures on this subject, von Neumann and Morgenstern [129] used what is now called domination in digraphs to find solution (or kernels, which are independent dominating sets) for cooperative n-person games. Most likely, the first formulation of domination by Berge [130], in 1958, was given in the context of digraphs and, only some years latter by Ore [131], in 1962, for undirected graphs. Despite this history, examination of domination and its variants in digraphs has been essentially overlooked (see [4] for an overview of the domination literature). Thus, there are few, if any, such results on domination for digraphs in the literature.The bondage number and its related topics for undirected graph have become one of major areas both in theoretical and applied researches. However, until recently, Carlson and Develin [42], Shan and Kang [132], and Huang and Xu [133, 134] studied the bondage number for digraphs, independently. In this section, we introduce their results for general digraphs. Results for some special digraphs such as vertex-transitive digraphs are introduced in the next section.


### 10.1. Upper Bounds for General Digraphs

LetG=(V,E) be a digraph without loops and parallel edges. A digraph G is called to be asymmetric if whenever (x,y)∈E(G) then (y,x)∉E(G) and to be symmetric if (x,y)∈E(G) implies (y,x)∈E(G). For a vertex x of V(G), the sets of out-neighbors and in-neighbors of x are, respectively, defined as NG+(x)={y∈V(G):(x,y)∈E(G)} and NG-(x)={x∈V(G):(x,y)∈E(G)}, the out-degree and the in-degree of x are, respectively, defined as dG+(x)=|NG+(x)| and dG-(x)=|NG+(x)|. Denote the maximum and the minimum out-degree (resp., in-degree) of G by Δ+(G) and δ+(G) (resp., Δ-(G) and δ-(G)). The degree dG(x) of x is defined as dG+(x)+dG-(x), and the maximum and the minimum degrees of G are denoted by Δ(G) and δ(G), respectively; that is, Δ(G)=max{dG(x):x∈V(G)} and δ(G)=min{dG(x):x∈V(G)}. Note that the definitions here are different from the ones in the textbook on digraphs; see for example, Xu [1].A subsetS of V(G) is called a dominating set if V(G)=S∪NG+(S), where NG+(S) is the set of out-neighbors of S. Then, just as for undirected graphs, γ(G) is the minimum cardinality of a dominating set, and the bondage numberb(G) is the smallest cardinality of a set B of edges such that γ(G-B)>γ(G) if such a subset B⊆E(G) exists. Otherwise, we put b(G)=∞.Some basic results for undirected graphs stated in Section3 can be generalized to digraphs. For example, Theorem 18 is generalized by Carlson and Develin [42], Huang and Xu [133], and Shan and Kang [132], independently, as follows.Theorem 180.
LetG be a digraph and (x,y)∈E(G). Then b(G)⩽dG(y)+dG-(x)-|NG-(x)∩NG-(y)|.Corollary 181.
For a digraphG, b(G)⩽δ-(G)+Δ(G).Sinceδ-(G)⩽(1/2)Δ(G), from Corollary 181, Conjecture 53 is valid for digraphs.Corollary 182.
For a digraphG, b(G)⩽(3/2)Δ(G).In the case of undirected graphs, the bondage number ofGn=Kn×Kn achieves this bound. However, it was shown by Carlson and Develin in [42] that if we take the symmetric digraph Gn, we have Δ(Gn)=4(n-1), γ(Gn)=n, and b(Gn)⩽4(n-1)+1=Δ(Gn)+1. So this family of digraphs cannot show that the bound in Corollary 182 is tight.Corresponding to Conjecture51, which is discredited for undirected graphs and is valid for digraphs, the same conjecture for digraphs can be proposed as follows.Conjecture 183 (Carlson and Develin [42], 2006).
b
(
G
)
⩽
Δ
(
G
)
+
1 for any digraph G.If Conjecture183 is true, then the following results shows that this upper bound is tight since b(Kn×Kn)=Δ(Kn×Kn)+1 for a complete digraph Kn.In 2007, Shan and Kang [132] gave some tight upper bounds on the bondage numbers for some asymmetric digraphs. For example, b(T)⩽Δ(T) for any asymmetric directed tree  T; b(G)⩽Δ(G) for any asymmetric digraph G with order at least 4 and γ(G)⩽2. For planar digraphs, they obtained the following results.Theorem 184 (Shan and Kang [132], 2007).
LetG be a asymmetric planar digraph. Then b(G)⩽Δ(G)+2; and b(G)⩽Δ(G)+1 if Δ(G)⩾5 and dG-(x)⩾3 for every vertex x with dG(x)⩾4.


### 10.2. Results for Some Special Digraphs

The exact values and bounds onb(G) for some standard digraphs are determined.Theorem 185 (Huang and Xu [133], 2006).
For a directed cycleCn and a directed path Pn,
(76)b(Cn)={3ifnisodd,2ifniseven,b(Pn)={2ifnisodd,1ifniseven.
For the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n),
(77)b(B(d,n))=difnisodd,d⩽b(B(d,n))⩽2difniseven,b(K(d,n))=d+1.Like undirected graphs, we can define the total domination number and the total bondage number. On the total bondage numbers for some special digraphs, the known results are as follows.Theorem 186 (Huang and Xu [134], 2007).
For a directed cycleCn and a directed path Pn, bT(Pn) and bT(Cn) all do not exist. For a complete digraph Kn,
(78)bT(Kn)=∞ifn=1,2,bT(Kn)=3ifn=3,n⩽bT(Kn)⩽2n-3ifn⩾4.The extended de Bruijn digraphEB(d,n;q1,…,qp) and the extended Kautz digraph EK(d,n;q1,…,qp) are introduced by Shibata and Gonda [135]. If p=1, then they are the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n), respectively. Huang and Xu [134] determined their total domination numbers. In particular, their total bondage numbers for general cases are determined as follows.Theorem 187 (Huang and Xu [134], 2007).
Ifd⩾2 and qi⩾2 for each i=1,2,…,p, then
(79)bT(EB(d,n;q1,…,qp))=dp-1,bT(EK(d,n;q1,…,qp))=dp.
In particular, for the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n),
(80)bT(B(d,n))=d-1,bT(K(d,n))=d.Zhang  et al. [136] determined the bondage number in complete t-partite digraphs.Theorem 188 (Zhang et al. [136], 2009).
For a completet-partite digraph Kn1,n2,…,nt, where n1⩽n2⩽⋯⩽nt,
(81)b(Kn1,n2,…,nt)={mifnm=1,nm+1⩾2forsome,m(1⩽m<t)4t-3ifn1=n2=⋯=nt=2,∑i=1t-1‍ni+2(t-1)otherwise.Since an undirected graph can be thought of as a symmetric digraph, any result for digraphs has an analogy for undirected graphs in general. In view of this point, studying the bondage number for digraphs is more significant than for undirected graphs. Thus, we should further study the bondage number of digraphs and try to generalize known results on the bondage number and related variants for undirected graphs to digraphs, prove or disprove Conjecture183. In particular, determine the exact values of b(B(d,n)) for an even n and bT(Kn) for n⩾4.


## 10.1. Upper Bounds for General Digraphs

LetG=(V,E) be a digraph without loops and parallel edges. A digraph G is called to be asymmetric if whenever (x,y)∈E(G) then (y,x)∉E(G) and to be symmetric if (x,y)∈E(G) implies (y,x)∈E(G). For a vertex x of V(G), the sets of out-neighbors and in-neighbors of x are, respectively, defined as NG+(x)={y∈V(G):(x,y)∈E(G)} and NG-(x)={x∈V(G):(x,y)∈E(G)}, the out-degree and the in-degree of x are, respectively, defined as dG+(x)=|NG+(x)| and dG-(x)=|NG+(x)|. Denote the maximum and the minimum out-degree (resp., in-degree) of G by Δ+(G) and δ+(G) (resp., Δ-(G) and δ-(G)). The degree dG(x) of x is defined as dG+(x)+dG-(x), and the maximum and the minimum degrees of G are denoted by Δ(G) and δ(G), respectively; that is, Δ(G)=max{dG(x):x∈V(G)} and δ(G)=min{dG(x):x∈V(G)}. Note that the definitions here are different from the ones in the textbook on digraphs; see for example, Xu [1].A subsetS of V(G) is called a dominating set if V(G)=S∪NG+(S), where NG+(S) is the set of out-neighbors of S. Then, just as for undirected graphs, γ(G) is the minimum cardinality of a dominating set, and the bondage numberb(G) is the smallest cardinality of a set B of edges such that γ(G-B)>γ(G) if such a subset B⊆E(G) exists. Otherwise, we put b(G)=∞.Some basic results for undirected graphs stated in Section3 can be generalized to digraphs. For example, Theorem 18 is generalized by Carlson and Develin [42], Huang and Xu [133], and Shan and Kang [132], independently, as follows.Theorem 180.
LetG be a digraph and (x,y)∈E(G). Then b(G)⩽dG(y)+dG-(x)-|NG-(x)∩NG-(y)|.Corollary 181.
For a digraphG, b(G)⩽δ-(G)+Δ(G).Sinceδ-(G)⩽(1/2)Δ(G), from Corollary 181, Conjecture 53 is valid for digraphs.Corollary 182.
For a digraphG, b(G)⩽(3/2)Δ(G).In the case of undirected graphs, the bondage number ofGn=Kn×Kn achieves this bound. However, it was shown by Carlson and Develin in [42] that if we take the symmetric digraph Gn, we have Δ(Gn)=4(n-1), γ(Gn)=n, and b(Gn)⩽4(n-1)+1=Δ(Gn)+1. So this family of digraphs cannot show that the bound in Corollary 182 is tight.Corresponding to Conjecture51, which is discredited for undirected graphs and is valid for digraphs, the same conjecture for digraphs can be proposed as follows.Conjecture 183 (Carlson and Develin [42], 2006).
b
(
G
)
⩽
Δ
(
G
)
+
1 for any digraph G.If Conjecture183 is true, then the following results shows that this upper bound is tight since b(Kn×Kn)=Δ(Kn×Kn)+1 for a complete digraph Kn.In 2007, Shan and Kang [132] gave some tight upper bounds on the bondage numbers for some asymmetric digraphs. For example, b(T)⩽Δ(T) for any asymmetric directed tree  T; b(G)⩽Δ(G) for any asymmetric digraph G with order at least 4 and γ(G)⩽2. For planar digraphs, they obtained the following results.Theorem 184 (Shan and Kang [132], 2007).
LetG be a asymmetric planar digraph. Then b(G)⩽Δ(G)+2; and b(G)⩽Δ(G)+1 if Δ(G)⩾5 and dG-(x)⩾3 for every vertex x with dG(x)⩾4.


## 10.2. Results for Some Special Digraphs

The exact values and bounds onb(G) for some standard digraphs are determined.Theorem 185 (Huang and Xu [133], 2006).
For a directed cycleCn and a directed path Pn,
(76)b(Cn)={3ifnisodd,2ifniseven,b(Pn)={2ifnisodd,1ifniseven.
For the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n),
(77)b(B(d,n))=difnisodd,d⩽b(B(d,n))⩽2difniseven,b(K(d,n))=d+1.Like undirected graphs, we can define the total domination number and the total bondage number. On the total bondage numbers for some special digraphs, the known results are as follows.Theorem 186 (Huang and Xu [134], 2007).
For a directed cycleCn and a directed path Pn, bT(Pn) and bT(Cn) all do not exist. For a complete digraph Kn,
(78)bT(Kn)=∞ifn=1,2,bT(Kn)=3ifn=3,n⩽bT(Kn)⩽2n-3ifn⩾4.The extended de Bruijn digraphEB(d,n;q1,…,qp) and the extended Kautz digraph EK(d,n;q1,…,qp) are introduced by Shibata and Gonda [135]. If p=1, then they are the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n), respectively. Huang and Xu [134] determined their total domination numbers. In particular, their total bondage numbers for general cases are determined as follows.Theorem 187 (Huang and Xu [134], 2007).
Ifd⩾2 and qi⩾2 for each i=1,2,…,p, then
(79)bT(EB(d,n;q1,…,qp))=dp-1,bT(EK(d,n;q1,…,qp))=dp.
In particular, for the de Bruijn digraph B(d,n) and the Kautz digraph K(d,n),
(80)bT(B(d,n))=d-1,bT(K(d,n))=d.Zhang  et al. [136] determined the bondage number in complete t-partite digraphs.Theorem 188 (Zhang et al. [136], 2009).
For a completet-partite digraph Kn1,n2,…,nt, where n1⩽n2⩽⋯⩽nt,
(81)b(Kn1,n2,…,nt)={mifnm=1,nm+1⩾2forsome,m(1⩽m<t)4t-3ifn1=n2=⋯=nt=2,∑i=1t-1‍ni+2(t-1)otherwise.Since an undirected graph can be thought of as a symmetric digraph, any result for digraphs has an analogy for undirected graphs in general. In view of this point, studying the bondage number for digraphs is more significant than for undirected graphs. Thus, we should further study the bondage number of digraphs and try to generalize known results on the bondage number and related variants for undirected graphs to digraphs, prove or disprove Conjecture183. In particular, determine the exact values of b(B(d,n)) for an even n and bT(Kn) for n⩾4.


## 11. Efficient Dominating Sets

A dominating setS of a graph G is called to be efficient if for every vertex x in G, |NG[x]∩S|=1 if G is a undirected graph or |NG-[x]∩S|=1 if G is a directed graph. The concept of an efficient set was proposed by Bange  et al. [137] in 1988. In the literature, an efficient set is also called a perfect dominating set (see Livingston and Stout [138] for an explanation).From definition, ifS is an efficient dominating set of a graph G, then S is certainly an independent set and every vertex not in S is adjacent to exactly one vertex in S.It is also clear from definition that a dominating setS is efficient if and only if 𝒩G[S]={NG[x]:x∈S} for the undirected graph G or 𝒩G+[S]={NG+[x]:x∈S} for the digraph G is a partition of V(G), where the induced subgraph by NG[x] or NG+[x] is a star or an out-star with the root x.The efficient domination has important applications in many areas, such as error-correcting codes, and receives much attention in the late years.The concept of efficient dominating sets is a measure of the efficiency of domination in graphs. Unfortunately, as shown in [137], not every graph has an efficient dominating set and, moreover, it is an NP-complete problem to determine whether a given graph has an efficient dominating set. In addition, it was shown by Clark [139] in 1993 that for a wide range of p, almost every random undirected graph G∈𝒢(υ,p) has no efficient dominating sets. This means that undirected graphs possessing an efficient dominating set are rare. However, it is easy to show that every undirected graph has an orientation with an efficient dominating set (see Bange  et al. [140]).In 1993, Barkauskas and Host [141] showed that determining whether an arbitrary oriented graph has an efficient dominating set is NP-complete. Even so, the existence of efficient dominating sets for some special classes of graphs has been examined; see, for example, Dejter and Serra [142] and Lee [143] for Cayley graph, Gu et al. [144] for meshes and tori, Obradović  et al. [145], Huang and Xu [36], Reji Kumar and MacGillivray [146] for circulant graphs, Harary graphs and tori, and Van Wieren  et al. [147] for cube-connected cycles.In this section, we introduce results of the bondage number for some graphs with efficient dominating sets, due to Huang and Xu [36].


### 11.1. Results for General Graphs

In this subsection, we introduce some results on bondage numbers obtained by applying efficient dominating sets. We first state the two following lemmas.Lemma 189.
For anyk-regular graph or digraph G of order n, γ(G)⩾n/(k+1), with equality if and only if G has an efficient dominating set. In addition, if G has an efficient dominating set, then every efficient dominating set is certainly a γ-set, and vice versa.Lete be an edge and S a dominating set in G. We say that esupportsS if e∈(S,S-), where (S,S-)={(x,y)∈E(G):x∈S,y∈S-}. Denote by s(G) the minimum number of edges which support all γ-sets in G.Lemma 190.
For any graph or digraphG, b(G)⩾s(G), with equality if G is regular and has an efficient dominating set.A graphG is called to be vertex-transitive if its automorphism group Aut(G) acts transitively on its vertex-set V(G). A vertex-transitive graph is regular. Applying Lemmas 189 and 190, Huang and Xu obtained some results on bondage numbers for vertex-transitive graphs or digraphs.Theorem 191 (Huang and Xu [36], 2008).
For any vertex-transitive graph or digraphG of order n,
(82)b(G)⩾{⌈n2γ(G)⌉ifGisundirected,⌈nγ(G)⌉ifGisdirected.Theorem 192 (Huang and Xu [36], 2008).
LetG be a k-regular graph of order n. Thenb(G)⩽k if G is undirected and n⩾γ(G)(k+1)-k+1;b(G)⩽k+1+ℓ if G is directed and n⩾γ(G)(k+1)-ℓ with 0⩽ℓ⩽k-1.Next, we introduce a better upper bound onb(G). To this aim, we need the following concept, which is a generalization of the concept of the edge-covering of a graph G. For V′⊆V(G) and E′⊆E(G), we say that E′covers V′ and call E′ an edge-covering for V′ if there exists an edge (x,y)∈E′ for any vertex x∈V′. For y∈V(G), let β′[y] be the minimum cardinality over all edge-coverings for NG-[y].Theorem 193 (Huang and Xu [36], 2008).
IfG is a k-regular graph with order γ(G)(k+1), then b(G)⩽β′[y] for any y∈V(G).The upper bound onb(G) given in Theorem 193 is tight in view of b(Cn) for a cycle or a directed cycle Cn (see Theorems 1 and 185, resp.).It is easy to see that for ak-regular graph G, ⌈(k+1)/2⌉⩽β′[y]⩽k when G is undirected and β′[y]=k+1 when G is directed. By this fact and Lemma 189, the following theorem is merely a simple combination of Theorems 191 and 193.Theorem 194 (Huang and Xu [36], 2008).
LetG be a vertex-transitive graph of degree k. If G has an efficient dominating set, then
(83)⌈k+12⌉⩽b(G)⩽kifGisundirected,b(G)=k+1ifGisdirected.Theorem 195 (Huang and Xu [36], 2008).
IfG is an undirected vertex-transitive cubic graph with order 4γ(G) and girth g(G)⩽5, then b(G)=2.The proof of Theorem195 leads to a byproduct. If g=5, let (u1,u2,u3,u4,u5) be a cycle, and let 𝒟i be the family of efficient dominating sets containing ui for each i∈{1,2,3,4,5}. Then 𝒟i∩𝒟j=∅ for i=1,2,…,5. Then G has at least 5s efficient dominating sets, where s=s(G). But there are only 4s (=ns/γ) distinct efficient dominating sets in G. This contradiction implies that an undirected vertex-transitive cubic graph with girth five has no efficient dominating sets. But a similar argument for g(G)=3,4 or g(G)⩾6 could not give any contradiction. This is consistent with the result that CCC(n), a vertex-transitive cubic graph with girth n if 3⩽n⩽8, or girth 8 if n⩾9, has efficient dominating sets for all n⩾3 except n=5 (see Theorem 199 in the following subsection).


### 11.2. Results for Cayley Graphs

In this subsection, we use Theorem194 to determine the exact values or approximative values of bondage numbers for some special vertex-transitive graphs by characterizing the existence of efficient dominating sets in these graphs.LetΓ be a nontrivial finite group, S a nonempty subset of Γ without the identity element of Γ. A digraph G is defined as follows:
(84)V(G)=Γ,(x,y)∈E(G)⟺x-1y∈Sforanyx,y∈Γ
is called a Cayley digraph of the group Γ with respect to S, denoted by CΓ(S). If S-1={s-1:s∈S}=S; then CΓ(S) is symmetric and is called a Cayley undirected graph, a Cayley graph for short. Cayley graphs or digraphs are certainly vertex-transitive (see Xu [1]).A circulant graphG(n;S) of order n is a Cayley graph CZn(S), where Zn={0,…,n-1} is the addition group of order n and S is a nonempty subset of Zn without the identity element and, hence, is a vertex-transitive digraph of degree |S|. If S-1=S, then G(n;S) is an undirected graph. If S={1,k}, where 2⩽k⩽n-2, we write G(n;1,k) for G(n;{1,k}) or G(n;{±1,±k}) and call it a double-loop circulant graph.Huang and Xu [36] showed that, for directed G=G(n;1,k), ⌈n/3⌉⩽γ(G)⩽⌈n/2⌉ and G has an efficient dominating set if and only if 3∣n and k≡2(mod3); for directed G=G(n;1,k) and k≠n/2, ⌈n/5⌉⩽γ(G)⩽⌈n/3⌉ and G has an efficient dominating set if and only if 5∣n and k≡±2(mod5). By Theorem 194, we obtain the bondage number of a double loop circulant graph if it has an efficient dominating set.Theorem 196 (Huang and Xu [36], 2008).
LetG be a double-loop circulant graph G(n;1,k). If G is directed with 3∣n and k≡2(mod3), or G is undirected with 5∣n and k≡±2(mod5), then b(G)=3.Them×n torus is the Cartesian product Cm×Cn of two cycles and is a Cayley graph CZm×Zn(S), where S={(0,1),(1,0)} for directed cycles and S={(0,±1),(±1,0)} for undirected cycles and, hence, is vertex-transitive. Gu  et al. [144] showed that the undirected torus Cm×Cn has an efficient dominating set if and only if both m and n are multiples of 5. Huang and Xu [36] showed that the directed torus Cm×Cn has an efficient dominating set if and only if both m and n are multiples of 3. Moreover, they found a necessary condition for a dominating set containing the vertex (0,0) in Cm×Cn to be efficient and obtained the following result.Theorem 197 (Huang and Xu [36], 2008).
LetG=Cm×Cn. If G is undirected and both m and n are multiples of 5 or if G is directed and both m and n are multiples of 3, then b(G)=3.The hypercubeQn is the Cayley graph CΓ(S), where Γ=Z2×⋯×Z2=(Z2)n and S={100⋯0,010⋯0,…,00⋯01}. Lee [143] showed that Qn has an efficient dominating set if and only if n=2m-1 for a positive integer m. By Theorem 194, the following result is obtained immediately.Theorem 198 (Huang and Xu [36], 2008).
Ifn=2m-1 for a positive integer m, then 2m-1⩽b(Qn)⩽2m-1.Problem 10.
Determine the exact value ofb(Qn) for n=2m-1.Then-dimensional cube-connected cycle, denoted by CCC(n), is constructed from the n-dimensional hypercube Qn by replacing each vertex x in Qn with an undirected cycle Cn of length n and linking the ith vertex of the Cn to the ith neighbor of x. It has been proved that CCC(n) is a Cayley graph and, hence, is a vertex-transitive graph with degree 3. Van Wieren  et al. [147] proved that CCC(n) has an efficient dominating set if and only if n≠5. From Theorems 194 and 195, the following result can be derived.Theorem 199 (Huang and Xu [36], 2008).
LetG=CCC(n) be the n-dimensional cube-connected cycles with n⩾3 and n≠5. Then γ(G)=n2n-2 and 2⩽b(G)⩽3. In addition, b(CCC(3))=b(CCC(4))=2.Problem 11.
Determine the exact value ofb(CCC(n)) for n⩾5.


## 11.1. Results for General Graphs

In this subsection, we introduce some results on bondage numbers obtained by applying efficient dominating sets. We first state the two following lemmas.Lemma 189.
For anyk-regular graph or digraph G of order n, γ(G)⩾n/(k+1), with equality if and only if G has an efficient dominating set. In addition, if G has an efficient dominating set, then every efficient dominating set is certainly a γ-set, and vice versa.Lete be an edge and S a dominating set in G. We say that esupportsS if e∈(S,S-), where (S,S-)={(x,y)∈E(G):x∈S,y∈S-}. Denote by s(G) the minimum number of edges which support all γ-sets in G.Lemma 190.
For any graph or digraphG, b(G)⩾s(G), with equality if G is regular and has an efficient dominating set.A graphG is called to be vertex-transitive if its automorphism group Aut(G) acts transitively on its vertex-set V(G). A vertex-transitive graph is regular. Applying Lemmas 189 and 190, Huang and Xu obtained some results on bondage numbers for vertex-transitive graphs or digraphs.Theorem 191 (Huang and Xu [36], 2008).
For any vertex-transitive graph or digraphG of order n,
(82)b(G)⩾{⌈n2γ(G)⌉ifGisundirected,⌈nγ(G)⌉ifGisdirected.Theorem 192 (Huang and Xu [36], 2008).
LetG be a k-regular graph of order n. Thenb(G)⩽k if G is undirected and n⩾γ(G)(k+1)-k+1;b(G)⩽k+1+ℓ if G is directed and n⩾γ(G)(k+1)-ℓ with 0⩽ℓ⩽k-1.Next, we introduce a better upper bound onb(G). To this aim, we need the following concept, which is a generalization of the concept of the edge-covering of a graph G. For V′⊆V(G) and E′⊆E(G), we say that E′covers V′ and call E′ an edge-covering for V′ if there exists an edge (x,y)∈E′ for any vertex x∈V′. For y∈V(G), let β′[y] be the minimum cardinality over all edge-coverings for NG-[y].Theorem 193 (Huang and Xu [36], 2008).
IfG is a k-regular graph with order γ(G)(k+1), then b(G)⩽β′[y] for any y∈V(G).The upper bound onb(G) given in Theorem 193 is tight in view of b(Cn) for a cycle or a directed cycle Cn (see Theorems 1 and 185, resp.).It is easy to see that for ak-regular graph G, ⌈(k+1)/2⌉⩽β′[y]⩽k when G is undirected and β′[y]=k+1 when G is directed. By this fact and Lemma 189, the following theorem is merely a simple combination of Theorems 191 and 193.Theorem 194 (Huang and Xu [36], 2008).
LetG be a vertex-transitive graph of degree k. If G has an efficient dominating set, then
(83)⌈k+12⌉⩽b(G)⩽kifGisundirected,b(G)=k+1ifGisdirected.Theorem 195 (Huang and Xu [36], 2008).
IfG is an undirected vertex-transitive cubic graph with order 4γ(G) and girth g(G)⩽5, then b(G)=2.The proof of Theorem195 leads to a byproduct. If g=5, let (u1,u2,u3,u4,u5) be a cycle, and let 𝒟i be the family of efficient dominating sets containing ui for each i∈{1,2,3,4,5}. Then 𝒟i∩𝒟j=∅ for i=1,2,…,5. Then G has at least 5s efficient dominating sets, where s=s(G). But there are only 4s (=ns/γ) distinct efficient dominating sets in G. This contradiction implies that an undirected vertex-transitive cubic graph with girth five has no efficient dominating sets. But a similar argument for g(G)=3,4 or g(G)⩾6 could not give any contradiction. This is consistent with the result that CCC(n), a vertex-transitive cubic graph with girth n if 3⩽n⩽8, or girth 8 if n⩾9, has efficient dominating sets for all n⩾3 except n=5 (see Theorem 199 in the following subsection).


## 11.2. Results for Cayley Graphs

In this subsection, we use Theorem194 to determine the exact values or approximative values of bondage numbers for some special vertex-transitive graphs by characterizing the existence of efficient dominating sets in these graphs.LetΓ be a nontrivial finite group, S a nonempty subset of Γ without the identity element of Γ. A digraph G is defined as follows:
(84)V(G)=Γ,(x,y)∈E(G)⟺x-1y∈Sforanyx,y∈Γ
is called a Cayley digraph of the group Γ with respect to S, denoted by CΓ(S). If S-1={s-1:s∈S}=S; then CΓ(S) is symmetric and is called a Cayley undirected graph, a Cayley graph for short. Cayley graphs or digraphs are certainly vertex-transitive (see Xu [1]).A circulant graphG(n;S) of order n is a Cayley graph CZn(S), where Zn={0,…,n-1} is the addition group of order n and S is a nonempty subset of Zn without the identity element and, hence, is a vertex-transitive digraph of degree |S|. If S-1=S, then G(n;S) is an undirected graph. If S={1,k}, where 2⩽k⩽n-2, we write G(n;1,k) for G(n;{1,k}) or G(n;{±1,±k}) and call it a double-loop circulant graph.Huang and Xu [36] showed that, for directed G=G(n;1,k), ⌈n/3⌉⩽γ(G)⩽⌈n/2⌉ and G has an efficient dominating set if and only if 3∣n and k≡2(mod3); for directed G=G(n;1,k) and k≠n/2, ⌈n/5⌉⩽γ(G)⩽⌈n/3⌉ and G has an efficient dominating set if and only if 5∣n and k≡±2(mod5). By Theorem 194, we obtain the bondage number of a double loop circulant graph if it has an efficient dominating set.Theorem 196 (Huang and Xu [36], 2008).
LetG be a double-loop circulant graph G(n;1,k). If G is directed with 3∣n and k≡2(mod3), or G is undirected with 5∣n and k≡±2(mod5), then b(G)=3.Them×n torus is the Cartesian product Cm×Cn of two cycles and is a Cayley graph CZm×Zn(S), where S={(0,1),(1,0)} for directed cycles and S={(0,±1),(±1,0)} for undirected cycles and, hence, is vertex-transitive. Gu  et al. [144] showed that the undirected torus Cm×Cn has an efficient dominating set if and only if both m and n are multiples of 5. Huang and Xu [36] showed that the directed torus Cm×Cn has an efficient dominating set if and only if both m and n are multiples of 3. Moreover, they found a necessary condition for a dominating set containing the vertex (0,0) in Cm×Cn to be efficient and obtained the following result.Theorem 197 (Huang and Xu [36], 2008).
LetG=Cm×Cn. If G is undirected and both m and n are multiples of 5 or if G is directed and both m and n are multiples of 3, then b(G)=3.The hypercubeQn is the Cayley graph CΓ(S), where Γ=Z2×⋯×Z2=(Z2)n and S={100⋯0,010⋯0,…,00⋯01}. Lee [143] showed that Qn has an efficient dominating set if and only if n=2m-1 for a positive integer m. By Theorem 194, the following result is obtained immediately.Theorem 198 (Huang and Xu [36], 2008).
Ifn=2m-1 for a positive integer m, then 2m-1⩽b(Qn)⩽2m-1.Problem 10.
Determine the exact value ofb(Qn) for n=2m-1.Then-dimensional cube-connected cycle, denoted by CCC(n), is constructed from the n-dimensional hypercube Qn by replacing each vertex x in Qn with an undirected cycle Cn of length n and linking the ith vertex of the Cn to the ith neighbor of x. It has been proved that CCC(n) is a Cayley graph and, hence, is a vertex-transitive graph with degree 3. Van Wieren  et al. [147] proved that CCC(n) has an efficient dominating set if and only if n≠5. From Theorems 194 and 195, the following result can be derived.Theorem 199 (Huang and Xu [36], 2008).
LetG=CCC(n) be the n-dimensional cube-connected cycles with n⩾3 and n≠5. Then γ(G)=n2n-2 and 2⩽b(G)⩽3. In addition, b(CCC(3))=b(CCC(4))=2.Problem 11.
Determine the exact value ofb(CCC(n)) for n⩾5.



---

*Source: 595210-2013-05-13.xml*