Scattered Domination in Graphs
Rajesh Kumar Tripathi1, Minakshi Gaur2
1Rajesh Kumar Tripathi, Astt Professor Deptt. of Mathematics, Bharat Institute Technology, Meerut(U.P.), India
2Dr. Minakshi Gaur, Head, Depts. Mathematics, N.A.S.(PG) College, Meerut(U.P.), India
Manuscript received on September 01, 2012. | Revised Manuscript received on September 02, 2012. | Manuscript published on September 05, 2012. | PP: 279-283 | Volume-2 Issue-4, September 2012. | Retrieval Number: D0950082412/2012©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In this paper, we want to compute an optimal scattered domination for domination graph. In this paper, we also show optimal broadcast domination is in path P. We first prove that every graph has an optimal scattered domination in which the subset of vertices dominated by the same vertex is ordered in a path or a cycle. Using this, we give a polynomial time algorithm for computing optimal broadcast domination of arbitrary graphs.
Keywords: Domination graph, scattered domination graph, path, broadcast domination of graph.