The Bondage Numbers and Efcient Dominations of
Vertex-Transitive Graphs


Jia Huang and Jun-Ming
Department of Mathematics, University of Science and Technology of China, Anhui 230026, P. R. China


Abstract     Full Text  PDF

The bondage number of a graph $G$ is the minimum number of edges whose removal results in a graph with larger domination number. A dominating set $D$ is called an efficient dominating set of $G$ if $|N^{+}[v]\bigcap D| = 1$ for every vertex $v\in V (G)$. In this paper we establish a tight lower bound for the bondage number of a vertex-transitive graph. We also obtain upper bounds by investigating the relation between the bondage number and the efficient domination. As applications, we determine the bondage number for some circulant graphs and tori by characterizing existence of efficient dominating sets in these graphs.