Minimum Neighborhood Domination of Split Graph of Graphs

Main Article Content



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.


Download data is not yet available.

Article Details

How to Cite
W A, MARY AA. Minimum Neighborhood Domination of Split Graph of Graphs. Baghdad Sci.J [Internet]. 2023 Mar. 1 [cited 2023 Oct. 3];20(1(SI):0273. Available from:


Cockayne EJ, Hedetniemi ST. Optimal Domination in Graphs. IEEE Trans Circuits Syst. 1975; 22(11): 855 – 857.

Bermudo S, Gómez JCH, Sigarreta JM. Total k-Domination in Graphs. Discuss. Math Graph Theory. 2018; 38: 301–317.

Al-Harere MN, Mitlif RJ, Sadiq FA. Variant Domination Types for a Complete h-Ary Tree. Baghdad Sci J. 2021; 18(1(Suppl.)): 797-802.

Martínez AC, Mira HFA, Sigarreta JM, Yero IG. On Computational and Combinatorial Properties of the Total Co-Independent Domination Number of Graphs. Comput J. 2019, 62(1): 97–108.

Aslam A, Nadeem MF, Zahid Z, Zafar S, Gao W. Computing Certain Topological Indices of the Line Graphs of Subdivision Graphs of Some Rooted Product Graphs. Mathematics. 2019; 7(5): 393.

Omran AA, Oda HH. Hn-Domination in Graphs. Baghdad Sci J. 2019; 16(1(Suppl.)): 242-247.

Al-Harere MN, Bakhash PAK. Tadpole Domination in Graphs. Baghdad Sci J. 2018; 15(4): 466-471.

Daoud SN, Mohamed K. The Complexity of Some Families of Cycle-Related Graphs. J Taibah Univ Sci. 2017; 11(2): 205-228.

Bertossi AA. Dominating Sets for Split and Bipartite Graphs. Inf Process Lett. 1984; 19(1): 37-40.