%0 Journal Article
%T On Bondage Numbers of Graphs: A Survey with Some Comments
%A Jun-Ming Xu
%J International Journal of Combinatorics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/595210
%X The domination number of a graph is the smallest number of vertices which dominate all remaining vertices by edges of . The bondage number of a nonempty graph is the smallest number of edges whose removal from results in a graph with domination number greater than the domination number of . 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. 1. Introduction For terminology and notation on graph theory not given here, the reader is referred to Xu [1]. Let be a finite, undirected, and simple graph. We call and the order and size of and denote them by and , respectively, unless otherwise specified. Through this paper, the notations , , and always denote a path, a cycle, and a complete graph of order , respectively, the notation denotes a complete -partite graph with and , with , and is a star. For two vertices and in a connected graph , we use to denote the distance between and in . For a vertex in , let be the open set of neighbors of and the closed set of neighbors of . For a subset , , and , where . Let be the set of edges incident with in ; that is, . We denote the degree of by . The maximum and the minimum degrees of are denoted by and , 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 subset is called a dominating set of if ; that is, every vertex in has at least one neighbor in . The domination number of , denoted by , is the minimum cardinality among all dominating sets; that is, A dominating set is called a -set of if . 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
%U http://www.hindawi.com/journals/ijcom/2013/595210/