% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{verbatim}
\usepackage{graphicx}
%\usepackage{amsthm}
\begin{comment}
\usepackage{latexsym}

\usepackage{algorithm}


\usepackage{color}
\usepackage{setspace}
\end{comment}


%\newtheorem {theorem} {Theorem} [section]
%\newtheorem {lemma} [theorem] {Lemma}
%\newtheorem {claim} [theorem] {Claim}
%\newtheorem {openp} [theorem] {Open Problem}
%\newtheorem {conj}  [theorem] {Conjecture}
%\newtheorem {cor}   {Corollary} [theorem]
%\renewcommand {\thecor} {\arabic{section}.\arabic{theorem}\alph{cor}}
%\newtheorem {cort}  {Corollary} [theorem]
%\newtheorem {obs}  [theorem] {Observation}

\newtheorem{conjecture}{Conjecture}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{proof}{Proof}
\newtheorem{cl}{Claim}
%\newtheorem{claim}{Claim}
%\newtheorem{cor}{Corollary}
\begin{document}

\setcounter{page}{83}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Some bounds on alliances in trees}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Ararat Harutyunyan}

\address{Department of Mathematics,
Simon Fraser University \\ 8888 University Drive, Burnaby, BC,
Canada\\ aha43@sfu.ca}

\begin{keyword}
alliances \sep global defensive alliance \sep global offensive
alliance \sep trees \sep complete k-ary trees
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{} The study of alliances in graphs was first introduced by
Hedetniemi, Hedetniemi and Kristiansen \cite{HHK2004}. They
introduced the concepts of defensive and offensive alliances,
global offensive and global defensive alliances and studied
alliance numbers of a class of graphs such as cycles, wheels,
grids and complete graphs. Haynes et al. \cite{HHH2003} studied
the global defensive alliance numbers of different classes of
graphs. They gave lower bounds for general graphs, bipartite
graphs and trees, and upper bounds for general graphs and trees.
Rodriquez-Velazquez and Sigarreta \cite{RS1} studied the defensive
alliance number and the global defensive alliance number of line
graphs. A characterization of trees with equal domination and
global strong defensive alliance numbers was given by  Haynes,
Hedetniemi and Henning \cite{HHH2004}. Rodriguez-Velazquez and
Sigarreta \cite{RS2007} gave bounds for the defensive, offensive,
global defensive, global offensive alliance numbers in terms of
the algebraic connectivity, the spectral radius, and the Laplacian
spectral radius of a graph. They also gave bounds on the global
offensive alliance number of cubic graphs in \cite{RS} and the
global offensive alliance number for general graphs in
\cite{RS2006}.

Balakrishnan et al. \cite{BCDD2006} studied the complexity of
global alliances. They showed that the decision problems for
global defensive and global offensive alliances are both
NP-complete for general graphs.

Given a simple graph $G=(V,E)$ and a vertex $v \in V$, the
\emph{open neighborhood} of $v$, $N(v)$, is defined as
$N(v)=\{u:(u,v) \in E \}$. The \emph{closed neighborhood} of $v$,
denoted by $N[v]$, is $N[v] = N(v) \cup \{v\}$.
\begin{definition}
A set $S \subset V$ is a \emph{defensive alliance} if for every $v
\in S$, $|N[v] \cap S| \geq |N(v) \cap (V-S)|$. A defensive
alliance $S$ is called a \emph{global defensive alliance} if $S$
is also a dominating set.
\end{definition}
\begin{definition}
A set $S \subset V$ is an \emph{offensive alliance} if for every
$v \in V-S$, $|N[v] \cap S| \geq |N[v] - S|.$ An offensive
alliance $S$ is called a \emph{global offensive alliance} if $S$
is also a dominating set.
\end{definition}
\begin{definition}
The \emph{global defensive(offensive) alliance number} of $G$ is
the cardinality of a minimum size global defensive(offensive)
alliance in $G$, and is denoted by $\gamma_a(G) (\gamma_o(G))$. A
minimum size global defensive(offensive) alliance is called a
$\gamma_a(G)$-set ($\gamma_o(G)$-set).
\end{definition}

In this paper, we study the global defensive and global offensive
alliance numbers of trees. We find the asymptotic order of global
defensive alliance number of complete $k$-ary trees, and compute
exactly the global offensive alliance number. We also give a sharp
bound on the difference between the global offensive and global
defensive alliance numbers for a general tree.

The rest of the paper is organized as follows. In Section 2, we
find the global defensive alliance number of complete binary and
complete ternary trees. We also find tight bounds for the global
defensive alliance number of complete $k$-ary trees, and determine
the asymptotic order. In Section 3, we find the global offensive
alliance number of complete $k$-ary trees. We also compare the
global offensive and global defensive alliance numbers of a
general tree.
\section{Defensive Alliances in Complete k-ary Trees}
A \emph{k-ary tree} is a rooted tree where each node has at most
$k$ children. A \emph{complete k-ary tree} is a $k$-ary tree in
which all the leaves have the same depth and all the nodes except
the leaves have $k$ children. We let $T_{k,d}$ be the complete
$k$-ary tree with depth/height $d$. The proofs of the following
theorems are omitted.
\begin{theorem} Let $n$ be the order of $T_{2,d}$. Then $\gamma_a(T_{2,d})
= \lceil \frac{2}{5}n \rceil$ for any $d$.
\end{theorem}

\begin{cor} If $d \equiv 2 (mod \; 4)$ or $d \equiv 3 (mod
\; 4)$ then there is a unique $\gamma_a(T_{2,d})$-set. If $d
\equiv 0 (mod \; 4)$ or $d \equiv 1 (mod \; 4)$ then there are
exactly two $\gamma_a(T_{2,d})$-sets.
\end{cor}
\begin{comment}

\begin{proof} In case 1, it was shown that each component of
$S_{i, i-3}$ had to have at least 3 vertices of any
$\gamma_a(T_d)$-set, and there was only one way to choose exactly
3 vertices. In the subcase (iii), we had two choices to choose a
vertex from $S_{1,0}$. Similarly, in case 2 we had to choose two
vertices from $S_{2,0}$ and we stated that this can be done in two
ways.
\end{proof}
Now, we are going to find the global defensive alliance numbers of
complete $k$-ary trees of depth $d$, $T_{k,d}$, for $k=3$ or
$k=4$.
\\

\end{comment}

\begin{theorem} If $d \geq 4$ then $\gamma_a(T_{3,d}) = \lfloor
\frac{19}{36}n \rfloor$ if $d$ is odd and $ \gamma_a(T_{3,d}) =
\lceil \frac{19}{36}n \rceil$ if $d$ is even.
\end{theorem}

\begin{comment}

\begin{proof}
Again, define $$S_{i,j} = \cup_{j \leq k \leq i} L_{k}.$$

Consider the set $S_{d, d-2}$. Its induced subgraph, $<S_{d,
d-2}>$ is a forrest. Each component of this forrest is an
identical copy of $T_{3,2}$. Given a $\gamma_o(T)$-set $S$, we
claim that each component of $<S_{d,d-2}>$ contains at least 7
vertices of $S$. Without loss of generality, consider the
component $C_1$ which is the subtree rooted at vertex $(d-2, 1)$.
Observe that if $v \in S$ is not a leaf, then at least two of its
neighbors are also in $S$. For each child of $(d-2,1)$ which is
not in $S$, all its three children must be in $S$ for otherwise
$S$ is not a dominating set. Also, if a child of $(d-2,1)$ is in
$S$, at least two of its neighbors must be in $S$.  The children
of $(d-2,1)$ have one neighbor in common, $(d-2,1)$. Therefore, if
$m$ is the number of children of $(d-2,1)$ which are in $S$, then
we need at least $(2m + 1)+3(3-m) = 10 - m $ vertices of $C_1$ to
be in $S$. Therefore, we need at least 7 vertices of $S$ in $C_1$.
\\
Next, we consider $S_{i, i-3}$, $i \geq 3$. This set induces a
graph which is a forrest. All the components of $<S_{i, i-3}>$ are
identical of copies of the tree $T_{3,3}$. We claim that each
component $C$ contains at least 10 vertices of $S$. Without loss
of generality, consider the component $C_2$ which contains the
vertex $(i-3,1)$.
\\
First, assume that $(i-3,1)$ is in $S$. For each child $v$ of the
vertex $(i-3,1)$ which is not in $S$, we need 3 vertices in
$S_{i,i-3} \cap T_v$ to dominate each of $v$'s children. For each
child $u$ of $(i-3,1)$ which is in $S$, we need at least one of
$u$'s children, say $y$, to be in $S$, and hence at least one
child of $y$ to be in $S$. Therefore, in this case we have that
$S$ must contain at least 10 vertices of $S_{i,i-3}$.
\\
Second, assume that the vertex $(i-3,1)$ is not in $S$. For every
child $u$ of $(i-3,1)$ which is not in $S$, one of $u$'s children,
say $v$, must be in $S$ to dominate $u$, and hence two of $v$'s
children must be in $S$ as well. Also, we need at least two
vertices to dominate the other two children of $u$. Therefore,
among $u$'s descendants in $S_{i,i-3}$ we need at least 5 nodes in
$S$. Now we consider the children of $(i-3,1)$ which are in $S$.
For every child $w$ of $(i-3,1)$ which is in $S$, at least two of
$w$'s children must be in $S$ as well. For each of $w$'s children
$x$ which is in $S$, one of $x$'s children must also be in $S$.
Therefore, among $w$ and its descendants there are at least 5
vertices that must be in $S$. We conclude that if $(i-3,1)$ is not
in $S$, then $S$ must contain at least 15 vertices in $S_{i,i-3}$.
\\
Therefore, we need at least 10 vertices of $S$ in each component
of $S_{i,i-3}$.


Next, we define a set $S^{'}$ which is a global defensive alliance
and show that $S^{'}$ contains exactly 7 vertices in all the
connected components of $S_{d,d-2}$ and 10 vertices in the
components of $S_{d-3-4i,d-6-4i}$, for $0 \leq i \leq \lfloor
\frac{d-6}{4} \rfloor$. By what we proved this would imply that
$S^{'}$ is a $\gamma_a(T_{3,d})$-set. \\
First let $S_1$ be the set
$$S_1 = \cup_{0 \leq i \leq \lfloor (d-2)/4 \rfloor} S_{d-4i-1,
d-4i-2}$$ and $S_2$ be the set \\
$S_2 = \{(i,j): i = d,\;d-3,\;d-4,\;d-7,\;d-8,\;d-11,
d-12\;...,d-3-4 \lfloor \frac{d-4}{4} \rfloor,\; d-4 - 4 \lfloor
\frac{d-4}{4} \rfloor \,;\ j=1,\;4,\;7,\;10,\;...,\;3^i-2\}.$
\\

We consider two cases. \\
{\bf Case 1:} $d \equiv 2 (mod \; 4)$ or $d \equiv 3 (mod \; 4)$.\\
i) if $d \equiv 2 (mod \; 4)$ then $S_1 = S_{d-1,d-2} \cup
S_{d-5,d-6} \cup ... \cup S_{1,0}$ and $S_2 = \{(i,j): i =
d,\;d-3,\;d-4,\;d-7,\;d-8,\;...,3,\;2\,;\
j=1,\;4,\;7,\;10,\;...,\;3^i-2\}$
\\
Let $S^{'}=S_1 \cup S_2$.
\\\\
As was shown above, if $S$ is a global defensive alliance then in
each component of $S_{d-3-4i,d-6-4i}$, for $0 \leq i \leq \lfloor
\frac{d-6}{4} \rfloor$, it must contain at least 10 vertices, and
in each component of $S_{d,d-2}$ it must contain at least 7
vertices. It is easy to check that the set $S^{'}$ attains these
lower bounds and at the same time it is a global defensive
alliance. Therefore, $S^{'}$ is a $\gamma_a(T_{3,d})$-set. The
size of $S^{'}$ is
\begin{eqnarray*}
|S^{'}| &=& 7 \times 3^{d-2} + 10 \times 3^{d-6} + 10 \times
3^{d-10} +...+ 10 \times 3^0 \\
        &=& 7 \times 3^{d-2} + 10(3^{d-6} + 3^{d-10} +...+ 3^0)\\
        & = &7 \times 3^{d-2} + 10 \left(\frac{(3^4)^{\frac{d-2}{4}}-1}{80}\right)\\
        & = & \left (7+ \frac{1}{8} \right)3^{d-2}- \frac{1}{8} = \frac{57}{8} \times
\frac{2n}{27} + \frac{57}{8} \times \frac{1}{27} - \frac{1}{8}\\
        &=& \left \lceil \frac{19}{36}n  \right \rceil.
\end{eqnarray*}
ii) if $d \equiv 3 (mod \; 4)$.
\\
Then $S_1 = S_{d-1,d-2} \cup S_{d-5,d-6} \cup ... \cup S_{2,1}$
\\
$S_2 = \{(i,j): i = d,\;d-3,\;d-4,\;d-7,\;d-8,\;...,4,\;3\,;\
j=1,\;4,\;7,\;10,\;...,\;3^i-2\}$
\\
Let $S^{'}=S_1 \cup S_2$.
\\
Again, by a similar argument as in (i) it's easy to see that
$S^{'}$ is a global defensive alliance.
\begin{eqnarray*}
|S^{'}| &=& 7 \times 3^{d-2} + 10 \times 3^{d-6} + 10 \times
3^{d-10} +...+ 10 \times 3^1 \\
& = & 7 \times 3^{d-2} + 10(3^{d-6} + 3^{d-10} +...+ 3^1)\\
& = & 7 \times 3^{d-2} + 30\left(\frac{(3^4)^{\frac{d-3}{4}}-1}{80}\right)\\
&= & \frac{57}{8} \times \frac{2n}{27} + \frac{57}{8} \times
\frac{1}{27} - \frac{3}{8}\\
&=& \left \lfloor \frac{19}{36}n  \right \rfloor.
\end{eqnarray*}
{\bf Case 2:} $d \equiv 0 (mod \; 4)$ or $d \equiv 1 (mod \;
4)$.\\ Here we are going to slightly modify the definitions of $S_1$ and $S_2$ but the general argument is the same.\\
i)$d \equiv 0 (mod \; 4).$\\
Then let $S_1 = S_{d-1,d-2} \cup S_{d-5,d-6} \cup ... \cup
S_{3,2}$
\\
and $S_2 = \{(i,j): i = d,\;d-3,\;d-4,\;d-7,\;d-8,\;...,5,\;4\,;\
j=1,\;4,\;7,\;10,\;...,\;3^i-2\}$
\\
Let $S^{'}=S_1 \cup S_2 \cup \{(1,1)\}$.
\\
$S^{'}$ is a $\gamma_a(T)$-set because we know that we need at
least 1 vertex of any global defensive alliance in the subtree
formed by the root and its children.
\begin{eqnarray*}
|S^{'}| & = & 1 + 7 \times 3^{d-2} + 10 \times 3^{d-6} + 10 \times
3^{d-10} +...+ 10 \times 3^2 \\
& = & 1+7 \times 3^{d-2} + 10(3^{d-6} +
3^{d-10} +...+ 3^2)\\
      & =& 1+ 7 \times 3^{d-2} +
90 \left(\frac{(3^4)^{\frac{d-4}{4}}-1}{80} \right)\\
     & = & 1+ \frac{57}{8} \times \frac{2n}{27} + \frac{57}{8} \times
\frac{1}{27} - \frac{9}{8}\\
      &=& \lceil \frac{19}{36}n \rceil.
\end{eqnarray*}
ii) $d \equiv 1 (mod \; 4)$.
\\
Let $S_1 = S_{d-1,d-2} \cup S_{d-5,d-6} \cup ... \cup S_{4,3}$ and
\\
$S_2 = \{(i,j): i = d,\;d-3,\;d-4,\;d-7,\;d-8,\;...,6,\;5\,;\
j=1,\;4,\;7,\;10,\;...,\;3^i-2\}$
\\
Let $S^{'}=S_1 \cup S_2 \cup \{(0,1),\;(1,1),\; (2,1)\}$.
\\
It's not hard to see that $S$ is a $\gamma_a(T)$-set since any
global defensive alliance needs at least 3 vertices in $S_{2,0}$.
\begin{eqnarray*}
|S| &=& 3 + 7 \times 3^{d-2} + 10 \times 3^{d-6} + 10 \times
3^{d-10} +...+ 10 \times 3^3\\
& =& 3+7 \times 3^{d-2} + 10(3^{d-6} + 3^{d-10} +...+ 3^3) \\
&=&  3 + 7 \times 3^{d-2} +
270 \left(\frac{(3^4)^{\frac{d-5}{4}}-1}{80} \right)\\
& = &3+ \frac{57}{8} \times \frac{2n}{27} + \frac{57}{8} \times
\frac{1}{27} - \frac{27}{8}\\
&=& \left \lfloor \frac{19}{36}n \right \rfloor.
\end{eqnarray*}
\end{proof}

\end{comment}

\begin{theorem} $ \frac{27}{64}n -2 \leq \gamma_a(T_{4,d}) \leq \frac{27}{64}n + 2$.
\end{theorem}
%\begin{proof}
%The proof goes exactly the same as for $T_{3,d}$.
%\end{proof}
When $k$ is large, the methods used to prove the above theorems
are difficult to apply. Therefore, for general $k$, we give upper
and lower bounds for $\gamma_a(T_{k,d})$.
\begin{theorem}For $d \geq 2$, and $k \geq 2$, $$k^{d-1} \left \lfloor \frac{k-1}{2} \right \rfloor + k^{d-1} + k^{d-2}    \leq
\gamma_a(T_{k,d}) \leq k^{d-1} \left \lfloor \frac{k-1}{2} \right
\rfloor + k^{d-1} + k^{d-2}  +   k^{d-3}.$$
\end{theorem}

\begin{comment}


\begin{proof}
To get the lower bound we claim that for any global defensive
alliance $S$, each component $C$ of $S_{d,d-2}$ must contain at
least $1 + k + k \lfloor \frac{k-1}{2} \rfloor$ vertices of $C$.
The proof is analogous to the case when $k=3$, which is proven
above. For the upper bound, define $S_1 = \cup_{i=0}^{d-1}L_i$ and
let $S_2$ be any set that contains $\lfloor \frac{k-1}{2} \rfloor$
children of each vertex in $L_{d-1}$. Then $S_1 \cup S_2$ is a
global defensive alliance.
\end{proof}

\end{comment}


It follows that $ \gamma_a(T_{k,d}) \sim k^{d-1} \left \lfloor
\frac{k-1}{2} \right \rfloor$, where the asymptotics is taken to
be in terms of $k$. Since the number of vertices of $T_{k,d}$ is
$n = \frac{k^{d+1}-1}{k-1}$ we get $\gamma_a(T_{k,d}) \sim
\frac{n}{2}$ when $k$ tends to infinity. For offensive alliances
we have the following result, the proof of which is omitted.
\section{Offensive Alliances vs. Defensive Alliances in general trees}
\begin{theorem} Let $T_{k,d}$ be the complete $k$-ary tree with
depth $d \geq 1$. Then, $\gamma_{o}(T_{k,d})= \left \lfloor
\frac{n}{k+1} \right \rfloor.$
\end{theorem}
\begin{comment}



\begin{proof}

Let $S = \bigcup_{i=0}^{\lfloor \frac{d-1}{2} \rfloor} L_{d-2i-1}$
\\
{\bf Case 1:} $d \equiv 1 (mod \; 2)$.
\\
It is easy to see that $S$ is a global offensive alliance. $S$ is
obviously a dominating set, and for every $v \notin S$, $v$'s
children and parent are both in $S$. We want to prove that any
$\gamma_{o}(T_{k,d})$-set contains at least as many vertices as
$S$.
\\
Let $S^{'}$ be any $\gamma_{o}(T_{k,d})$-set. Let $v$ be any
vertex at depth $d-(2i-1)$, $(1 \leq i \leq \frac{d+1}{2})$.
Consider the subtree formed by $v$ and its $k$ children. Then the
claim is that at least one vertex in this subtree must be in
$S^{'}$. Suppose not. Then $v$'s parent must be in $S^{'}$ for
otherwise $v$ would not be dominated. Since $v$ is not in $S^{'}$
and its parent is in $S^{'}$ it follows that some of the children
of $v$ must be in $S^{'}$, a contradiction. Therefore, every such
subtree contains at least one vertex that must be in any
$\gamma_{o}(T_{k,d})$-set. It is easy to see that $S$ contains
exactly one vertex for each such subtree. Therefore, $S$ is a
minimum cardinality global offensive alliance.
\\
$|S| = k^{d-1} + k^{d-3} +... + k^2 + k^0 =
\frac{(k^2)^{\frac{d+1}{2}} - 1}{k^2 - 1} = \frac{k^{d+1} -1}{k^2
- 1}= \frac{n}{k+1}$.
\\
Therefore, if $d$ is odd, $\gamma_{o}(T_{k,d}) = \frac{n}{k+1}$.
\\\\
{\bf Case 2:} $d \equiv 0 (mod \; 2)$.
\\
As in case 1, it is easy to see that $S$ is a global offensive
alliance. Also, by the same argument as in case 1, $S$ is a
$\gamma_{o}(T_{k,d})$-set.
\\
$|S| = k^{d-1} + k^{d-3} +... + k^3 + k^1 =
\frac{k((k^2)^{\frac{d}{2}} - 1)}{k^2 - 1} = \frac{k^{d+1}
-k}{(k-1)(k+1)}= \frac{k^{d+1}-1+1-k}{(k-1)(k+1)} =
\frac{k^{d+1}-1}{(k-1)(k+1)} + \frac{1-k}{(k-1)(k+1)} =
\frac{n}{k+1} - \frac{1}{k+1}$.
\\
Therefore, if $d$ is even, $\gamma_{o}(T_{k,d}) =
\frac{n}{k+1}-\frac{1}{k+1}$.
\\
Thus, $\gamma_{o}(T_{k,d}) = \lfloor \frac{n}{k+1} \rfloor$ for
all $d \geq 1.$
\end{proof}

\end{comment}

Note that $\gamma_o(T_{k,d}) \sim \frac{n}{k}$ with respect to
$k$. As $k$ becomes very large the difference between
$\gamma_a(T_{k,d})$ and $\gamma_o(T_{k,d})$ approaches $n/2$. In
general, we are interested if this difference can be larger for
other trees. In fact, we have the following theorem.


\begin{theorem} For any tree $T$  of order $n$, $\gamma_a(T)
\leq \gamma_o(T) + \frac{n}{2}.$
\end{theorem}
\begin{proof}
Root the tree $T$ at a vertex of largest \emph{eccentricity}(the
eccentricity of a vertex $x$ is equal to $max_{y \in
V(G)}d(x,y)$). Let $T$ have a depth $d$, and let $v$ be a vertex
at depth $d-2$. Let $u$ be $v$'s parent. We are going to proceed
by induction on $n$. We may assume that $diam(T) \geq 3$.
Otherwise, $T$ is a star and the theorem holds (this also
establishes the base case).
\\
Let $T_{v}$ be the subtree of $T$ rooted at vertex $v$. Let
$T^{'}= T - T_{v}$ be the subtree of $T$ obtained by removing all
the vertices of $T_v$, and let $|T^{'}|=n^{'}$. Define $P$ to be
the set of children of $v$ in $T$ which are support vertices.
Denote by $L$ the set of children of $v$ which are leaves. By
assumption on the diameter of $T$, $|P| \geq 1$. Let $y_i$ denote
the number of children of each vertex in $P$, $1 \leq i \leq |P|$.
The proofs of the following two claims are omitted due to space
restrictions.
\begin{cl} $\gamma_o(T^{'}) \leq \gamma_o(T) - |P|$.
\end{cl}
\begin{comment}

\begin{proof} To see this consider a $\gamma_o(T)$-set $S$.
Without loss of generality, we can assume that all the vertices of
$P$ are in $S$ (for every $x \in P$ not in $S$ a child of $x$ is
in $S$ and we can swap it with $x$). First, suppose $v$ is not in
$S$. Then $v$'s parent $u$ is dominated by a vertex in $T^{'}$. In
this case, it is easy to see that $S-P$ is a global offensive
alliance for $T^{'}$. Therefore, in this case $\gamma_o(T^{'})
\leq \gamma_o(T) - |P|$. Next, suppose that $v$ is in $S$. Then
the set $S-P-\{v\} \cup \{u\}$ is global offensive alliance for
$T^{'}$. In this case as well, we have the inequality that we
desire.
\end{proof}
\end{comment}

\begin{cl} $\gamma_a(T) \leq \gamma_a(T^{'}) + k$ where
$k=1+|P| + max \left(\lceil \frac{|L|-|P|}{2} \rceil , 0 \right) +
\sum_{i=1}^{|P|} \lfloor \frac{y_i-1}{2} \rfloor$.
\end{cl}

\begin{comment}
\begin{proof} Let $S^{'}$ be a $\gamma_a(T^{'})$-set. Then if we
add to $S^{'}$, \{v\}, the set of vertices in $P$ and at most
$\lceil \frac{|L|-|P|}{2} \rceil$ vertices of $L$, and for each $i
\in P$, $\lfloor \frac{y_i-1}{2} \rfloor$ of its children then we
get a global defensive alliance for $T$. A crucial assumption here
is that $y_1 \geq 1$.
\end{proof}
\end{comment}
By the last claim and the induction hypothesis we have
$$\gamma_a(T) \leq \gamma_a(T^{'}) + k \leq \gamma_o(T^{'}) +
\frac{n^{'}}{2} + k.$$ What is left to prove is that
$\gamma_o(T^{'}) + \frac{n^{'}}{2} + k \leq \gamma_o(T) +
\frac{n}{2}.$ By the first claim, it is sufficient to prove that
$k- \lfloor \frac{n-n^{'}}{2} \rfloor \leq |P|$. Since $|P| \geq
1$, we have that $$ 1 + max \left (\left \lceil \frac{|L|-|P|}{2}
\right \rceil, 0 \right) + \sum_{i=1}^{|P|} \left \lfloor
\frac{y_i-1}{2} \right \rfloor \leq 1 + \left \lfloor
\frac{|L|}{2} \right \rfloor + \sum_{i=1}^{|P|} \left \lfloor
\frac{y_i-1}{2} \right \rfloor \leq \left \lfloor
\frac{n-n^{'}}{2} \right \rfloor,$$ as required.

\end{proof}
The above bound is best possible. Consider $K_{1,n-1}$ where $n$
is odd. Then $\gamma_o(K_{1,n-1})=1$ and $\gamma_a(K_{1,n-1}) = 1
+ \frac{n-1}{2}$.

In a bipartite graph, each partite set forms a global offensive
alliance. It follows that $\gamma_o(T) \leq \frac{n}{2}$ for any
tree $T$. Therefore, $|\gamma_a(T) - \gamma_o(T)| \leq
\frac{n}{2}$. However, we believe the following stronger result is
true: for any $n$-vertex tree $T$, $ \gamma_o(T) \leq \gamma_a(T)
+ \frac{n}{6}.$ This conjecture, if true, is essentially best
possible because of the following theorem, the proof of which we
omit.
\begin{theorem}For any constant $C
> 0 $, there exists an $n$-vertex tree $T$ with $\gamma_o(T) \geq
\gamma_a(T) + \frac{n}{6} - C$.
\end{theorem}
%\begin{center}
%\includegraphics{tree.eps}
%\end{center}
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix
% \section{}
% \label{}
\begin{thebibliography}{00}
\bibitem{BCDD2006} H. Balakrishnan, A. Cami, N. Deo, and R. D. Dutton, On the complexity of finding optimal
global alliances, J. Combinatorial Mathematics and Combinatorial
Computing, Volume 58 (2006), 23-31.
\bibitem{HHH2003}T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, Global defensive allliances in graphs,
Electronic Journal of Combinatorics 10 (2003), no. 1, R47.
\bibitem{HHH2004} T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, A characterization of trees with equal domination
and global strong alliance numbers, Utilitas Mathematica, Volume
66(2004), 105-119.

\bibitem{HHK2004} S. M. Hedetniemi, S. T. Hedetniemi, and P. Kristiansen,
Alliances in graphs, Journal of Combinatorial Mathematics and
Combinatorial Computing, Volume 48 (2004), 157-177.

\bibitem{RS2007} J. A. Rodriguez-Velazquez, J.M. Sigarreta, Spectal study of alliances in graphs, Discussiones Mathematicae Graph Theory 27 (1) (2007)
143-157.

\bibitem{RS} J. A. Rodriquez-Velazquez and J. M. Sigarreta, Offensive alliances in cubic graphs, International Mathematical Forum
Volume 1 (2006), no. 36, 1773-1782.

\bibitem{RS2006} J. A. Rodriguez-Velazquez, J.M. Sigarreta,
Global Offensive Alliances in Graphs, Electronic Notes in Discrete
Mathematics, Volume 25 (2006), 157-164.

\bibitem{RS1} J. A. Rodriguez-Velazquez, J. M. Sigarreta,
On defensive alliances and line graphs. Applied Mathematics
Letters, Volume 19 (12) (2006) 1345-1350.
% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

%\bibitem{}

\end{thebibliography}

\end{document}
