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)