z-logo
open-access-imgOpen Access
On the global offensive alliance number of a tree
Author(s) -
Mohamed Bouzefrane,
Mustapha Chellali
Publication year - 2009
Publication title -
rocznik akademii górniczo-hutniczej im. stanisława staszica. opuscula mathematica/opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2009.29.3.223
Subject(s) - offensive , mathematics , alliance , tree (set theory) , combinatorics , operations research , political science , law
For a graph \(G=(V,E)\), a set \(S \subseteq V\) is a dominating set if every vertex in \(V-S\) has at least a neighbor in \(S\). A dominating set \(S\) is a global offensive alliance if for every vertex \(v\) in \(V-S\), at least half of the vertices in its closed neighborhood are in \(S\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\) and the global offensive alliance number \(\gamma_o(G)\) is the minimum cardinality of a global offensive alliance of \(G\). We first show that every tree of order at least three with \(l\) leaves and \(s\) support vertices satisfies \(\gamma_o(T) \geq (n-l+s+1)/3\) and we characterize extremal trees attaining this lower bound. Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here