Bondage Number of A Non - Split Perfect Domin...

Bondage Number of A Non - Split Perfect Dominating Set Extended To Directed Graphs Towards In & Out Degree Using Interval Graphs

Author Name : Dr. A. Sudhakaraiah, K. Mahaboob Basha, E. Gnana Deepika

ABSTRACT

The research of the domination in graphs has been an evergreen of the graph theory. Its basic concept is the dominating set and the domination number. The   theory of domination in graphs was introduced by O. Ore [1] and C. Berge [2].        A survey on results and applications of dominating sets was presented by E.J. Cockayane and S.T. Hedetniemi [3]. Among the various applications of the theory of perfect domination [4], the most often discussed is communication network. There has been persistent in the algorithmic aspects of interval graphs in past decades spurred much by their numerous applications of interval graphs corresponding to interval families.

Non - split domination in graphs was introduced by V.R. Kulli [5] in 1997. They have studied these parameters for various standard graphs and obtained the bounds for them. The concept of restrained domination was introduced by J.A. Telle and A. Proskurowski [6], albeit indirectly, as a vertex partitioning problem. One application of domination is that of prisoners and guards. For security, each prisoner must be seen by some guard; the concept is that of domination. However, in order to protect the rights of prisoners, we may also require that each prisoner is seen by another prisoner; the concept is that of restrained domination.

The bondage number of a non-empty graph G is the minimum cardinality among all sets of edges , for which . Here indicates the domination number of G. The domination number of G is the minimum cardinality of a dominating set. Also a minimum dominating set in the graph corresponds to a smallest set of sites selected in the network for some particular uses such as placing transmitters.

The concept of the bondage number was proposed for an undirected graph by J.F. Fink et al. and for a digraph by K. Carlson and M. Develin. There are many research articles on the bondage number for undirected graphs.

In this paper, we consider the bondage number for a non split perfect dominating set, which is defined as the minimum number of edges whose removal results in a new graph with larger domination number. By constructing a family of minimum dominating sets, we compute the bondage number as .

KEY WORDS : Interval graph, Dominating set, Perfect dominating set, Non-split perfect dominating set, Bondage number, In degree, Out degree.