Strong Domination Number of Some Graphs

Abstract

In this paper, we consider strong domination number of P_n^k  and C_n^k .  Let  G=(V,E) be a graph, V is a vertex set and E is an edge set of graph G and u,v∈V . u strongly dominates v and v weakly dominates u if  (i) uv ∈ E and (ii) d ( u, G ) ≥ d ( v, G ) . A set D⊂V  is a strong-dominating set (sd-set) of G if every vertex in V-D is strongly dominated by at least one vertex in D. The strong domination number γ_s of G is the minimum cardinality of an sd-set.

Keywords

• Domination Number, Strong Domination Number, Power of a Graph, Networks, sd-set

Strong Domination Number of Some Graphs

Abstract

In this paper, we consider strong domination number of P_n^k  and C_n^k .  Let  G=(V,E) be a graph, V is a vertex set and E is an edge set of graph G and u,v∈V . u strongly dominates v and v weakly dominates u if  (i) uv ∈ E and (ii) d ( u, G ) ≥ d ( v, G ) . A set D⊂V  is a strong-dominating set (sd-set) of G if every vertex in V-D is strongly dominated by at least one vertex in D. The strong domination number γ_s of G is the minimum cardinality of an sd-set.

 

Keywords

• Domination Number, Strong Domination Number, Power of a Graph, Networks, sd-set

References

1. Barefoot, C.A.; Entringer, R.; Swart,H. Vulnerability in graphs a comparative survey, Journal of Combinatorial Mathematics and Combinational Computing. 1987; 1, 12-22.
2. Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J. Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
3. Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J. (Eds.), Domination in Graphs, Advanced Topics, Marcel Dekker, New York, 1998.
4. Sampathkumar, E.; Latha L. P. Strong weak domination and domination balance in a graph, Discrete Mathematics. 1996; 161(13), 235-242.
5. Rautenbach, D. Bounds on the strong domination number, Discrete Mathematics. 2000; 215, pp. 201-212.
6. Rautenbach, D. Bounds on the weak domination number, Australasian Journal of Combinatorics 18, 1998, pp.245-251.
7. Domke G. S.; Hattingh J. H.; Markus L. R.; Ungerer E. On parameters related to strong and weak domination in graphs, Discrete Mathematics, 258, 2002, pp. 1-11.