全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

A note on global alliances in trees

Keywords: global defensive alliance , global offensive alliance , domination , trees

Full-Text   Cite this paper   Add to My Lib

Abstract:

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 (respectively, defensive) alliance if for each vertex in $V-S$ (respectively, in $S$) at least half the vertices from the closed neighborhood of $v$ 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)$ (respectively, global defensive alliance number $\gamma_{a}(G))$ is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of $G$. We show that if $T$ is a tree of order $n,$ then $\gamma_{o}(T)\leq2\gamma(T)-1$ and if $n\geq3,$ then $\gamma_{o}(T)\leq\frac{3}{2}\gamma_{a}(T)-1$. Moreover, all extremal trees attaining the first bound are characterized.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133