Alliance polynomial of regular graphs

Abstract

The alliance polynomial of a graph $G$ with order $n$ and maximum degree $\Delta$ is the polynomial $A(G;x)={\sum }_{k=-\Delta }^{\Delta }{A}_k(G)x^{n+k}$, where $A_k(G)$ is the number of exact defensive $k$-alliances in $G$. We obtain some properties of $A(G;x)$ and its coefficients for regular graphs. In particular, we characterize the degree of regular graphs by the number of non-zero coefficients of their alliance polynomial. Besides, we prove that the family of alliance polynomials of $\Delta$-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not $\Delta$-regular. By using this last result and direct computation we find that the alliance polynomial determines uniquely each cubic graph of order less than or equal to $10$.

One reference was rectified. Our apology to their authors