Efficient bondage number of a graph

Abstract

A set S of vertices in G is an efficient dominating set, if every vertex u in V-S is adjacent to exactly one vertex in S. The efficient domination number v(e) (G) of G is the minimum number of vertices inan efficient dominating set of G. In general, v(e) (G) can be made to increase by removal of edges from G. Our main objective is to study this phenomenon. Let E be a set of edges of G such that v(e) (G-E) >v(e) (G). Then we define the efficient bondage number b(e) (G) of G to be the minimum number of edges in E. In this communication, an upper bound for b(e) (G) has been established and its exact values for some classes of graphs have been found. In addition, Nordhaus-Goddum type results are established.