A New Upper Bound on the Global Defensive Alliance Number in Trees

Xue-gang Chen, Wai Chee Shiu

Abstract


A global defensive alliance in a graph $G=(V,E)$ is a dominating set $S$ satisfying the condition that for every vertex $v\in S$, $|N[v]\cap S|\geq |N(v)\cap(V-S)|$. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.


Full Text: PDF