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.
This work is licensed under a Creative Commons Attribution 4.0 International License.
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. https://doi.org/10.21123/bsj.2021.18.1(Suppl.).0797
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. https://doi.org/10.1093/comjnl/bxy038
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. https://doi.org/10.21123/bsj.2019.16.1(Suppl.).0242
Al-Harere MN, Bakhash PAK. Tadpole Domination in Graphs. Baghdad Sci J. 2018; 15(4): 466-471. https://doi.org/10.21123/bsj.2018.15.4.0466
Daoud SN, Mohamed K. The Complexity of Some Families of Cycle-Related Graphs. J Taibah Univ Sci. 2017; 11(2): 205-228. https://doi.org/10.1016/j.jtusci.2016.04.002
Bertossi AA. Dominating Sets for Split and Bipartite Graphs. Inf Process Lett. 1984; 19(1): 37-40. https://doi.org/10.1016/0020-0190(84)90126-1