Minimum Neighborhood Domination of Split Graph of Graphs

Abstract

Let be a non-trivial simple graph. A dominating set in a graph is a set of vertices such that every vertex not in the set is adjacent to at least one vertex in the set. A subset is a minimum neighborhood dominating set if is a dominating set and if for every holds. The minimum cardinality of the minimum neighborhood dominating set of a graph is called as minimum neighborhood dominating number and it is denoted by . A minimum neighborhood dominating set is a dominating set where the intersection of the neighborhoods of all vertices in the set is as small as possible, (i.e., ). The minimum neighborhood dominating number, denoted by , is the minimum cardinality of a minimum neighborhood dominating set. In other words, it is the smallest number of vertices needed to form a minimum neighborhood-dominating set. The concept of minimum neighborhood dominating set is related to the study of the structure and properties of graphs and is used in various fields such as computer science, operations research, and network design. A minimum neighborhood dominating set is also useful in the study of graph theory and has applications in areas such as network design and control theory. This concept is a variation of the traditional dominating set problem and adds an extra constraint on the intersection of the neighborhoods of the vertices in the set. It is also an NP-hard problem. The main aim of this paper is to study the minimum neighborhood domination number of the split graph of some of the graphs.

Keywords

• Dominating set, Domination number, Minimum neighborhood dominating set, Minimum neighborhood dominating number, Split graph