---
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$.'
address:
- 'National council of science and technology (CONACYT) $\&$ Autonomous University of Zacatecas, Paseo la Bufa, int. Calzada Solidaridad, 98060 Zacatecas, ZAC, Mexico'
- 'Department of Mathematics, Universidad Carlos III de Madrid, Av. de la Universidad 30, 28911 Leganés, Madrid, Spain'
- 'Faculty of Mathematics, Autonomous University of Guerrero, Carlos E. Adame 5, Col. La Garita, Acapulco, Guerrero, Mexico'
- 'Humboldt International University, 4000 West Flagler Street, 33134, Miami, Fl., USA'
author:
- Walter Carballosa
- 'José M. Rodr[í]{}guez'
- 'José M. Sigarreta'
- 'Yadira Torres-Nuñez'
title: Alliance polynomial of regular graphs
---

Regular Graphs ,Cubic Graphs ,Defensive Alliances ,Alliance Polynomials

05C69 ,11B83

Introduction.
=============

Graph polynomials have been widely study since George D. Birkhoff introduced the chromatic polynomial (1912) in an attempt to prove the four color theorem (see [@Bi]). Although the original motivation for the study of this invariant (chromatic number) is still important, much of the current interest, for example, in the Tutte polynomial is not related to any of its applications. In particular, graph polynomials are considered interesting when they encode much information about the underlying graph. Some parameters of a graph $G$ allow one to define polynomials on the graph $G$, for instance, the parameters associated to matching sets [@F; @GG], independent sets [@BDN; @GH; @HL], domination sets [@AAP; @AP], chromatic numbers [@Bi; @R; @T] and many others. In recent years there has been an increase in the number of papers introducing new properties of graph polynomials [@KM; @MR; @MRB].

The study of defensive alliances in graphs, together with a variety of other kinds of alliances, was introduced in [@KHH]. In the cited paper authors initiated the study of the mathematical properties of alliances. In particular, several bounds on the defensive alliance number were given. The particular case of global defensive alliance (generalization of dominating sets) was investigated in [@FLH3; @HHH; @SRV2] where several bounds on the global defensive alliance number were obtained. Several tight bounds on different types of alliance numbers of a graph were obtained in [@KHH; @SRV2; @S; @SGBR], namely, (global) defensive alliance number, (global) offensive alliance number and (global) dual alliance number. Moreover, alliances, as a graph-theoretic concept, have recently attracted a great deal of attention due to some interesting applications in a variety of areas, including quantitative analysis of secondary RNA structures [@HKSZ] and national defense [@P]. Besides, defensive alliances could work as a mathematical model of web communities. Adopting the definition of a Web community proposed recently in [@FLG], “a Web community is a set of web pages having more hyperlinks (in either direction) to members of the set than to non-members”. In [@CHRT], the authors use the cardinality of the strong defensive alliances by define the strong alliance polynomial of a graph. The exact defensive alliance was defined in [@C]. The alliance polynomial was introduced in [@To] and have been studied in [@CRST; @CRSTx].

Throughout this paper, $G=(V,E)$ denotes a simple graph (not necessarily connected) of order $|V|=n$ and size $|E|=m$. We denote two adjacent vertices $u$ and $v$ by $u\sim v$. For a nonempty set $X\subseteq V$, and a vertex $v\in V$, $N_X(v)$ denotes the set of neighbors $v$ has in $X$: $N_X(v):=\{u\in X: u\sim v\},$ and the degree of $v$ in $ X$ will be denoted by $\delta_{X}(v)=|N_{X}(v)|$. We denote by ${\delta}$ and ${\Delta}$ the minimum and maximum degree of $G$, respectively. If $G$ is a regular graph with degree ${\Delta}$ we say that $G$ is ${\Delta}$-regular. The subgraph induced by $S\subset V$ will be denoted by $\langle S\rangle $ and the complement of the set $S\in V$ will be denoted by $\overline{S}$.

A nonempty set $S\subseteq V$ with $\langle S\rangle$ connected is a *defensive $k$-alliance* in $G=(V,E)$, $k\in [-\Delta,\Delta]\cap \mathbb{Z}$, if for every $ v\in S$, $$\label{cond-A-Defensiva} \delta _S(v)\ge \delta_{\overline{S}}(v)+k.$$ A vertex $v\in S$ is said to be $k$-*satisfied* by the set $S$, if holds.

We consider the value of $k$ in the set of integers $\mathcal{K}:= [-\Delta,\Delta]\cap \mathbb{Z}$. It may be that there are some values of $k \in\mathcal K$ such that there do not exist. For instance, for $k\ge 2$ there are no defensive $k$-alliances in the star graph $S_n$ with $n$ vertices. Besides, if $G$ is connected then $V(G)$ is a defensive ${\delta}$-alliance. Notice that for any $S$ with $\langle S\rangle$ connected there exists some $k\in\mathcal{K}$ such that it is a defensive $k$-alliance in $G$.

We define, for $S\subseteq V(G)$ inducing a connected subgraph $\langle S\rangle$, $$\label{eq:k_exact}
    k_{S}:=\displaystyle\max_{} \{k\in\mathcal{K} \,:\,  S \text{ is a defensive $k$-alliance}\}.$$ We say that $k_{S}$ is the *exact index of alliance of* $S$, or also, $S$ is an *exact defensive $k_{S}$-alliance* in $G$. The exact index of alliance of $S$ in $G$ is also $k_{S}= \displaystyle\min_{v\in S} \{{\delta}_{S}(v) - {\delta}_{\overline{S}}(v)\}$.

The *alliance polynomial* of a graph $G$ is defined as an ordinary generating function for the number of exact defensive $k$-alliances: $$\label{eq:Poly1}
    A(G;x)= \displaystyle\sum_{k\in \mathcal{K}} A_{k}(G) x^{n+k}, \ \text{ with } A_{k}(G) \text{ the number of exact defensive } k \text{-alliances in } G.$$

There are several d.p.-equivalent definitions for an alliance polynomial. For instance, another natural definition for alliance polynomials of $G$ could be $A^\star(G;x)= \sum_{k\in \mathcal{K}} A_{k}(G) x^{k}$ (*i.e.*, $A(G;x)= x^n\, A^\star(G;x)$). We may also define it by $A^\dag(G;x)=\sum_{k\in \mathcal{K}} \big(A_k(G)+1\big) x^k$. Note that, $A^\star(G;x)$ and $A^\dag(G;x)$ are Laurent polynomials, and that the polynomial $A^\dag(G;x)$ does not satisfy any easy variant of Corollary \[c:CubUnim\]. Hence it is convenient to keep the previous choice, although each result in this paper has an analogous for $A^\star(G;x)$.

The following procedure allows to compute the alliance polynomial of a graph $G$ with order $n$, see [@CRST Algorithm 2.1]. This will be used in Section \[sect3\] in order to compute alliance polynomials. Let us consider $W=\{S_1,\dots,S_{2^n-1}\}$ the collection of nonempty subsets of $V$.

\[algorithm\] ${}$Input: adjacency matrix of $G$. Output: alliance polynomial of $G$. The algorithm starts with $A(G;x)=0$ and continues with the following steps, for $1 \le j \le 2^n-1$.

1.  [If $\langle S_j\rangle$ is a connected subgraph, then go to step (2), else replace $j$ by $j+1$ and apply this step again.]{}

2.  [Compute $k_{S_j}$, and add one term $x^{n+k_{S_j}}$ to $A(G;x)$.]{}

3.  [If $j < 2^n-1$, then replace $j$ by $j+1$ and apply step (1) again. If $j = 2^n-1$, then the algorithm stops.]{}

The main aim of this work is to obtain further results about the alliance polynomial of regular graphs (graphs with all vertices with the same degree), since they are a very interesting class of graphs with many applications (see, e.g., [@B; @Cu; @DM; @RST]). In this paper we study the alliance polynomials of regular graphs and their coefficients, see Section \[sect:reg\]. In Section \[sect:con\_reg\] we focus on the alliance polynomials of connected regular graphs; besides, we prove that the family of alliance polynomials of connected ${\Delta}$-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not connected ${\Delta}$-regular (see Theorems \[t:Reg0-3\] and \[t:Reg4-6\]). Finally, by using Theorem \[t:Reg0-3\] and direct computation we find that the alliance polynomial determines uniquely each cubic graph of order less than or equal to $10$.

Alliance polynomials for regular graphs {#sect:reg}
=======================================

In this section we deal with regular graphs, in particular, we obtain some properties of the alliance polynomial of regular graph and its coefficients. Below, a quick reminder of some previous results for general graphs (not necessarily regular) which will be useful, see [@CRST]. We denote by $\operatorname{Deg}(p)$ the degree of the polynomial $p$.

\[p:AlliPoly\] Let $G$ be any graph. Then $A(G;x)$ satisfies the following properties:

i)  [$A(G;x)$ does not have zeros in the interval $(0,\infty)$.]{}

ii) [$A(G;1) < 2^{n}$, and it is the number of connected induced subgraphs in $G$.]{}

iii) [If $G$ has at least an edge and its degree sequence has exactly $r$ different values, then $A(G;x)$ has at least $r + 1$ terms.]{}

iv) [ $A(G;x)$ is a symmetric polynomial (i.e., an even or an odd function of $x$) if and only if the degree sequence of $G$ has either all values odd or all even.]{}

v)  [$A_{-{\Delta}}(G)$ and $A_{-{\Delta}+ 1}(G)$ are the number of vertices in $G$ with degree ${\Delta}$ and ${\Delta}-1$, respectively.]{}

vi) [$A_{{\Delta}}(G)$ is equal to the number of connected components in $G$ which are ${\Delta}$-regular.]{}

vii) [$n + {\delta}\leq \operatorname{Deg}(A(G;x)) \leq n + {\Delta}$.]{}

As usual, by *cycle* we mean a simple closed curve, i.e., a path with different vertices, unless the last one, which is equal to the first vertex. The following lemma is a well known result of graph theory.

\[l:degreem\] If $r\ge 2$ is a natural number and $G$ is any graph with ${\delta}(v) \ge r$ for every $v \in V(G)$, then there exists a cycle $\eta$ in $G$ with $L(\eta) \ge r+1$.

We show now some results about the alliance polynomial of regular graphs and their coefficients. If $G$ is a graph and $v\in V(G)$, we denote by $G \setminus \{v\}$ the subgraph obtained by removing from $G$ the vertex $v$ and the edges incident to $v$. We say that $v$ is a *cut vertex* if $G \setminus \{v\}$ has more connected components than $G$. Besides, if $p$ is a polynomial we denote by $\operatorname{Deg}_{min}(p)$ the minimum degree of their non-zero coefficients.

\[t:PropRegular\] For any ${\Delta}$-regular graph $G$, its alliance polynomial $A(G;x)$ satisfies the following properties:

i)  [$A_{-{\Delta}+2i}(G)$ is the number of connected induced subgraphs of $G$ with minimum degree $i$ $(0\le i\le{\Delta})$.]{}

ii) [$\operatorname{Deg}_{\min}\big(A(G;x)\big)= n - {\Delta}$ and $A_{-{\Delta}}(G) = n$.]{}

iii) $\operatorname{Deg}\big(A(G;x)\big) = n + {\Delta}$. Furthermore,

    $$\label{eq:RegOrderV}
             n = \frac{\operatorname{Deg}_{\min}\big(A(G;x)\big) + \operatorname{Deg}\big(A(G;x)\big)}2$$

    and $$m = A_{-{\Delta}}(G) \frac{\operatorname{Deg}\big(A(G;x)\big) - \operatorname{Deg}_{\min}\big(A(G;x)\big)}4 = \frac{\operatorname{Deg}^2\big(A(G;x)\big) - \operatorname{Deg}_{\min}^2\big(A(G;x)\big)}8.$$

iv) [$1\le A_{{\Delta}}(G) \le n/({\Delta}+1)$. Furthermore, $G$ is a connected graph if and only if $A_{{\Delta}}(G) = 1$.]{}

v)  [If ${\Delta}>0$, then $A_{-{\Delta}+2}(G) \ge m$ and $A_{{\Delta}-2}(G) \ge n+n_0$ with $n_0$ the number of cut vertices; in particular, $A_{{\Delta}-2}(G)\ge n$.]{}

vi) [$A(G;x)$ is either an even or an odd function of $x$. Furthermore, $A(G;x)$ is an even function of $x$ if and only if $n + {\Delta}$ is even.]{}

vii) [The unique real zero of $A(G;x)$ is $x=0$, and its multiplicity is $n-{\Delta}$.]{}

We prove each item separately.

i)  [Let us consider $S\subset V$ with $S$ an exact defensive ($2i-{\Delta}$)-alliance in $G$. Then, we have for all $v\in S$ $$2{\delta}_S(v)\ge {\delta}(v)+2i-{\Delta}= {\Delta}+2i-{\Delta}\quad \Leftrightarrow \quad {\delta}_S(v)\ge i,$$ besides, the equality holds at some $w\in S$. We have the result since $A_{-{\Delta}+2i}(G)$ is the number of exact defensive ($2i-{\Delta}$)-alliance in $G$.]{}

ii) [One can check directly that if $S$ is a single vertex, then $S$ is an exact defensive ($-{\Delta}$)-alliance; furthermore, it is clear that any $S\subseteq V$ with $\langle S\rangle$ connected and more than one vertex is not an exact defensive ($-{\Delta}$)-alliance, since for any $v\in S$ we have $$\label{eq:i}
          {\delta}_{S}(v) - {\delta}_{\overline{S}}(v) \geq  1 - ({\Delta}- 1) = -{\Delta}+ 2.$$ Consequently $A_{-{\Delta}}(G) = n$, since $G$ is a ${\Delta}$-regular graph.]{}

iii) [The maximum value in $\mathcal{K}$ is ${\Delta}$, so $Deg\big(A(G;x)\big)$ is at most $n+{\Delta}$. We have that each connected component of $G$ is an exact defensive ${\Delta}$-alliance since ${\delta}(v)={\Delta}$ for any vertex $v$. Then, $A_{{\Delta}}(G)>0$ and $Deg\big(A(G;x)\big)= n+{\Delta}$. Besides, the other results are consequences of the well known fact $2m=n{\Delta}$ and the previous results.]{}

iv) [By item i), $A_{{\Delta}}(G)$ is the number of connected induced subgraphs of $G$ with minimum degree ${\Delta}$; hence, $A_{{\Delta}}(G)$ is the number of connected components of $G$. Besides, since any connected component has cardinality greater than ${\Delta}$, we obtain the upper bound of $A_{{\Delta}}(G)$.]{}

v)  [If $u,v\in V$ with $u\sim v$, then $S:=\{u,v\}$ is an exact defensive ($2-{\Delta}$)-alliance since $1={\delta}_S(u)={\delta}_{\overline{S}}(u)+2-{\Delta}$ and $1={\delta}_S(v)={\delta}_{\overline{S}}(v)+2-{\Delta}$. Thus, we obtain $A_{-{\Delta}+2}(G)\ge m$. Note that if ${\Delta}=1$, we have the second inequality. Assume that ${\Delta}\ge2$. Without loss of generality we can assume that $G$ is connected; otherwise, it suffices to analyze each connected component of $G$. Let us define $S_v:=V\setminus\{v\}$ for any $v\in V$. Since ${\delta}_{S_v}(u)\ge {\Delta}-1$, ${\delta}_{\overline{S_v}}(u)\le1$ for every $u\in S_v$ and both equalities hold for every $w\in N(v)$, we have that $S_v$ is an exact defensive (${\Delta}-2$)-alliance if $v$ is a non-cut vertex, or contains at least two exact defensive (${\Delta}-2$)-alliances if $v$ is a cut vertex.]{}

vi) [The first statement is a consequence of Theorem \[p:AlliPoly\] iv). Consider an exact defensive $k$-alliance $S$ in $G$. So, there exists $v\in S$ with $$2{\delta}_{S}(v) = {\delta}(v) + k = {\Delta}+k.$$ Then, ${\Delta}\equiv k \ (\text{mod } 2)$, $n + k \equiv n + {\Delta}\ (\text{mod } 2)$ and we have the result.]{}

vii) [Since $Deg_{\min}\big(A(G;x)\big)=n-{\Delta}$, we have that $x=0$ is a zero of $A(G;x)$ with multiplicity $n-{\Delta}$. The positivity of all coefficients of $A(G;x)$ gives $A(G;x)\neq 0$ for every $x>0$. Finally, by item vi), $A(G;x)=(-1)^{n+{\Delta}}A(G;-x)\neq0$ for every $x<0$.]{}

Note that Theorem \[t:PropRegular\] (items ii, iv, v and vi) has the following direct consequence.

\[c:Cubic\] Let $G$ be any cubic graph. Then, $$A(G;x)=A_{-3}(G)\, x^{n-3}+A_{-1}(G)\, x^{n-1}+A_1(G)\, x^{n+1}+A_{3}(G)\, x^{n+3},$$ with $A_{-3}(G)=n < m\le A_{-1}(G)$ and $A_{1}(G)\ge A_{3}(G)$.

A finite sequence of real numbers $(a_{0} , a_{1} , a_{2} , . . . , a_{n})$ is said to be *unimodal* if there is some $k \in \{0, 1, . . . , n\}$, called the *mode* of the sequence, such that $$a_{0} \leq . . . \leq a_{k-1} \leq a_{k} \geq a_{k+1} \geq . . . \geq a_{n}.$$ A polynomial is called unimodal if the sequence of its coefficients is unimodal. Therefore, we have the following result for alliance polynomial of a cubic graph, note that $A^\dag$ does not satisfy it.

\[c:CubUnim\] For any cubic graph $G$, $x^{(3-n)/2}\,A(G;\sqrt{x}\,)$ is an unimodal polynomial.

\[c:ConComp\] Let $G$ be any connected graph. Then $G$ is regular if and only if $A_{{\Delta}}(G) = 1$.

If $G$ is regular, then by Theorem \[p:AlliPoly\] vi) we obtain $A_{{\Delta}}(G)=1$. Besides, if $A_{{\Delta}}(G)=1$, then there is an exact defensive ${\Delta}$-alliance $S$ in $G$ with ${\delta}_S(v) \ge {\delta}_{\bar{S}}(v) + {\Delta}\ge {\Delta}$ (i.e., ${\delta}_S(v)={\Delta}$ and ${\delta}_{\overline{S}}(v)=0$) for every $v\in S$. So, the connectivity of $G$ gives that $G$ is a ${\Delta}$-regular graph.

\[t:Regulars\] Let $G_1,G_2$ be two regular graphs. If $A(G_1;x)=A(G_2;x)$, then $G_1$ and $G_2$ have the same order, size, degree and number of connected components.

Let $n_1,n_2$ be the orders of $G_1$ and $G_2$, respectively, and ${\Delta}_1,{\Delta}_2$ the degrees of $G_1$ and $G_2$, respectively. Then, by Theorem \[t:PropRegular\] ii) and iii) we have $$n_1 - {\Delta}_1 = n_2 - {\Delta}_2 \quad \text{ and } \quad n_1+{\Delta}_1 = n_2+{\Delta}_2$$ and we conclude $$n_1 = n_2 \quad \text{ and } \quad {\Delta}_1 = {\Delta}_2.$$ Hence, both graphs have the same size. Finally, since $A_{{\Delta}_1}(G_1) = A_{{\Delta}_2}(G_2)$, they have the same number of connected components by Theorem \[p:AlliPoly\] vi).

\[c:Reg1\] Let $G_1,G_2$ be two regular graphs with orders $n_1$ and $n_2$, and degrees ${\Delta}_1$ and ${\Delta}_2$, respectively. If $n_1 \neq n_2$ or ${\Delta}_1 \neq {\Delta}_2$, then $A(G_1;x) \neq A(G_2;x)$.

The next theorem characterizes the degree of any regular graph by the number of non-zero coefficients of its alliance polynomial.

\[t:PolyReg\] Let $G$ be 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 graph theory which will be useful.

\[Dirac\] A graph with order $n \ge 3$ is Hamiltonian if every vertex has degree $n / 2$ or greater.

In what follows we will use the following notation: for any $A,B\subset V$, we denote by $N(A,B)$ the number of edges with one endpoint in $A$ and the other endpoint in $B$.

\[t:An+D-2=n\] Let $G$ be any ${\Delta}$-regular graph with order $n < 2{\Delta}$. Then $A_{{\Delta}-2}(G)=n$.

Notice that ${\Delta}\ge 2$, since otherwise, such a graph $G$ does not exist; furthermore, $n\ge {\Delta}+1 \ge 3$. We have that $G$ is a Hamiltonian graph by Theorem \[Dirac\]. Besides, by Theorem \[t:PropRegular\] i), we have that $A_{{\Delta}-2}(G)$ is the number of connected induced subgraphs of $G$ with minimum degree ${\Delta}-1$. Let us consider $u\in V$ and define $S_u:=V\setminus\{u\}$. Since $G$ is a Hamiltonian graph, $\langle S_u\rangle$ is connected. Besides, we have ${\delta}_{S_u}(v)\ge {\Delta}-1 \ge {\delta}_{\overline{S_u}}(v) + {\Delta}-2$ for all $v\in S_u$ and the equality holds at $w\in N(u)$. So, $S_u$ is an exact defensive (${\Delta}-2$)-alliance in $G$ and $A_{{\Delta}-2}(G)\ge n$.

Seeking for a contradiction assume that there is an exact defensive (${\Delta}-2$)-alliance $S\subset V$ with $|S|\le n-2$. Notice that $|S|\ge{\Delta}>n/2$, by Theorem \[t:PropRegular\] i). Then, since any vertex in $S$ has degree ${\Delta}$ in $G$ with at most one edge among $S$ and $\overline{S}$, we have $$N(S,S) + N(S,\overline{S}) = \frac{|S| {\Delta}}2 + \frac{N(S,\overline{S})}2 \le \frac{|S| {\Delta}}2 + \frac{|S|}2 = \frac{|S|({\Delta}+1)}2.$$ Besides, since $|\overline{S}|=n-|S|$, we have $$N(\overline{S},\overline{S}) \le \frac{(n-|S|)(n-|S|-1)}2.$$ If $m$ denotes the size of $G$, then $$\begin{aligned}
0 & = 2\left(N(S,S) + N(S,\overline{S}) + N(\overline{S},\overline{S})\right) - 2m \\
&\le |S|({\Delta}+1) + (n-|S|)(n-|S|-1) - n{\Delta}\\
& = |S|^2 + |S|({\Delta}+2-2n) + n^2 - n - n{\Delta}.
\end{aligned}$$ Define $P(x):=x^2 + x({\Delta}+2-2n) + n^2 - n - n{\Delta}$; then $P(|S|)\ge0$. Since $$\begin{aligned}
P\left(\frac{n}2\right) &= \frac{n^2}4 + \frac{n}2 ({\Delta}+2-2n) + n^2 - n - n{\Delta}\\
&= \frac{n^2}4 + \frac{n{\Delta}}2 + n -n^2 + n^2 - n - n{\Delta}\\
&= \frac{n}4(n-2{\Delta})<0
\end{aligned}$$ and $$\begin{aligned}
P(n-2)&= (n-2)^2 + (n-2)({\Delta}+2-2n) + n^2 - n - n{\Delta}\\
&= (n-2)^2 + (n-2)({\Delta}-n) - (n-2)^2 + n^2 - n - n{\Delta}\\
&= n-2{\Delta}< 0,
\end{aligned}$$ we obtain that $P(|S|)<0$. This is the contradiction we were looking for, so, there not exists an exact defensive (${\Delta}-2$)-alliance $S$ with $|S|\le n-2$. This finishes the proof since $V$ is an exact defensive ${\Delta}$-alliance.

A *clique* in a graph $G = (V, E)$ is a subset $C$ of the vertex set $V$, such that $\langle C\rangle$ is a complete graph.

\[l:clique\] Let $G$ be any ${\Delta}$-regular graph with order $n$, ${\Delta}\ge3$ and $2{\Delta}\le n \le 2{\Delta}+1$. If $G$ contains two cliques of cardinality ${\Delta}$, then these cliques are disjoint. In particular, $G$ contains at most two cliques of cardinality ${\Delta}$.

Seeking for a contradiction, assume that there exist $S_1,S_2\subset V$ cliques of cardinality ${\Delta}$ with $S_1\cap S_2\neq\emptyset$. Denote by $r$ the number $r:= |S_1\cap S_2|$; then $1\le r \le {\Delta}-1$. Note that for any $v\in S_1\cap S_2$ we have ${\delta}_{S_1\cup S_2}(v)= |S_1|-1 + |S_2\setminus S_1|= {\Delta}-1+{\Delta}-r$, so, we obtain $r={\Delta}-1$. Then, we have $|S_1\cup S_2|={\Delta}+1$ and ${\Delta}-1\le|\overline{S_1\cup S_2}|\le {\Delta}$. Besides, we have $N(S_1\cup S_2,\overline{S_1\cup S_2}) = 2 = |(S_1\cup S_2)\setminus (S_1\cap S_2)|$ and, since $|\overline{S_1\cup S_2}|\le{\Delta}$, $N(\overline{S_1\cup S_2},S_1\cup S_2)\ge |\overline{S_1\cup S_2}|\ge {\Delta}-1$. Since $N(S_1\cup S_2,\overline{S_1\cup S_2}) = N(\overline{S_1\cup S_2},S_1\cup S_2)$, we obtain ${\Delta}=3$ and $n=6$; therefore, $G$ is a graph isomorphic to either $K_{3,3}$ or the Cartesian product $P_2\Box K_3$. Thus, we obtain that there are not two non-disjoint cliques in $G$ with cardinality ${\Delta}$. This finishes the proof since, by $n\le 2{\Delta}+1$, it is impossible to have three disjoint cliques of cardinality ${\Delta}$ contained in $G$.

\[r:exitClique\] If $G$ is a ${\Delta}$-regular graph with $n \le 2{\Delta}+1$, then $G$ does not contain a clique of cardinality greater than ${\Delta}$, since $2({\Delta}+1)>2{\Delta}+1\ge n$.

\[r:DisjointClique\] Let $G$ be any ${\Delta}$-regular graph with order $n$ and ${\Delta}\ge1$ such that $G$ has two disjoint cliques of cardinality ${\Delta}$. Then

1.  If $n=2{\Delta}$, then $G$ is isomorphic to the Cartesian product graph $P_2 \Box K_{\Delta}$.

2.  If $n=2{\Delta}+1$, then ${\Delta}$ is even (since $n{\Delta}=2m$) and $G$ can be obtained from $P_2 \Box K_{\Delta}$ by removing ${\Delta}/2$ copy edges of $P_2$ and connecting the ${\Delta}$ vertices with degree ${\Delta}-1$ with a new vertex. In particular, if $S$ is a clique of cardinality ${\Delta}$ in $G$, then $\overline{S}$ is not an exact defensive (${\Delta}-2$)-alliance.

\[t:An+D-2&lt;=n+m\] Let $G$ be any ${\Delta}$-regular graph with order $n$, size $m$, ${\Delta}\ge 3$ and $2{\Delta}\le n \le 2{\Delta}+1$. Then $n\le A_{{\Delta}-2}(G)\le n+m+2$.

Note that if ${\Delta}=3$ then $n=6$, and $G$ is a graph isomorphic to either $K_{3,3}$ or $P_2\Box K_3$. Thus, a simple computation gives $6\le A_{1}(K_{3,3})=15\le 6 + 9 + 2$ and $6\le A_{1}(P_2\Box K_3) = 11 \le 6 + 9 + 2$.

Assume now that ${\Delta}\ge 4$. Clearly, $G$ is a connected graph and $\operatorname{diam}G = 2$, since $2{\Delta}>n-2$.

First we prove that $G$ does not have cut vertices. If $n=2{\Delta}$, then $G$ is a Hamiltonian graph by Theorem \[Dirac\]. If $n=2{\Delta}+1$, seeking for a contradiction assume that there is a cut vertex $w$ in $G$. Let $S_1,S_2 \subset V$ with $S_1\cup S_2\cup \{w\}=V$ such that $\langle S_1\rangle$ and $\langle S_2\rangle$ are disjoint. Without loss of generality we can assume that $|S_1|\le {\Delta}\le |S_2|$. Since ${\delta}_{S_1}(w),{\delta}_{S_2}(w)\ge1$, ${\delta}_{S_1}(w)+{\delta}_{S_2}(w)={\Delta}$ and ${\delta}_{S_1}(u)\le |S_1|-1 \le {\Delta}-1$ for all $u\in S_1$, we have ${\delta}_{S_1}(w)=|S_1|$ and ${\delta}_{S_1}(u)={\Delta}-1$ for all $u\in S_1$. Then, we obtain that $|S_1|={\Delta}$, but this is a contradiction since ${\delta}_{S_1}(w)={\Delta}-{\delta}_{S_2}(w)\le {\Delta}-1<{\Delta}=|S_1|={\delta}_{S_1}(w)$. Then, $G$ does not have cut vertices.

By Theorem \[t:PropRegular\] i), we have that $A_{{\Delta}-2}(G)$ is the number of connected induced subgraphs of $G$ with minimum degree ${\Delta}-1$; thus, any exact defensive (${\Delta}-2$)-alliance $S$ in $G$ verifies $|S|\ge {\Delta}$. Let us consider $u\in V$ and denote by $S_u:=V\setminus\{u\}$. Since $G$ does not have cut vertices, $\langle S_u\rangle$ is connected. Besides, we have ${\delta}_{S_u}(v)\ge {\Delta}-1 \ge {\delta}_{\overline{S_u}}(v) + {\Delta}-2$ for all $v\in S_u$ and the equality holds for every $v\in N(u)$; so, $S_u$ is an exact defensive (${\Delta}-2$)-alliance in $G$. Thus, $A_{{\Delta}-2}(G)\ge n$.

Let us consider $u_1,u_2\in V$ with $u_1\neq u_2$ and define $S_{u_1,u_2}:=V\setminus\{u_1,u_2\}$. If $u_1\nsim u_2$, then there is $w\in V$ with $u_1,u_2\in N(w)$ since ${\delta}(u_1)+{\delta}(u_2)= 2{\Delta}>|S_{u_1,u_2}|$; in fact, $S_{u_1,u_2}$ is not a defensive (${\Delta}-2$)-alliance in $G$. So, $S_{u_1,u_2}$ may be an exact defensive (${\Delta}-2$)-alliance in $G$, if $u_1\sim u_2$; then there are at most $m$ exact defensive (${\Delta}-2$)-alliances with $n-2$ vertices. Consider now $u_1,\ldots,u_r\in V$ with $3\le r\le {\Delta}-1$ and $u_i\neq u_j$ if $i\neq j$. Note that $S_r:=V\setminus\{u_1,\ldots,u_r\}$ is not a defensive (${\Delta}-2$)-alliance in $G$ if $r>3$, since $N(\overline{S_r},S_r)\ge r({\Delta}-r+1)=2{\Delta}-r+(r-2)({\Delta}-r)> 2{\Delta}+1-r \ge |S_r|$. Besides, if $r=3$ and ${\Delta}\ge5$ (thus ${\Delta}-r\ge2$) we have the same inequality and then $S_r$ is not a defensive (${\Delta}-2$)-alliance in $G$. Note that, if $r=3$ and $n=2{\Delta}$, then $N(\overline{S_r},S_r)\ge 2{\Delta}-r+(r-2)({\Delta}-r)>2{\Delta}-r=n-r\ge |S_r|$ and we also conclude that $S_r$ is not a defensive (${\Delta}-2$)-alliance in $G$. However, if $r=3$, ${\Delta}=4$ and $n=2{\Delta}+1$ (thus, $n=9$), then $S_r$ may be an exact defensive (${\Delta}-2$)-alliance in $G$. But a simple computation gives that these five graphs $G$ verify $A_{2}(G)< 9+18+2$.

We analyze separately the cases $n=2{\Delta}$ and $n=2{\Delta}+1$. Assume first that $n=2{\Delta}$. We only need to compute the possible exact defensive (${\Delta}-2$)-alliances in $G$ with cardinality ${\Delta}$, since every defensive (${\Delta}-2$)-alliance has at least ${\Delta}$ vertices and $n=2{\Delta}$. If $S$ is an exact defensive (${\Delta}-2$)-alliance in $G$, then $S$ is a clique of cardinality ${\Delta}$ and by Lemma \[l:clique\] there are at most $2$ exact defensive (${\Delta}-2$)-alliances with ${\Delta}$ vertices. Assume now that $n=2{\Delta}+1$. So, ${\Delta}$ is even. We only need to compute the possible exact defensive (${\Delta}-2$)-alliances in $G$ with cardinalities ${\Delta}$ and ${\Delta}+1$. If $S$ is an exact defensive (${\Delta}-2$)-alliance in $G$ with $|S|={\Delta}+1$, then ${\delta}_S(u)\ge {\Delta}-1$ for every $u\in S$ and ${\delta}_S(u_0)={\Delta}$ for some $u_0\in S$, since otherwise ${\delta}_S(u)={\Delta}-1$ for every $u\in S$ and we conclude $({\Delta}+1)({\Delta}-1)=|S|({\Delta}-1)=2m_S$, with $m_S$ the size of $\langle S\rangle$, which is not possible since ${\Delta}$ is even. Hence, $N(\overline{S},S)\le {\Delta}$; furthermore, since $|\overline{S}|={\Delta}$, ${\delta}_{S}(v)\ge 1$ for all $v\in \overline{S}$, and so, $\overline{S}$ is a clique. If $S$ is an exact defensive (${\Delta}-2$)-alliance in $G$ with $|S|={\Delta}$, then ${\delta}_S(u)\ge{\Delta}-1$ for every $u\in S$ and $S$ is a clique of cardinality ${\Delta}$. Lemma \[l:clique\] completes the proof since if $G$ has two cliques of cardinality ${\Delta}$, then they are disjoint and Remark \[r:DisjointClique\] gives that $\overline{S}$ is not an exact defensive (${\Delta}-2$)-alliance in $G$.

\[t:RegCharact\] Let $G$ be a ${\Delta}$-regular connected graph with order $n$ and let $G^*$ be a graph with order $n_1$ and, minimum and maximum degrees ${\delta}_1$ and ${\Delta}_1$, respectively. If $A(G^*;x)=A(G;x)$, then $G^*$ is a connected graph with exactly $n$ vertices of degree ${\Delta}_1={\Delta}+n_1-n$, $n_1\ge n$, ${\Delta}_1\ge{\Delta}$ and ${\delta}_1 \equiv {\Delta}_1 (\text{mod } 2)$.

Furthermore, if $n_1 > n$, then the following inequalities hold: $$\label{eq:Poly2}
       \frac{{\Delta}_1+{\delta}_1+2}2\le {\Delta}.$$ $$\label{eq:Poly1}
       {\delta}_1+2 < {\Delta}< {\Delta}_1,$$ $$\label{eq:Poly3}
       {\Delta}+ 1 \le {\Delta}_1 \le 2{\Delta}-3,$$ $$\label{eq:Poly4}
       {\delta}_1+4 \le {\Delta}_1.$$

Since $A(G^*;x)=A(G;x)$ is a symmetric polynomial by Theorem \[t:PropRegular\] vi), we conclude that ${\delta}_1 \equiv {\Delta}_1 (\text{mod } 2)$ by Theorem \[p:AlliPoly\] iv). By Theorems \[p:AlliPoly\] v) and \[t:PropRegular\] ii), $G^*$ has $n$ vertices of maximum degree ${\Delta}_1$, so, $n_1 \geq n$; besides, $n_1 - {\Delta}_1 = n-{\Delta}$. Note that if $n_1=n$ then $G^*$ is a ${\Delta}$-regular graph with $A_{{\Delta}}(G^*)=1$, so, Theorem \[c:ConComp\] gives that $G^*$ is a connected graph.

Assume that $n_1 > n$. Denote by $t:=n_1-n={\Delta}_1 -{\Delta}$. Let $v_1,\ldots,v_n \in V(G^*)$ be the vertices in $G^*$ with degree ${\Delta}_1$ and define $S:=\{v_1,\ldots,v_n\}$. Note that for any $v\in S$ we have ${\delta}_{S}(v) \ge {\Delta}_1 - t = t + ({\Delta}_1-2t) \ge {\delta}_{\overline{S}}(v) + {\Delta}_1-2t$; hence, $S$ contains a defensive (${\Delta}_1-2t$)-alliance $S_1$ and $k_{S_1} \ge {\Delta}_1-2t$. Therefore, there is at least one term of degree greater or equal than $n_1+{\Delta}_1-2t$ in $A(G^*;x)$. Since $x^{n_1+{\Delta}_1-2t}=x^{n+{\Delta}}$, $S_1$ is an exact defensive (${\Delta}_1-2t$)-alliance in $G^*$. Finally, note that if $\langle S\rangle$ is not a connected subgraph (i.e., $S_1\neq S$), then in $A(G^*;x)$ appear at least two terms $x^{n+{\Delta}}$, but this is a contradiction since $A(G;x)$ is a monic polynomial by Theorem \[p:AlliPoly\] vi). Hence, $\langle S\rangle$ is connected. Since the degree of $A(G^*;x)$ is $n+{\Delta}=n_1+{\Delta}_1-2t$, then $S$ is an exact defensive (${\Delta}_1-2t$)-alliance in $G^*$; therefore, there exists $1\le j\le n$ such that ${\Delta}_1={\delta}(v_j)=2{\delta}_{\overline{S}}(v_j)+{\Delta}_1-2t$, and we have ${\delta}_{\overline{S}}(v_j)=t$. Since $|S|=n=n_1-t$ and $|\overline{S}|=t$, $\overline{S}\subseteq N(v_j)$ and $G^*$ is a connected graph.

Also, since $G^*$ is connected, $A(G^*;x)=A(G;x)$, $k_S={\Delta}_1-2t$ and $k_{V(G^*)}={\delta}_1$, we have ${\delta}_1\le {\Delta}_1-2t$. We are going to prove ${\delta}_1 < {\Delta}_1 - 2t$; seeking for a contradiction assume that ${\delta}_1 = {\Delta}_1 - 2t$. Since $G^*$ is connected, $k_{V(G^*)}={\delta}_1= {\Delta}_1 - 2t = k_{S}$ and this contradicts that $A(G^*;x)$ is a monic polynomial. Therefore, ${\delta}_1 < {\Delta}_1 - 2t$. But, since ${\delta}_1\equiv {\Delta}_1 (\text{mod } 2)$ we obtain ${\delta}_1+2\le {\Delta}_1-2({\Delta}_1-{\Delta})=2{\Delta}-{\Delta}_1$, so holds.

Besides, since ${\Delta}_1>{\Delta}$, gives ${\delta}_1+2 <{\Delta}$, and so, holds. Furthermore, we have ${\Delta}+1\le {\Delta}_1$ and gives , since ${\delta}_1\ge1$. Finally, since ${\Delta}\le {\Delta}_1-1$, provides .

Alliance polynomials of regular graphs with small degree {#sect:con_reg}
========================================================

The theorems in this section can be seen as a natural continuation of the study in [@CRST] in the sense of showing the distinctive power of the alliance polynomial of a graph. In particular, we show that the family of alliance polynomials of ${\Delta}$-regular graphs with small degree ${\Delta}$ is a special family of alliance polynomials since there not exists a non ${\Delta}$-regular graph with alliance polynomial equal to one of their members, see Theorems \[t:Reg0-3\] and \[t:Reg4-6\].

\[t:Reg0-3\] Let $G$ be a ${\Delta}$-regular graph with $0\le{\Delta}\le3$ and $G^*$ another graph. If $A(G^*;x) = A(G;x)$, then $G^*$ is a ${\Delta}$-regular graph with the same order, size and number of connected components of $G$.

In [@CRST Theorem 2.7] the authors obtain the uniqueness of the alliance polynomials of $0$-regular graphs (the empty graphs).

Theorems \[p:AlliPoly\] iii) and \[t:PolyReg\] give that $1$-regular graphs are the unique graphs which have exactly two non-zero terms in their alliance polynomial; besides, Theorems \[p:AlliPoly\] vi) and \[t:PropRegular\] ii) give the uniqueness of these alliance polynomials.

In order to obtain the result for $2\le{\Delta}\le3$, denote by $n,n_1$, the orders of $G,G^*$, respectively, and let ${\delta}_1,{\Delta}_1$ be the minimum and maximum degree of $G^*$.

Assume first that ${\Delta}=2$. By Theorem \[t:PolyReg\] we have $A(G;x)= n x^{n-2} + A_0(G) x^n + A_2(G) x^{n+2}$, thus, by Theorem \[p:AlliPoly\] iii) the degree sequence of $G^*$ has at most two different values. If $G^*$ is regular then Theorem \[t:Regulars\] gives the result. Therefore, seeking for a contradiction assume that the degree sequence of $G^*$ has exactly two different values (i.e., $G^*$ is bi-regular). By Theorems \[p:AlliPoly\] iv) and \[t:PropRegular\] vi) we have ${\delta}_1 \equiv {\Delta}_1 (\text{mod } 2)$. By Theorems \[p:AlliPoly\] v) and \[t:PropRegular\] ii) we have $A_{-{\Delta}_1}(G^*)=A_2(G)=n<n_1$ and $n-2=n_1-{\Delta}_1$, so, we have ${\Delta}_1>2$. By Theorems \[p:AlliPoly\] vii) and \[t:PropRegular\] iii) we have $n_1+{\delta}_1 \le n+2$, so, we obtain $0\le {\delta}_1 \le 1$. If ${\delta}_1=0$, then there is a connected component $G'$ of $G^*$ which is ${\Delta}_1$-regular. So, $k_{V(G')}={\Delta}_1$ and $\operatorname{Deg}\big(A(G^*;x)\big)=n_1+{\Delta}_1 > n+2$, which is a contradiction. Thus, we can assume that ${\delta}_1=1$. Then, we have $n_1=n+1$; and so, ${\Delta}_1=3$. We prove now that $A_1(G^*)\ge n$. Let $u_0,v_0$ be the vertices of $G^*$ with ${\delta}(u_0)=1$ and $v_0\sim u_0$. If $G^*$ is not connected, then it has a $3$-regular connected component $G_0^*$; since $V(G_0^*)$ is an exact defensive $3$-alliance, then $\operatorname{Deg}\big( A(G^*;x)\big) \ge n_1+3 > n+2 = \operatorname{Deg}\big( A(G;x)\big)$, which is a contradiction and we conclude that $G^*$ is connected. Let us define $S_v:=V(G^*)\setminus\{v\}$ for any $v\in V(G^*)\setminus \{v_0\}$. Since ${\delta}_{S_v}(u)\ge 2$, ${\delta}_{\overline{S_v}}(u)\le1$ for every $u\in S_v\setminus\{u_0\}$ and both equalities hold for every $w\in N(v)$, and ${\delta}_{S_v}(u_0)=1$, ${\delta}_{\overline{S_v}}(u_0)=0$, we have that $S_v$ is an exact defensive $1$-alliance or contains an exact defensive $1$-alliance if $v$ is a cut vertex. Thus, $A_{1}(G^*)\ge n$. Besides, Theorem \[t:PropRegular\] iv) gives $A_2(G)\le n/3 < n\le A_{1}(G^*)$, so, $A(G;x)\neq A(G^*;x)$. This is the contradiction we were looking for, and so, we conclude $n_1=n$ and ${\Delta}_1=2$, and we obtain the result for ${\Delta}=2$.

Finally, assume that ${\Delta}=3$. By Corollary \[c:Cubic\] we have $A(G^*;x) = A(G;x)= n x^{n-3} + A_{-1}(G) x^{n-1} + A_{1}(G) x^{n+1} + A_{3}(G) x^{n+3}$, with $A_3(G)$ is the number of connected components of $G$. By Theorem \[p:AlliPoly\] i), we have $n_1 - {\Delta}_1 = n - 3$ and $n \leq n_1$. Hence, $n_1\geq n$ and ${\Delta}_1 \geq 3$. Also we have $n_1 + {\delta}_1 \le n+3$ by Theorem \[p:AlliPoly\] vii). Furthermore, if ${\Delta}_1 = 3$, then $n_1 = n$ and so, $G^*$ is $3$-regular since $A_{- 3}(G^*) = n$. By Theorem \[p:AlliPoly\] vi) they have the same number of connected components, and consequently $G,G^*$ have the same size, too. We will finish the proof by checking that ${\Delta}_1=3$.

Seeking a contradiction, assume that ${\Delta}_1 > 3$ (then $n_1 > n$) and let $k = n_1 - n = {\Delta}_1 - 3$.

Assume that ${\Delta}_1 \ge 6$ (i.e., $k \ge 3$). Then there exists a connected component $G_0$ of $G^*$ with ${\delta}_{G_0}(v)={\delta}(v)\ge1$ for every $v\in V(G_0)$; if $S=V(G_0)$, then ${\delta}_S(v)={\delta}(v)\ge1$, and so, $k_{S}^{(G^*)} \ge 1$. Hence, $A(G^*;x)$ has at least one term with exponent greater than $n_1 \ge n + 3 = \operatorname{Deg}\big(A(G;x)\big)$, and $A(G^*;x) \neq A(G;x)$, which is a contradiction. Thus, ${\Delta}_1=4$ or ${\Delta}_1=5$.

Assume that ${\Delta}_1 = 5$, then $n_1 = n + 2$. By Theorem \[p:AlliPoly\] v), we have that $G^*$ has exactly $n$ vertices with degree $5$; and so, by Theorem \[p:AlliPoly\] iv), we have that the other two vertices of $G$ have degree $1$ or $3$. Since $n_1+{\delta}_1\le n+3$ by Theorem \[p:AlliPoly\] vii), we obtain ${\delta}_1=1$.

Assume that $G^*$ has two vertices $v_1$ and $v_2$ with degree $1$. In this case, if $v_1 \sim v_2$, then $G^*$ is a disconnected graph with at least one connected component which is $5$-regular since $V(G^*)\setminus \{v_1,v_2\}$ induces a $5$-regular subgraph $G_1$ of $G^*$. Since $V(G_1)$ is an exact defensive $5$-alliance, $\operatorname{Deg}(A(G^*;x))\ge n_1+5$ and we have $\operatorname{Deg}(A(G^*;x)) \ge n_1 + 5 > n+3 = \operatorname{Deg}(A(G;x))$. If $v_1 \nsim v_2$ but there exists $w\in V(G^*)$ such that $w\sim v_1$ and $w\sim v_2$, then let us consider the connected component $G_2$ of $G^*$ containing $\{v_1,v_2,w\}$. The set $S=V(G_2)\setminus\{v_1,v_2,w\}$ is a defensive $3$-alliance in $G^*$, since for any $v\in S$ we have ${\delta}_{S}(v) \geq 4$ and ${\delta}_{\overline{S}}(v) \leq 1$. Then, $\operatorname{Deg}(A(G^*;x)) \geq n_1 + 3 > n + 3 = \operatorname{Deg}(A(G;x))$. If $v_1 \nsim v_2$ but there does not exist $w\in V(G^*)$ with $w\sim v_1$ and $w\sim v_2$, then let us consider the connected component $G_3$ of $G^*$ containing $v_1$ and $S=V(G_3)\setminus\{v_1,v_2\}$. The set $S$ is a defensive $3$-alliance in $G^*$, since for all $v\in S$ we have ${\delta}_{S}(v) \geq 4$ and ${\delta}_{\overline{S}}(v) \leq 1$. Then, $\operatorname{Deg}(A(G^*;x)) \geq n_1 + 3 > n + 3 = \operatorname{Deg}(A(G;x))$.

Consider now the case of $G^*$ containing two vertices $v_1$ and $v_2$ with degree $1$ and $3$, respectively. If $v_1 \sim v_2$, then let us consider the connected component $G_4$ of $G^*$ containing $\{v_1,v_2\}$ and $S=V(G_4)\setminus\{v_1,v_2\}$. Then, $S$ is a defensive $3$-alliance in $G^*$, since for all $v\in S$ we have ${\delta}_{S}(v) \geq 4$ and ${\delta}_{\overline{S}}(v) \leq 1$. Then, $\operatorname{Deg}(A(G^*;x)) \geq n_1 + 3 > n + 3 = \operatorname{Deg}(A(G;x))$. If $v_1 \nsim v_2$, let $G_5$ be the connected component of $G^*$ containing $v_1$ and $S=V(G_5)\setminus\{v_1\}$. Hence, $S$ is an exact defensive $3$-alliance in $G^*$, since ${\delta}_{S}(v_2) - {\delta}_{\overline{S}}(v_2) = 3-0$ if $v_2\in S$ and ${\delta}_{S}(v) - {\delta}_{\overline{S}}(v) \ge 4 - 1$ for any $v\in S\setminus\{v_2\}$. Then, $\operatorname{Deg}(A(G^*;x)) \geq n_1 + 3 > n + 3 = \operatorname{Deg}(A(G;x))$. So, it is not possible to have ${\Delta}_1 = 5$.

Assume that ${\Delta}_1 = 4$, then $n_1 = n + 1$. If $G^*$ is a disconnected graph, then there exists a connected component $\langle S^*\rangle$ of $G^*$ such that $\langle S^*\rangle$ is $4$-regular and so, $S^*$ is an exact defensive $4$-alliance in $G^*$. Therefore, $\operatorname{Deg}(A(G^*;x)) = n_1 + 4 > n + 3 = \operatorname{Deg}(A(G;x))$. Thus, $G^*$ is connected, and ${\delta}_1 = 2$ by Theorem \[p:AlliPoly\] iv). So, we have that $G^*$ has exactly $n$ vertices with degree $4$ and another vertex $w$ with degree $2$. Let $v_1,v_2 \in V(G^*)\setminus\{w\}$ with $v_1\neq v_2$, $v_1\sim w$ and $v_2\sim w$. Consider $\{u_1,\ldots,u_{n-2}\} := V(G^*)\setminus \{w,v_1,v_2\}$. Let $G_i$ be the connected component of $\langle V(G^*)\setminus\{u_i\}\rangle \subset G^*$ containing $w$, and $S_i=V(G_i)$, for each $1\le i\le n-2$. Note that $S_i$ is an exact defensive $2$-alliance since ${\delta}_{S_i}(w)-{\delta}_{\overline{S_i}}(w)=2$, for each $1\le i\le n-2$. Note that if $i\neq j$ and $u_j\notin S_i$ then $u_i \in S_j$, and so, $S_i\neq S_j$ since $u_i\notin S_i$; furthermore, if $u_j\in S_i$ then $S_i\neq S_j$ since $u_j\notin S_j$. Then, we obtain that $A_{2}(G^*)\ge n-1$, and thus $A_{3}(G)\ge n-1$. This contradicts Theorem \[p:AlliPoly\] vi) since $G$ is a cubic graph with order $n$. So, it is not possible to have ${\Delta}_1 = 4$.

Now we prove a similar result for ${\Delta}$-regular graphs with ${\Delta}>3$. First, we prove some technical results which will be useful.

\[l:d1=1\] Let $G_1$ be a graph with minimum and maximum degree ${\delta}_1$ and ${\Delta}_1$, respectively, and let $n\ge3$ be a fixed natural number. Assume that $G_1$ has order $n_1 > n$ with exactly $n$ vertices of degree ${\Delta}_1$, and such that its alliance polynomial $A(G_1;x)$ is symmetric. The following statements hold:

1.  [If ${\delta}_1=1$, then $A(G_1;x)$ is not a monic polynomial of degree $2n-n_1+{\Delta}_1$.]{}

2.  [If ${\delta}_1=2$, then we have $2n_1<2{\Delta}_1+n$ or $A(G_1;x)$ is not a monic polynomial of degree $2n-n_1+{\Delta}_1$.]{}

Seeking for a contradiction assume that $A(G_1;x)$ is a monic polynomial with degree $2n-n_1+{\Delta}_1$. By hypothesis, we have $n$ different vertices $v_1,\ldots,v_n$ in $G_1$ with degree ${\Delta}_1$. Denote by $S$ the set $S:=\{v_1,\ldots,v_n\}$. The argument in the proof of Theorem \[t:RegCharact\] gives that $G_1$ is a connected graph, $S$ is an exact defensive -alliance in $G_1$ and there is $w\in S$ with $\overline{S}\subseteq N(w)$. Let $u\in \overline{S}$ with ${\delta}(u)={\delta}_1$.

First assume that ${\delta}_1=1$. So, $S_w:=S\setminus\{w\}$ contains a defensive -alliance since ${\delta}_{S_w}(v)\ge {\Delta}_1 - \big(|\overline{S}\cup\{w\}|-|\{u\}|\big) = {\Delta}_1 - (n_1-n)$ and ${\delta}_{\overline{S}_w}(v)\le |\overline{S}\cup\{w\}|-1 = n_1-n$ for all $v\in S_w$; thus, in $A(G_1;x)$ appears at least one term of degree greater or equal than $2n-n_1+{\Delta}_1$ associated to $S_w$, but this is impossible since $A(G_1;x)$ is monic of degree $2n-n_1+{\Delta}_1$. This is the contradiction we were looking for.

Assume now that ${\delta}_1=2$. Let $w'\in V(G_1)\setminus\{w\}$ with $w'\sim u$. If $w'\in \overline{S}$ then $S_w$ is a defensive -alliance since $u\notin N(v)$ for every $v\in S_w$. This implies a contradiction as above. So, we can assume that $w'\in S_w$. Note that if $w'\nsim w$ then $S_w$ is a defensive -alliance since ${\delta}_{S_w}(w')-{\delta}_{\overline{S_w}}(w') \ge ({\Delta}_1-n_1+n)-(n_1-n)$ and ${\delta}_{S_w}(v)-{\delta}_{\overline{S_w}}(v) \ge ({\Delta}_1-n_1+n)-(n_1-n)$ for all $v\in S_w\setminus\{w'\}$, but this is impossible since $A(G_1;x)$ is a monic polynomial of degree $n_1+{\Delta}_1-2(n_1-n)$. Then, we can assume that $w'\sim w$. Note that if ${\delta}_{\overline{S}}(w')< n_1-n$ then $S_w$ is a defensive -alliance, but this is impossible, too. So, we can assume that $\overline{S} \subseteq N(w')$. Notice that if there is $u'\in S$ with $d(u',\{w,w'\})\ge 2$, then we can check that $S\setminus\{u'\}$ is a defensive -alliance, which is impossible. Thus, we can assume that $S\subseteq N(w)\cup N(w')$; in fact, $$n-2=|S\setminus\{w,w'\}| \le {\delta}_{S\setminus\{w'\}}(w) + {\delta}_{S\setminus\{w\}}(w') = 2[{\Delta}_1 -(n_1-n)-1].$$ Since $S\subseteq N(w)\cup N(w')$, if $n-2=2[{\Delta}_1 -(n_1-n)-1]$ then $S\cap N(w)\cap N(w')=\emptyset$, and $${\delta}_{S\setminus\{w,w'\}}(v) \ge {\Delta}_1-(n_1-n) \text{  and  } {\delta}_{\overline{S\setminus\{w,w'\}}}(v) \le n_1-n,\quad \text{for every } v\in S\setminus\{w,w'\}.$$ Hence, $S\setminus\{w,w'\}$ is a defensive -alliance, which is impossible. Then $n-2 < 2[{\Delta}_1 -(n_1-n)-1]$ and this finishes the proof.

\[l:An+D-2&gt;n\] Let $G_1$ be a graph with minimum and maximum degree $2$ and ${\Delta}_1$, respectively, and let $n\ge3$ be a fixed natural number. Assume that $G_1$ has order $n_1 > n$ with exactly $n$ vertices of degree ${\Delta}_1$, and such that its alliance polynomial $A(G_1;x)$ is symmetric. If $n< 2[{\Delta}_1 -(n_1-n)]$ and $A(G_1;x)$ is a monic polynomial of degree $2n-n_1+{\Delta}_1$, then $A_{2(n-n_1)+{\Delta}_1-2}(G_1)> n$.

By hypothesis, there exist different vertices $v_1,\ldots,v_n$ in $G_1$ with degree ${\Delta}_1$. The arguments in the proof of Lemma \[l:d1=1\] give that $G_1$ is a connected graph where $S:=\{v_1,\ldots,v_n\}$ is the unique exact defensive -alliance in $G_1$ and there are $w,w'\in S$ with $\overline{S}\subset N(w)\cap N(w')$. Note that $S_u:=S\setminus\{u\}$ is a defensive -alliance for any $u\in S$, since for all $v\in S_u$ we have $${\delta}_{S_u}(v)\ge {\Delta}_1 - \big|\overline{S_u}\big| \quad \text{ and } \quad {\delta}_{\overline{S_u}}(v)\le \big|\overline{S_u}\big|=n_1-n+1.$$ Note that ${\delta}_{S}(v)\ge {\Delta}_1-(n_1-n) > n/2$ for every $v\in S$. Since $\langle S\rangle$ is Hamiltonian by Theorem \[Dirac\], we have that $S_u$ induces a connected subgraph for any $u\in S$. Since $S$ is the unique exact defensive -alliance in $G_1$, $S_u$ is an exact defensive -alliance for any $u\in S$. Therefore, we have $A_{{\Delta}_1-2(n_1-n)-2}(G_1)\ge n$.

Denote by $u'$ a vertex of $G_1$ with ${\delta}(u')=2$. Since $v\nsim u'$ for any $v\in S\setminus\{w,w'\}$ we have $|S|-1\ge {\delta}_{S}(v)\ge{\delta}_{S}(w)+1$, and so, ${\delta}_S(w)\le |S|-2$ and there are $u_1,u_2\in S\setminus\{w,w'\}$ with $u_1,u_2\notin N(w)$; then $u_1,u_2\notin N(w)\cap N(w')$. Note that $S\setminus\{u_1,u_2\}$ is a defensive -alliance in $G_1$, since $${\delta}_{S\setminus\{u_1,u_2\}}(w) - {\delta}_{\overline{S\setminus\{u_1,u_2\}}}(w) = {\Delta}_1 - 2{\delta}_{\overline{S\setminus\{u_1,u_2\}}}(w) \ge {\Delta}_1 - 2(n_1-n+1),$$ $${\delta}_{S\setminus\{u_1,u_2\}}(w') - {\delta}_{\overline{S\setminus\{u_1,u_2\}}}(w')  = {\Delta}_1 - 2{\delta}_{\overline{S\setminus\{u_1,u_2\}}}(w') \ge {\Delta}_1 - 2(n_1-n+1),$$ and $${\delta}_{S\setminus\{u_1,u_2\}}(v) - {\delta}_{\overline{S\setminus\{u_1,u_2\}}}(v) \ge {\Delta}_1 - 2( n_1-n+1) \quad \text{ for all } v\in S\setminus\{u_1,u_2,w,w'\}.$$ Then $S\setminus\{u_1,u_2\}$ is an exact defensive -alliance and this finishes the proof.

\[t:Reg4-6\] Let $G$ be a connected ${\Delta}$-regular graph with ${\Delta}\le5$ and $G^*$ another graph. If $A(G^*;x) = A(G;x)$, then $G^*$ is a ${\Delta}$-regular graph with the same order and size of $G$.

If $0\le{\Delta}\le3$, then the result follows from Theorem \[t:Reg0-3\]. Assume that $4\le{\Delta}\le5$. Let $n,n_1$ be the orders of $G,G^*$, respectively, and let ${\delta}_1,{\Delta}_1$ be the minimum and maximum degree of $G^*$, respectively. By Theorem \[t:RegCharact\], $G^*$ is a connected graph and $n_1\ge n$. Seeking for a contradiction assume that $n_1> n$.

Assume first ${\Delta}=4$. By Theorem \[t:RegCharact\] we have $n_1=n+{\Delta}_1-4$, ${\Delta}_1>4$ and ${\Delta}_1+{\delta}_1\le 6$. Thus, we have ${\Delta}_1=5$ and ${\delta}_1=1$, and then $n_1=n+1$. Then, Theorem \[t:RegCharact\] and Lemma \[l:d1=1\] give that $A(G;x)=A(G^*;x)$ is not a monic polynomial of degree $n_1+3=n+4$. This is the contradiction we were looking for, and we conclude $n_1=n$.

Assume now ${\Delta}=5$. By Theorem \[t:RegCharact\] we have $n_1=n+{\Delta}_1-5$, ${\Delta}_1>5$, ${\Delta}_1+{\delta}_1\le 8$, ${\delta}_1+4\le{\Delta}_1$ and ${\delta}_1\equiv {\Delta}_1 (\text{mod } 2)$. Thus, we have the following cases:

Case 1

:   [${\delta}_1=1$ and ${\Delta}_1=7$,]{}

Case 2

:   [${\delta}_1=2$ and ${\Delta}_1=6$.]{}

Lemma \[l:d1=1\] gives that $A(G;x)$ is not a monic polynomial of degree $n+5$ in Case 1; this is the contradiction we were looking for, and we conclude $n_1=n$. In Case 2 we have $n_1=n+1$. Since $A(G;x)$ is a monic polynomial of degree $n+5$, Lemma \[l:d1=1\] gives that $n<10$. Hence, Lemma \[l:An+D-2&gt;n\] gives that $A_{2}(G^*)> n$; however, Theorem \[t:An+D-2=n\] gives $A_{3}(G)=n$. This is the contradiction we were looking for, and we conclude $n_1=n$.

Computing the alliance polynomials for cubic graphs with small order {#sect3}
--------------------------------------------------------------------

In this subsection we compute the alliance polynomial of cubic graphs of small order by using Algorithm \[algorithm\], and find that non-isomorphic cubic graphs of order at most $10$ have different alliance polynomials. By Theorem \[t:Reg0-3\] this implies these cubic graphs are uniquely determined by their alliance polynomial. A similar study on characterization of cubic graphs with small order by their domination polynomials is done in [@AP1], although it obtains a different result.

Computing the alliance polynomial of a graph $G$ on $n$ vertices and $m$ edges by calculating $k_S$ for each connected induced subgraph $\langle S\rangle$ takes time $O(m2^n)$. On ${\Delta}$-regular graphs the complexity is $O(n2^n)$. Note that in order to decreasing this time for small size of $G$ could be used its topology by traveling each connected induced subgraph. Testing whether $\langle S\rangle$ is connected can be done using Depth-First Search (DFS), and this has time complexity $O(m)$. Finding $k_S$ requires $O(n)$ time.

Let $G$ be a cubic graph with order $n$. If $n=4$ then $G$ is isomorphic to $K_4$ and Theorem \[t:Reg0-3\] gives uniqueness. If $n=6$ then $G$ is isomorphic either to $K_{3,3}$ or to the Cartesian product $P_2\Box C_3$; hence, Theorem \[t:Reg0-3\] implies that they are uniquely determined by their alliance polynomial since $A(K_{3,3};x)=6 x^3 + 33 x^5 + 15 x^7 + x^9$ and $A(P_2\Box C_3;x)=6 x^3 + 33 x^5 + 11 x^7 + x^9$. Notice that these alliance polynomials are equal except for the coefficient of $x^7$; it is an interesting fact since many parameters of these graphs are different.

Figure \[fig:ord8\] shows the cubic graphs with order $8$ and Table \[tab:ord8\] their alliance polynomials; since they are different, Theorem \[t:Reg0-3\] gives their uniqueness.

Figure \[fig:ord10\] shows the cubic graphs with order $10$ and Table \[tab:ord10\] their alliance polynomials. Since they are different, Theorem \[t:Reg0-3\] gives their uniqueness.

We say that a graph $G$ is characterized by a graph polynomial $f$ if for every graph $G'$ such that $f(G') = f(G)$ we have that $G'$ is isomorphic to $G$. A set of graphs $K$ is characterized by a graph polynomial $f$ if every graph $G \in K$ is characterized by $f$.

\[p:uniqCub10\] Every cubic graph of order at most $10$ is characterized by its alliance polynomial.

Particularly, by Theorem \[p:AlliPoly\] ii) we have that the cubic graphs of order at most $10$ are characterized by the evaluation at $x=1$ of their alliance polynomials.

\[p:Eval1Cub10\] Two non-isomorphic cubic graphs of order at most $10$ have a different number of connected induced subgraphs.

Here we have proved that a polynomial cannot be the alliance polynomial of both a cubic and a non-cubic graph.

In [@CRST] the authors prove that paths, cycles, complete graphs, complete graphs minus an edge, and stars are all characterized by their alliance polynomials. Here we have proved that a polynomial cannot be the alliance polynomial of both a cubic and a non-cubic graph. In fact, cubic graphs of order at most $10$ are characterized by their alliance polynomials (Proposition \[p:uniqCub10\]).

In [@CRST Proposition 4.1] the authors compare the distinctive power of the alliance polynomial with other well-known graph polynomials, such as the domination polynomial [@AP], the independence polynomial [@GH], the matching polynomial [@F], the characteristic polynomial, the Tutte polynomial [@T], the bivariate chromatic polynomial [@DPT] and the subgraph component polynomial [@TAM]. In fact, this result exhibits for each of these polynomials $p(G;x)$ two graphs $G_1,G_2$ with $p(G_1;x) = p(G_2;x)$ and $A(G_1;x) \neq A(G_2;x)$.

Acknowledgements {#acknowledgements .unnumbered}
================

This work was partly supported by a grant for Mobility of own research program at the University Carlos III de Madrid, a grant from Ministerio de Econom[í]{}a y Competitividad (MTM 2013-46374-P) Spain, and a grant from CONACYT  (CONACYT-UAG I0110/62/10), Mexico.

[99]{}

S. Akbari, S. Alikhani and Y-H. Peng, Characterization of graphs using domination polynomials, [*European J. Combin.*]{} [**31**]{}(7) (2010), 1714–1724.

S. Alikhani and Y-H. Peng, Domination polynomials of cubic graphs of order 10, [*Turkish J. Math.*]{} [**35**]{}(3) (2011), 355–366.

S. Alikhani and Y-H. Peng, Introduction to Domination Polynomial of a Graph, [*Ars Comb.*]{} [**CXIV**]{} (2014), 257-266.

G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, [*Ann. of Math.*]{} [**2**]{}(14) (1912), 42-46.

P. L. Bowers, Negatively curved graph and planar metrics with applications to type, [*Michigan Math. J.*]{} [**45**]{} (1998), 31-53.

J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of Independence Polynomials of Well Covered Graphs, [*J. Alg. Comb.*]{} [**11**]{}(3) (2000), 197-210.

W. Carballosa, Exact Defensive Alliances in Graphs, [*Appl. Math. Sci.*]{} [**7**]{}(74) (2013), 3673-3679.

W. Carballosa, J.C. Hernández-Gómez, O. Rosario and Y. Torres-Nuñez, Computing the strong alliance polynomial of a graph. To appear in [*Invest. Oper.*]{}

W. Carballosa, J. M. Rodríguez, J. M. Sigarreta and Y. Torres-Nuñez, Computing the alliance polynomial of a graph, to appear in [*Ars Comb.*]{} Preprint in http://arxiv.org/abs/1410.2940

W. Carballosa, J. M. Rodríguez, J. M. Sigarreta and Y. Torres-Nuñez, Distinctive power of the alliance polynomial for regular graphs, [*Electron. Notes Discrete Math.*]{} [**46**]{} (2014), 313-320.

Curtin, B., Algebraic characterizations of graph regularity conditions, [*Designs, Codes and Cryptography*]{} [**34**]{}(2-3) (2005), 241-248.

M. DeVos and B. Mohar, An analogue of the Descartes-Euler formula for infinite graph and Higuchi’s conjecture, [*Trans. Amer. Math. Soc.*]{} [**359**]{} (2007), 3275-3286.

K. Dohmen, A. Pönitz, and P. Tittmann, A new two-variable generalization of the chromatic polynomial, [*Discrete Math. Theor. Comput. Sci.*]{} [**6**]{} (2003), 69–90.

E. J. Farrell, An introduction to matching polynomials, [*J. Comb. Theory Ser. B*]{} [**27**]{} (1979), 75-86.

G. W. Flake, S. Lawrence, and C. L. Giles, Efficient Identification of Web Communities. In [*Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*]{} (KDD-2000), (2000), 150-160.

G. H. Fricke, L. M. Lawson, T. W. Haynes, S. M. Hedetniemi and S. T. Hedetniemi, A Note on Defensive Alliances in Graphs, [*Bull. Inst. Combin. Appl.*]{} [**38**]{} (2003), 37-41.

C. D. Godsil and I. Gutman, On the theory of the matching polynomial, [*J. Graph Theory*]{} [**5**]{} (1981), 137-144.

I. Gutman and F. Harary, Generalizations of the matching polynomial, [*Utilitas Math.*]{} [**24**]{} (1983) 97–106.

T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Global defensive alliances in graphs, [*Electron. J. Combin.*]{} [**10**]{} (2003), 139-146.

T. Haynes, D. Knisley, E. Seier, and Y. Zou, A quantitative analysis of secondary RNA structure using domination based parameters on trees, [*BMC bioinformatics*]{}, [**7**]{}:108 (2006).

C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, [*Discrete Math.*]{} [**125**]{} (1994), 219-228.

P. Kristiansen, S. M. Hedetniemi and S. T. Hedetniemi, Alliances in graphs, [*J. Combin. Math. Combin. Comput.*]{} [**48**]{} (2004), 157-177.

T. Kotek and J. A. Makowsky, Recurrence relations for graph polynomials on bi-iterative families of graphs, [*Eur. J. Combin.*]{} [**41**]{} (2014), 47-67. J. A. Makowsky and E. V. Ravve, On the location of roots of graph polynomials, [*Electron. Notes Discrete Math.*]{} [**43**]{} (2013), 201-206.

J. A. Makowsky, E. V. Ravve and N. K. Blanchard, On the location of roots of graph polynomials, [*Eur. J. Combin.*]{} [**41**]{} (2014), 1-19.

M. Powel, Alliance in graph, [*Proceeding presented in th 255 of the United state Military Academy*]{} (2004), 1350-1415.

R. C. Read, An introduction to chromatic polynomials, [*J. Comb. Theory*]{} [**4**]{}(1) (1968), 52–71.

J. M. Rodríguez, J. M. Sigarreta and Y. Torres-Nuñez, Computing the hyperbolicity constant of a cubic graph, [*Int. J. Comp. Math.*]{} [**91**]{}(9) (2014), 1897-1910.

J. A. Rodríguez-Velázquez and J. M. Sigarreta, Global defensive k-aliances in graphs, [*Discr. Appl. Math.*]{} [**157**]{}(2) (2009), 211-218.

J. M. Sigarreta, Upper k-alliances in graphs, [*Int. J. Contemp. Math. Sciences*]{} [**6**]{}(43) (2011), 2121- 2128.

J. M. Sigarreta, I. González-Yero, S. Bermudo and J. A. Rodríguez-Velázquez, Partitioning a graph into offensive k-alliances, [*Discr. Appl. Math.*]{} [**159**]{} (2011), 224-231.

P. Tittmann, I. Averbouch and J.A. Makowsky, The enumeration of vertex induced subgraphs with respect to the number of components, [*European J. Combin.*]{} [**32**]{} (7) (2011), 954–974.

Y. Torres-Nuñez, Alliance polynomial and hyperbolicity in regular graphs, Ph. D. Thesis, Universidad Carlos III de Madrid, Madrid, Spain. 2014. http://orff.uc3m.es/handle/10016/19744

W. T. Tutte, A contribution to the theory of chromatic polynomials, [*Canad. J. Math.*]{} [**6**]{}(80-91) (1954), 3-4.
