any ${\Delta}$-regular graph with order $n$. Then $A(G;x)$ has ${\Delta}+1$ non-zero coefficients. Furthermore, $$A(G;x)=\displaystyle\sum_{i=0}^{{\Delta}} A_{{\Delta}-2i}(G)\ x^{n+{\Delta}-2i},$$ with $A_{-{\Delta}}(G)=n$, $A_{{\Delta}}(G)\ge1$, and $$A_{{\Delta}-2i}(G) \ge \frac{n {{\Delta}\choose i}}{\min\{{\Delta},n-i\}} \quad \text{for  } \ 1\le i\le {\Delta}-1 \text{  if  } {\Delta}>0.$$

Since $G$ is ${\Delta}$-regular, by Theorem \[t:PropRegular\] we have $A_{-{\Delta}}(G)=n$, $A_{{\Delta}}(G)\ge1$ and $A(G;x)$ is an even or an odd function of $x$. Assume now that ${\Delta}>0$ and fix $1\le i \le {\Delta}-1$. Let us consider $u\in V$ and $v_1,\ldots,v_i$ different vertices in $N(u)$. Denote by $S_u:=V\setminus\{v_1,\ldots,v_i\}$. Then, we have that ${\delta}_{S_u}(v)\ge {\Delta}-i$ and ${\delta}_{\overline{S_u}}(v)\le i$ for every $v\in S_u$; furthermore, the equalities hold at $u$. Let $S_u^*\subset S_u$ such that $\langle S_u^*\rangle$ is the connected component of $\langle S_u\rangle$ which contains $u$. So, $S_u^*$ is an exact defensive (${\Delta}-2i$)-alliance and $A_{{\Delta}-2i}(G)>0$. Since each set $S_u^*$ can appear at most $n-i$ times (once for each $S_w^*$ with $w\in V\setminus \{v_1,\ldots,v_i\}$), and at most ${\Delta}$ times (once for each $S_w^*$ with $w\sim v_1$), we obtain $A_{{\Delta}-2i}(G)\ge n {{\Delta}\choose i}/ \min\{{\Delta},n-i\}$.

A *Hamiltonian cycle* is a cycle in a graph that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a *Hamiltonian graph*. The following theorem is a well known result in 