Computing the alliance polynomial of a graph

Abstract

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.

Accepted for publication in Ars Combinatoria

References in corpus (1)

• Introduction to Domination Polynomial of a Graph

Cited by in corpus (2)

• Computing the strong alliance polynomial of a graph
• Defensive alliance polynomial