  The alliance polynomial of a graph $\Gamma$ with order $n$ and maximum degree
$\delta_1$ is the polynomial $A(\Gamma; x) = \sum_{k=-\delta_1}^{\delta_1}
A_{k}(\Gamma) \, x^{n+k}$, where $A_{k}(\Gamma)$ is the number of exact
defensive $k$-alliances in $\Gamma$. We provide an algorithm for computing the
alliance polynomial. Furthermore, we obtain some properties of $A(\Gamma; x)$
and its coefficients. In particular, we prove that the path, cycle, complete
and star graphs are characterized by their alliance polynomials. We also show
that the alliance polynomial characterizes many graphs that are not
distinguished by other usual polynomials of graphs.
