Secure domination in a network A protection strategy - Canoy, Segio R. Jr.; Go, Carmelito E. (2011)
The concept of secure total domination in graphs was invested further. The study particularly considered a result obtained by Benecke et al. in a recent article. A counter example showed that such a result is faulty. A rectification of this result was provided and some quick consequences of the same were stated. Secure total dominating sets in the join of graphs were also studied and some characterizations were generated. The aforementioned new type of protection strategy in a given network was considered in this study. This strategy which uses a variant of domination in a network is more secure than the ones studied previously. Just like other existing strategies, the objective in this strategy is to evaluate or determine the minimum number of guards needed to protect a graph or network. The following main results have been generated in this study:
1. Let X be the total dominating set in a connected graph, v ϵ X, and u ϵ V (G) \ X. Then v X-defends u if and only if epn(v;X) and ipn(v;X) are contained in Ng (u).
2. If u ϵ epn(v;X) for some v ϵ X, then u is not X-defended.
3. Let X be a total dominating set in G. Then X is a secure total dominating set if and only if (i) epn(v;x) = Ø for all v ϵ X, and (ii) for each u ϵ V(G) \ X there exists v ϵ X \ N(u) such that ipn(v;X) ≤ N(u).
4. Let G be a connected graph of order n ≥ 2. Then st(G) = 2 if and only if there exists x, y ϵ V(G) \ {x} and N(y) = V(G) \ {y}.
5. Let G and H be connected non-complete graphs of orders m and n, respectively. Then yst (G+H) = 2 if and only if one of the following holds (i)yst (G) = 2 or (ii)yst(H)=2 or (iii)Δ(G) = - 1 and Δ(H) = n - 1.
6. Let G be a connected graph of orders m and n, respectively, and suppose st(G+H)≠2. Then st(G+H)=3 if and only if at least one of the following holds: (i) y(G)=2, or (ii) y(H), or (iii) Δ(G)=-1 1 or Δ(H)=n-1 (but not both).
Keywords: Mathematical models; Graphic methods