No label defined (Q4812925)

Let \(G=(V, E)\) be a graph and \(f: V \rightarrow \{0,1,2, \ldots \}\) be a function. Let \(V_i = \{v \in V\mid f(v) = i \}\). Then \((V_0, V_1, \ldots )\) partitions \(V\) and is also used to identify \(f\). The value \(f(v)\) can be thought of as the number of guards at \(v\). The weight \(w(f)\) of \(f\) is defined as \(\sum_{v \in V}f(v)\) and \(f\) is said to be a safe function if each \(v \in V_0\) is adjacent to at least one vertex in \(V-V_0\). So \(V-V_0\) is a dominating set for \(G\). A safe function of the type \(f=(V_0, V_1)\) is called a dominating function and the minimum weight of such a dominating function is called the domination number of \(G\) and is denoted by \(\gamma(G)\). A safe function of the type \(f = (V_0, V_1, V_2)\) such that each \(v \in V_0\) is adjacent to at least on vertex in \(V_2\) is called a Roman dominating function for \(G\) and the smallest weight of such a function is called the Roman domination number of \(G\) and is denoted by \(\gamma_R(G)\). Suppose \(v \in V_0\) is adjacent with some \(u \in V_0\). Then \(g_{uv}\) is the function defined by \(g_{uv}(v) = f(v) -1\), \(g_{uv}(u)=1\) and \(g_{uv} (w) = f(w)\) for all \(w \in V -\{u, v\}\). A safe function \(f = (V_0, V_1, V_2)\) such that for each \(u \in V_0\) there exists \(v \in N(u) \cap (V-V_0)\) such that \(g_{uv}\) is safe is called a weak Roman dominating function (WRDF) of \(G\). The minimum weight of a WRDF is called the weak Roman domination number of \(G\) and is denoted by \(\gamma_{r}(G)\). There are WRDFs \(f = (V_0, V_1, V_2)\) of minimum weight with \(V_2 = \emptyset\). To this end a function \(f=(V_0, V_1)\) such that for each \(u \in V_0\) there exists a \(v \in N(u) \cap V_1\) such that \(g_{uv}\) is safe is called a secure dominating function. The minimum weight of a secure dominating function is called the secure domination number of \(G\) and is denoted by \(\gamma_s(G)\). It is shown for all graphs \(G\) of order \(n\) that \(\gamma_s(G) \leq n - \nu(G)\) where \(\nu(G)\) is the matching number of \(G\). Let \(\beta(G)\) be the independence number of \(G\) and \(\delta(G)\) the minimum degree of \(G\). For claw-free graphs \(G\) it is shown that \[ \begin{aligned} \gamma_r(G)&= \gamma_s(G) \leq 2\gamma(G) \tag{i}\\ \gamma_s(G)&\leq \begin{cases} \beta(G) & \text{if }G \text{ is also }C_5\text{-free}\\ \frac{3}{2}\beta(G) & \text{otherwise}\end{cases} \tag{ii}\\ \gamma_s(G) &\leq 3n/(\delta(G)+3) \tag{iii} \end{aligned} \] For \(K_t\)-free graphs with maximum degree \(\Delta\), the following sharp lower bound is established: \[ \gamma_s(G) \geq n(2\Delta -2t +5)/((\Delta + 1)^2-(t-1)(t-2)). \]