Some Nordhaus - Gaddum Type Relations On Strong Efficient Dominating Sets

Year 2016, Volume: 5 Issue: 11, 4 - 16, 08.08.2016

K Murugan N Meena

Abstract

Let G = (V, E) be a simple graph with p vertices and q edges. A subset S of V(G) is called a strong (weak) efficient dominating set of G if for every vV(G),│Ns[v]∩S│=1(│Nw[v]∩S│=1).Ns(v) ={u V(G) uv E(G), deg(u) ≥ deg(v)}.The minimum cardinality of a strong (weak) efficient dominating set G is called strong (weak) efficient domination number of G and is denoted by γse (γwe ). A graph G is strong efficient if there exists a strong efficient dominating set of G. In this paper, the authors introduced a new parameter called the number of strong efficient dominating sets of a graph G denoted by # γse (G) and studied some Nordhaus- Gaddum type relations on strong efficient domination number of a graph and its derived graph. The relation between the number of strong efficient dominating sets of a graph and its derived graph is also studied

Keywords

Strong efficient dominating sets, Strong efficient domination number and number of strong efficient dominating sets

References

• Bange. D.W, Barkauskas. A.E. and Slater. P.J., Efficient dominating sets in graphs, Application of Discrete Mathematics, 189 – 199, SIAM, Philadephia (1988).
• Harary. F., Graph Theory, Addison – Wesley (1969).
• Haynes. T W., Stephen T. Hedetniemi, Peter J. Slater. Fundamentals of domination in graphs. Advanced Topics, Marcel Dekker, Inc, New York (1998).
• Meena.N., Subramanian.A.., Swaminathan.V., Graphs in which Upper Strong Efficient Domination Number Equals the Independent Number, International Journal of Engineering and Science Invention, 32-39,Vol 2, Issue 12, December 2013.
• Meena.N., Subramanian.A.., Swaminathan.V., Strong Efficient Domination in Graphs, International Journal of Innovative Science, Engineering & Technology, 172-177, Vol.1 Issue 4, June 2014.
• Sampathkumar.E and Pushpa Latha.L. Strong weak domination and domination balance in a graph, Discrete Math., 161: 235 – 242 (1996).
• S.K.vaidya and P.L.Vihol, Fibonacci and Super Fibonacci graceful labeling of some graphs, Studies in Mathematical Sciences,Vol.2,No.2,(2011), 24-35.