Opuscula Math. 32, no. 2 (2012), 235-238
http://dx.doi.org/10.7494/OpMath.2012.32.2.235

Opuscula Mathematica

# A note on a relation between the weak and strong domination numbers of a graph

Razika Boutrig
Mustapha Chellali

Abstract. In a graph $$G=(V,E)$$ a vertex is said to dominate itself and all its neighbors. A set $$D \subset V$$ is a weak (strong, respectively) dominating set of $$G$$ if every vertex $$v \in V-S$$ is adjacent to a vertex $$u \in D$$ such that $$d_G(v) \geq d_G(u)$$ ($$d_G(v) \leq d_G(u)$$, respectively). The weak (strong, respectively) domination number of $$G$$, denoted by $$\gamma_w(G)$$ ($$\gamma_s(G)$$, respectively), is the minimum cardinality of a weak (strong, respectively) dominating set of $$G$$. In this note we show that if $$G$$ is a connected graph of order $$n \geq 3$$, then $$\gamma_w(G) + t\gamma_s(G) \leq n$$, where $$t=3/(\Delta+1)$$ if $$G$$ is an arbitrary graph, $$t=3/5$$ if $$G$$ is a block graph, and $$t=2/3$$ if $$G$$ is a claw free graph.

Keywords: weak domination, strong domination.

Mathematics Subject Classification: 05C69.

Full text (pdf)