#  Forcing and anti-forcing polynomials of a polyomino graph ††thanks:
Supported by the Natural Science Foundation of Ningxia, China (Grant No.
2019AAC03124), and the Science and Technology Research Foundation of the
Higher Education Institutions of Ningxia, China (Grant No. NGY2018-139).

Kai Denga, , Huazhong Lüb, Tingzeng Wuc
a School of Mathematics and Information Science, North Minzu University,
Yinchuan, Ningxia 750021, P. R. China
E-mail<EMAIL_ADDRESS>
b School of Mathematical Sciences, University of Electronic Science and
Technology of China,
Chengdu, Sichuan 610054, P.R. China
E-mail<EMAIL_ADDRESS>
c School of Mathematics and Statistics, Qinghai Nationalities University,
Xining, Qinghai 810007, P.R. China
E-mail<EMAIL_ADDRESS>Corresponding author.

###### Abstract

The forcing number of a perfect matching $M$ in a graph $G$ is the smallest
number of edges inside $M$ that can not be contained in other perfect
matchings. The anti-forcing number of $M$ is the smallest number of edges
outside $M$ whose removal results in a subgraph with a single perfect
matching, that is $M$. Recently, in order to investigate the distributions of
forcing numbers and anti-forcing numbers, the forcing polynomial and anti-
forcing polynomial were proposed, respectively. In this work, the forcing and
anti-forcing polynomials of a polyomino graph are obtained. As consequences,
the forcing and anti-forcing spectra of this polyomino graph are determined,
and the asymptotic behaviors on the degree of freedom and the sum of all anti-
forcing numbers are revealed, respectively.

Key words: Perfect matching; Forcing polynomial; Anti-forcing polynomial;
Polyomino graph

##  1 Introduction

A perfect matching in a graph is a set of independent edges that saturates
each vertex. The perfect matching arose in many fields, such as a dimer
covering in statistical physics [18], a Kekulé structure in quantum chemistry
[7], and a solution for optimal assignment [24], etc. In 1985–1987 Klein and
Randić [19, 28] observed that a few number of fixed double bonds of a Kekulé
structure can determine the whole Kekulé structure, and defined the least
number of fixed double bonds as the _innate degree of freedom_ of this Kekulé
structure. This concept was extended to a perfect matching by Harary et al.
[14] in 1991, and renamed as _forcing number_. From the opposite point of
view, Vukičević and Trinajstié [36, 37] proposed the anti-forcing number of a
graph, that was extended to a single perfect matching in 2015 [22]. Generally,
computing the forcing and anti-forcing numbers of a perfect matching are both
NP-complete[1, 10]. Recently, the forcing polynomial [46] and anti-forcing
polynomial [15] were proposed to investigate the distributions of forcing and
anti-forcing numbers of all perfect matchings, respectively. In this paper, we
will calculate the forcing polynomial and anti-forcing polynomial of a
polyomino graph, respectively.

Suppose graph $G$ has a perfect matching $M$. A subset $S\subseteq M$ is
called a forcing set of $M$ if other perfect matchings in $G$ do not contain
$S$. That is, $M$ is determined by an edge set inside of $M$. Thus the forcing
number of $M$ is the size of a minimum forcing set, denoted by $f(G,M)$. The
_forcing spectrum_ [1, 2] of $G$ is the collection of forcing numbers of all
perfect matchings, denoted by Spec${}_{f}(G)$. The minimum and maximum values
in Spec${}_{f}(G)$ are called the _minimum_ and _maximum forcing numbers_ of
$G$, denoted by $f(G)$ and $F(G)$, respectively. Finding the minimum forcing
number was proved to be a NP-complete problem [2], but the special structure
of graph helps to compute it. The minimum forcing numbers of some special
graphs were obtained, such as $2n\times 2n$ grids [27], hypercubes [30, 13],
$2m\times 2n$ toric grids [30], toric hexagonal systems [38], etc. On the
other hand, the maximum forcing number was considered, such as cylindrical
grids [2, 17], $2m\times 2n$ toric grids [20], 4-8 lattices [17], etc. For a
hexagonal system, Xu et al. [39] confirmed that the maximum forcing number is
equal to the Clar number, that is true for polyomino graphs [47] and
(4,6)-fullerenes [32] as well. The forcing spectra of some graphs were
discussed, such as hypercubes [1], grid graphs [2], tubular boron-nitrogen
fullerene graphs [16], hexagonal systems [42], etc. Especially, Randić,
Vukičević and Gutman [29, 34, 35] calculated the forcing spectra of fullerenes
C60, C70 and C72, showing that the Kekulé structure contributing more to the
stability of molecule often has larger innate degree of freedom. There are few
results on forcing polynomial, Zhao and Zhang [49, 46, 51] considered some
special hexagonal systems, and $2\times n$ and $3\times 2n$ grids. For more
results, see [41, 4, 21, 5, 31, 53, 52, 43].

Let $E(G)$ denote the edge set of a graph $G$, and let $M$ be a perfect
matching of $G$. For a subset $S^{\prime}\subseteq E(G)\setminus M$, if
$G-S^{\prime}$ (the graph obtained by removing all the edges of $S^{\prime}$
from $G$) has a single perfect matching, that is $M$, then $S^{\prime}$ is
named an _anti-forcing set_ of $M$. In other words, $M$ is fixed by an edge
set outside of $M$. The size of a minimum anti-forcing set is named the _anti-
forcing number_ of $M$, denoted by $af(G,M)$. The collection of anti-forcing
numbers of all perfect matchings is called the _anti-forcing spectrum_ of $G$,
denoted by Spec${}_{af}(G)$. The minimum and maximum values in
Spec${}_{af}(G)$ are called _minimum_ and _maximum anti-forcing numbers_ of
$G$, denoted by $af(G)$ and $Af(G)$, respectively. Actually, as early in 1997
Li [23] had described the extremal hexagonal systems of minimal anti-forcing
number 1. The minimum anti-forcing numbers of some chemical graphs were
discussed, such as hexagonal systems [8, 9, 36, 37], catacondensed phenylene
[48], fullerene graphs [40], etc. Recently, Lei et al. [22] proved that the
maximum anti-forcing number is equal to Fries number for a hexagonal system,
that is true for (4,6)-fullerenes [32] as well. Furthermore, Deng and Zhang
[12] showed that the cyclomatic number is an attainable upper bound on the
maximum anti-forcing number, and characterized the extremal graphs.
Afterwards, Shi and Zhang [33] gave another achievable upper bound, and got
the maximum anti-forcing numbers of hypercube and its two variants. The anti-
forcing spectra of some hexagonal systems were confirmed to be continuous,
such as monotonic constructable hexagonal systems [10], catacondensed
hexagonal systems [11], etc. For anti-forcing polynomial, a few number of
graphs are considered, such as extremal hexagonal systems with forcing number
1, and $2\times n$ and $3\times 2n$ grids.

In section 2, as preparations, some basic results on forcing and anti-forcing
numbers are introduced, and some useful properties of the polyomino graph
$G_{n}$ (see Fig. 1(a)) are discussed. In section 3, we get the forcing
polynomial of $G_{n}$, as corollaries, Spec${}_{f}(G_{n})=[n,2n]$, and the
asymptotic behavior of degree of freedom of $G_{n}$ is revealed. In section 4,
we obtain the anti-forcing polynomial of $G_{n}$, as consequences,
Spec${}_{af}(G_{n})=[n,3n]$, and the asymptotic behavior of the sum of all
anti-forcing numbers is showed.

##  2 Preliminaries

(a) $G_{n}$

(b) $H_{n}=G_{n}\ominus\\{v_{0},u_{0}\\}$

Fig. 1: The polyomino graphs $G_{n}$ and $H_{n}$.

A polyomino graph is a 2-edge-connected subgraph of the infinite plane grid
such that the periphery of every interior face is a square. The polyomino
graph is an important plane bipartite graphs, which is studied in many
combinatorial problems [3, 6, 26, 18, 44]. The polyomino graph $G_{n}$ as
shown in Fig. 1(a) consisting of $4n$ squares, that is a subgraph of
$4\times(2n+1)$ grids, and the vertices of $G_{n}$ are labeled by
$u_{0},v_{0},u_{i},v_{i},w_{i},z_{i}$, $i=1,2,\cdots,2n$. The polyomino graph
$H_{n}$ is obtained by removing the leftmost square $s_{1,1}$ from $G_{n}$
(see Fig. 1(b)), that is a subgraph of $4\times 2n$ grids.

The number of perfect matchings of a graph $G$ is denoted by $\Phi(G)$. Let
$G_{0}$ denote the null graph. Then $\Phi(G_{0})=1$. For a perfect matching
$M$, a cycle $C$ is called an $M$-alternating cycle if the edges of $C$ appear
alternately in $M$ and $E(C)\setminus M$. Let $W$ be a set of vertices, and
let $G\ominus W$ denote the subgraph generated by deleting all the vertices of
$W$ and their incident edges from $G$.

###### Lemma 2.1

. For $n\geq 2$,

$\Phi(G_{n})=6\Phi(G_{n-1})-4\Phi(G_{n-2}),$ (2.1)

where $\Phi(G_{0})=1$ and $\Phi(G_{1})=6$.

###### Proof.

Let $M^{\prime}$ be a perfect matching of $H_{n}$. If $u_{1}v_{1}\in
M^{\prime}$, then $w_{1}w_{2},z_{1}z_{2}\in M^{\prime}$. Thus the restriction
of $M^{\prime}$ on
$G_{n-1}=H_{n}\ominus\\{u_{1},v_{1},w_{1},w_{2},z_{1},z_{2}\\}$ is a perfect
matching of $G_{n-1}$. If $u_{1}v_{1}\not\in M^{\prime}$, then $s_{1,2}$ and
$s_{1,4}$ both are $M^{\prime}$-alternating squares, and the restriction of
$M^{\prime}$ on
$H_{n-1}=H_{n}\ominus\\{w_{1},w_{2},u_{1},u_{2},v_{1},v_{2},z_{1},z_{2}\\}$ is
a perfect matching of $H_{n-1}$ (see Fig. 1(b)). Note that there are four
different cases such that $s_{1,2}$ and $s_{1,4}$ both are
$M^{\prime}$-alternating. Therefore

$\Phi(H_{n})=\Phi(G_{n-1})+4\Phi(H_{n-1}).$ (2.2)

Let $M$ be a perfect matching of $G_{n}$. If $u_{0}v_{0}\in M$, then the
restriction of $M$ on $H_{n}=G_{n}\ominus\\{u_{0},v_{0}\\}$ is a perfect
matching of $H_{n}$ (see Fig. 1). If $u_{0}v_{0}\not\in M$, then
$u_{0}u_{1},v_{0}v_{1},w_{1}w_{2},z_{1}z_{2}\in M$, and the restriction of $M$
on $G_{n-1}=G_{n}\ominus\\{u_{0},u_{1},v_{0},v_{1},w_{1},w_{2},$
$z_{1},z_{2}\\}$ is a perfect matching of $G_{n-1}$. So
$\Phi(G_{n})=\Phi(H_{n})+\Phi(G_{n-1})$, we have
$\Phi(H_{n})=\Phi(G_{n})-\Phi(G_{n-1})$ and
$\Phi(H_{n-1})=\Phi(G_{n-1})-\Phi(G_{n-2})$, substituting them into Eq. (2.2),
then Eq. (2.1) is obtained. ∎

###### Theorem 2.2

.

$\Phi(G_{n})=\displaystyle\frac{5-3\sqrt{5}}{10}(3-\sqrt{5})^{n}+\displaystyle\frac{5+3\sqrt{5}}{10}(3+\sqrt{5})^{n}.$
(2.3)

###### Proof.

According to Lemma 2.1, the characteristics equation of recurrence formula
(2.1) is $x^{2}-6x+4=0$, with roots $3\pm\sqrt{5}$. Suppose the general
solution of formula (2.1) is
$\Phi(G_{n})=\lambda_{0}(3-\sqrt{5})^{n}+\lambda_{1}(3+\sqrt{5})^{n}$, by the
initial conditions $\Phi(G_{2})=32$ and $\Phi(G_{3})=168$, we can obtain
$\lambda_{0}=\frac{5-3\sqrt{5}}{10}$ and $\lambda_{1}=\frac{5+3\sqrt{5}}{10}$,
so Eq. (2.3) holds for $n\geq 2$. We can check that the equation also holds
for $n=0,1$, so the proof is completed. ∎

Let $M$ be a perfect matching in graph $G$, and $c(M)$ denote the largest
number of disjoint $M$-alternating cycles. Pachter and Kim [27] showed the
following result by means of the minimax theorem on feedback set [25].

###### Theorem 2.3

[27]. Let $M$ be a perfect matching of a plane bipartite graph $G$. Then
$f(G,M)=c(M)$.

An _$M$ -resonant set_ with respect to a perfect matching $M$ of a polyomino
graph $G$ is a collection of independent $M$-alternating squares. Let $s(M)$
denote the size of a maximal $M$-resonant set. Then the maximum $s(M)$ over
all perfect matchings is called the _Clar number_ of $G$, denoted by $cl(G)$.

###### Theorem 2.4

[47]. Suppose $G$ is a polyomino graph that has a perfect matching. Then
$F(G)=cl(G)$.

###### Lemma 2.5

[45]. Let $C$ be an $M$-alternating cycle with respect to a perfect matching
$M$ in a planar bipartite graph $G$. Then there exists a face in the interior
of $C$ whose periphery is an $M$-alternating cycle.

Suppose $M$ is a perfect matching of a polyomino graph, and $\mathcal{A}$ is a
collection of $M$-alternating cycles. Let
$I(\mathcal{A})=\sum_{C\in\mathcal{A}}I(C)$, where $I(C)$ is the number of
squares in the interior of cycle $C$.

###### Lemma 2.6

. Let $M$ be a perfect matching of $G_{n}$. Then $f(G_{n},M)=s(M)$.

###### Proof.

Let $\mathcal{A}$ be a maximal set of disjoint $M$-alternating cycles such
that $I(\mathcal{A})$ is as small as possible. Then $\mathcal{A}$ is an
$M$-resonant set. Otherwise, $\mathcal{A}$ must contain a non-square cycle
$C$. By Lemma 2.5, there is an $M$-alternating square $s$ in the interior of
$C$. Since each vertex is on the periphery of $G_{n}$,
$\mathcal{A}^{\prime}=(\mathcal{A}\setminus\\{C\\})\cup\\{s\\}$ is another
maximal set of disjoint $M$-alternating cycles, however,
$I(\mathcal{A}^{\prime})<I(\mathcal{A})$, a contradiction. Therefore
$|\mathcal{A}|\leq s(M)$. On the other hand, by Theorem 2.3,
$f(G_{n},M)=|\mathcal{A}|\geq s(M)$. So $f(G_{n},M)=s(M)$. ∎

Suppose that $M$ is a perfect matching in a graph $G$. A _compatible
$M$-alternating set_ $\mathcal{A}^{\prime}$ is a collection of $M$-alternating
cycles such that any two cycles of $\mathcal{A}^{\prime}$ are disjoint, or
overlap only on edges in $M$. Let $c^{\prime}(M)$ denote the size of a maximal
compatible $M$-alternating set.

###### Theorem 2.7

[22]. Suppose that $M$ is a perfect matching in a planar bipartite graph $G$.
Then $af(G,M)=c^{\prime}(M)$.

For a planar bipartite graph, two cycles $C_{1}$ and $C_{2}$ in a compatible
$M$-alternating set $\mathcal{A}^{\prime}$ are called _crossing_ if $C_{1}$
enters the interior of $C_{2}$ from the exterior of $C_{2}$. If any two cycles
of $\mathcal{A}^{\prime}$ are no crossing, then $\mathcal{A}^{\prime}$ is
called _non-crossing_.

###### Lemma 2.8

[22, 12]. Suppose $G$ is a planar bipartite graph that has a perfect matching
$M$. Then there is a non-crossing compatible $M$-alternating set
$\mathcal{A}^{\prime}$ such that $af(G,M)=|\mathcal{A}^{\prime}|$.

(a) $L_{k}$

(b) $W_{1}$, $W_{2}$ and $W_{r}$

Fig. 2: The illustrations of Lemma 2.9, where bold edges belong to a perfect
matching.

The anti-forcing number of a perfect matching $M$ in $G_{n}$ is related with
the number of substructures $L_{k}$ and $W_{r}$ as shown in Fig. 2. $L_{k}$ is
a straight chain with $k$ squares, $1\leq k\leq 2n-1$ and $k$ is odd. The
restriction of $M$ on $L_{k}$ is a perfect matching of $L_{k}$, and the
periphery of $L_{k}$ is an $M$-alternating cycle which is compatible with
$\frac{k-1}{2}$ $M$-alternating squares in its interior (see Fig. 2(a)).
$W_{r}$ is isomorphic to $H_{r}$, the restriction of $M$ on $W_{r}$ is a
perfect matching of $W_{r}$, and $W_{r}$ contains the substructure $L_{2r-1}$
such that the peripheries of $W_{r}$ and $L_{2r-1}$ are non-crossing
compatible $M$-alternating cycles, and both of them are compatible with $r-1$
$M$-alternating squares in their interiors (see Fig. 2(b)).

###### Lemma 2.9

. Let $M$ be a perfect matching in $G_{n}$, and $\mathcal{A}^{\prime}$ be a
maximal non-crossing compatible $M$-alternating set such that
$I(\mathcal{A}^{\prime})$ is as small as possible. Then each $M$-alternating
square must belong to $\mathcal{A}^{\prime}$, and any non-square cycle of
$\mathcal{A}^{\prime}$ either is the periphery of an $L_{k}$ or the periphery
of a $W_{r}$.

###### Proof.

Suppose $s$ is an $M$-alternating square that is not in
$\mathcal{A}^{\prime}$. Then $s$ is not compatible with a cycle
$C\in\mathcal{A}^{\prime}$. Since any two $M$-alternating squares are
compatible with each other, $C$ is a non-square cycle. Therefore
$\mathcal{A}^{\prime\prime}=(\mathcal{A}^{\prime}\setminus\\{C\\})\cup\\{s\\}$
is another maximal non-crossing compatible $M$-alternating set, but
$I(\mathcal{A}^{\prime\prime})<I(\mathcal{A}^{\prime})$, a contradiction. So
each $M$-alternating square must belong to $\mathcal{A}^{\prime}$.

Let $C\in\mathcal{A}^{\prime}$ be a non-square cycle, $M(C)=M\cap E(C)$. Note
that none of these vertical edges $w_{i}u_{i}$ and $v_{j}z_{j}$ for $1\leq
i,j\leq 2n$ belong to $M(C)$, otherwise $s_{\lceil\frac{i}{2}\rceil,2}$ or
$s_{\lceil\frac{j}{2}\rceil,4}$ will be an $M$-alternating square that is not
compatible with $C$ (see Fig. 1(a)). Since $C$ is $M$-alternating, $M(C)$
contains just two vertical edges $u_{i}v_{i}$ and $u_{j}v_{j}(0\leq i<j\leq
2n)$ and $i+j$ is odd. If $i$ is even, then $C=u_{i}u_{i+1}\cdots
u_{j}v_{j}v_{j-1}\cdots v_{i}u_{i}$ is the periphery of an $L_{j-i}$. If $i$
is odd, then $C$ is the periphery of an $L_{j-i}$ or $C=u_{i}w_{i}$
$w_{i+1}u_{i+1}u_{i+2}w_{i+2}w_{i+3}u_{i+3}\cdots
u_{j-1}w_{j-1}w_{j}u_{j}v_{j}z_{j}z_{j-1}v_{j-1}v_{j-2}z_{j-2}z_{j-3}v_{j-3}\cdots
v_{i+1}z_{i+1}z_{i}v_{i}u_{i}$ is the periphery of a
$W_{\lceil\frac{j-i}{2}\rceil}$. ∎

Remark 1. The same as above, we can show that Lemmas 2.6 and 2.9 also hold for
$H_{n}$.

##  3 Forcing polynomials

The _forcing polynomial_ [46] of a graph $G$ is defined as follows :

$F(G,x)=\sum_{M\in\mathcal{M}(G)}x^{f(G,M)},$ (3.1)

where $\mathcal{M}(G)$ is the collection of all perfect matchings of $G$.

By Eq. $(\ref{eq1})$, another expression is immediately obtained:

$F(G,x)=\sum_{i=f(G)}^{F(G)}w(G,i)x^{i},$

where $w(G,i)$ is the number of perfect matchings with the forcing number $i$.

The forcing polynomial can count the number of perfect matchings with the same
forcing number, in other words, the distribution of all forcing numbers is
revealed. Moreover, $\Phi(G)=F(G,1)$, and the _degree of freedom_ of $G$,
$IDF(G)=\frac{d}{dx}F(G,x)|_{x=1}$, i.e. the sum of forcing numbers of all
perfect matchings, which can estimate the resonance energy of a molecule [28].
Obviously, if $G$ is a null graph or a graph has a unique perfect matching,
then $F(G,x)=1$.

The following theorem give a recurrence relation for forcing polynomial of
$G_{n}$.

###### Theorem 3.1

. For $n\geq 3$,

$F(G_{n},x)=(4x^{2}+3x)F(G_{n-1},x)-(8x^{3}+2x^{2})F(G_{n-2},x)+4x^{3}F(G_{n-3},x),$
(3.2)

where $F(G_{0},x)=1,F(G_{1},x)=4x^{2}+2x,F(G_{2},x)=16x^{4}+12x^{3}+4x^{2}$.

###### Proof.

We divide $\mathcal{M}(G_{n})$ in two subsets:
$\mathcal{M}_{1}=\\{M\in\mathcal{M}(G_{n})|u_{0}v_{0}\not\in M\\}$ and
$\mathcal{M}_{2}=\\{M\in\mathcal{M}(G_{n})|u_{0}v_{0}\in M\\}$. If
$M\in\mathcal{M}_{1}$, then
$\\{u_{0}u_{1},v_{0}v_{1},w_{1}w_{2},z_{1}z_{2}\\}\subseteq M$ and $s_{1,1}$
is an $M$-alternating square. Note that the restriction $M^{\prime}$ of $M$ on
$G_{n-1}=G_{n}\ominus\\{u_{0},u_{1},v_{0},v_{1},w_{1},w_{2},z_{1},z_{2}\\}$ is
a perfect matching of $G_{n-1}$. Let $\mathcal{A}^{\prime}$ be a maximum
$M^{\prime}$-resonance set of $G_{n-1}$. Then
$\mathcal{A}^{\prime}\cup\\{s_{1,1}\\}$ is a maximum $M$-resonance set of
$G_{n}$ (see Fig. 1(a)). By Lemma 2.6, $f(G_{n},M)=1+f(G_{n-1},M^{\prime})$.
According to Eq. (3.1),

$\displaystyle\sum_{M\in\mathcal{M}_{1}}x^{f(G_{n},M)}$ $\displaystyle=$
$\displaystyle\sum_{M^{\prime}\in\mathcal{M}(G_{n-1})}x^{1+f(G_{n-1},M^{\prime})}$
(3.3) $\displaystyle=$ $\displaystyle
x\sum_{M^{\prime}\in\mathcal{M}(G_{n-1})}x^{f(G_{n-1},M^{\prime})}=xF(G_{n-1},x).$

Now suppose $M\in\mathcal{M}_{2}$, we divide $\mathcal{M}_{2}$ in two subsets:
$\mathcal{M}_{2,1}=\\{M\in\mathcal{M}_{2}|u_{1}v_{1}\in M\\}$ and
$\mathcal{M}_{2,2}=\\{M\in\mathcal{M}_{2}|u_{1}v_{1}\not\in M\\}$. If
$M\in\mathcal{M}_{2,1}$, then the restriction $M^{\prime\prime}$ of $M$ on
$G_{n-1}=G_{n}\ominus\\{u_{0},u_{1},v_{0},v_{1},w_{1},w_{2},z_{1},z_{2}\\}$ is
a perfect matching of $G_{n-1}$. Similarly,

$\displaystyle\sum_{M\in\mathcal{M}_{2,1}}x^{f(G_{n},M)}=\sum_{M^{\prime\prime}\in\mathcal{M}(G_{n-1})}x^{1+f(G_{n-1},M^{\prime\prime})}=xF(G_{n-1},x).$
(3.4)

If $M\in\mathcal{M}_{2,2}$, then $\\{s_{1,2},s_{1,4}\\}$ is an $M$-resonance
set and the restriction $M^{\prime\prime\prime}$ of $M$ on
$H_{n-1}=G_{n}\ominus\\{u_{0},u_{1},v_{0},v_{1},w_{1},w_{2},z_{1},z_{2},u_{2},v_{2}\\}$
is a perfect matching of $H_{n-1}$ (see Fig. 1). Let
$\mathcal{A}^{\prime\prime\prime}$ be a maximum
$M^{\prime\prime\prime}$-resonance set of $H_{n-1}$. Then
$\mathcal{A}^{\prime\prime\prime}\cup\\{s_{1,2},s_{1,4}\\}$ is a maximum
$M$-resonance set of $G_{n}$. By Lemma 2.6 and Remark 1,
$af(G_{n},M)=2+|\mathcal{A}^{\prime\prime\prime}|=2+f(H_{n-1},M^{\prime\prime\prime})$.
Note that there are four independent subcases such that
$\\{s_{1,2},s_{1,4}\\}$ is an $M$-resonance set, so

$\displaystyle\sum_{M\in\mathcal{M}_{2,2}}x^{af(G_{n},M)}$ $\displaystyle=$
$\displaystyle
4\sum_{M^{\prime\prime\prime}\in\mathcal{M}(H_{n-1})}x^{2+f(H_{n-1},M^{\prime\prime\prime})}$
(3.5) $\displaystyle=$ $\displaystyle 4x^{2}F(H_{n-1},x).$

According to Eqs. (3.3), (3.4) and (3.5),

$\displaystyle F(G_{n},x)$ $\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}(G_{n})}x^{f(G_{n},M)}$ (3.6)
$\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}_{1}}x^{f(G_{n},M)}+\sum_{M\in\mathcal{M}_{2}}x^{f(G_{n},M)}$
$\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}_{1}}x^{f(G_{n},M)}+\sum_{M\in\mathcal{M}_{2,1}}x^{f(G_{n},M)}+\sum_{M\in\mathcal{M}_{2,2}}x^{f(G_{n},M)}$
$\displaystyle=$ $\displaystyle 2xF(G_{n-1},x)+4x^{2}F(H_{n-1},x).$

On the other hand, we divide $\mathcal{M}(H_{n})$ in two subsets:
$\mathcal{N}_{1}=\\{M\in\mathcal{M}(H_{n})|u_{1}v_{1}\in M\\}$ and
$\mathcal{N}_{2}=\\{M\in\mathcal{M}(H_{n})|u_{1}v_{1}\not\in M\\}$. Further,
$\mathcal{N}_{1}$ can be divided into two subsets
$\mathcal{N}_{1,1}=\\{M\in\mathcal{N}_{1}|u_{2}v_{2}\in M\\}$ and
$\mathcal{N}_{1,2}=\\{M\in\mathcal{N}_{1}|u_{2}v_{2}\not\in M\\}$. Similarly,
$\sum_{M\in\mathcal{N}_{1,1}}x^{f(H_{n},M)}=xF(H_{n-1},x)$,
$\sum_{M\in\mathcal{N}_{1,2}}x^{f(H_{n},M)}=xF(G_{n-2},x)$, and
$\sum_{M\in\mathcal{N}_{2}}x^{f(H_{n},M)}=4x^{2}F(H_{n-1},x)$. Therefore

$\displaystyle F(H_{n},x)=(4x^{2}+x)F(H_{n-1},x)+xF(G_{n-2},x).$ (3.7)

By Eq. (3.7) minus Eq. (3.6), we can obtain

$F(H_{n},x)-xF(H_{n-1},x)=F(G_{n},x)-2xF(G_{n-1},x)+xF(G_{n-2},x),$

thus

$4xF(H_{n},x)-4x^{2}F(H_{n-1},x)=4xF(G_{n},x)-8x^{2}F(G_{n-1},x)+4x^{2}F(G_{n-2},x).$
(3.8)

According to Eq. (3.6), $4x^{2}F(H_{n-1},x)=F(G_{n},x)-2xF(G_{n-1},x)$,
substituting it into Eq. (3.8), we have

$4xF(H_{n},x)=(4x+1)F(G_{n},x)-(8x^{2}+2x)F(G_{n-1},x)+4x^{2}F(G_{n-2},x),$

so

$4xF(H_{n-1},x)=(4x+1)F(G_{n-1},x)-(8x^{2}+2x)F(G_{n-2},x)+4x^{2}F(G_{n-3},x),$

substituting it into Eq. (3.6), then Eq. (3.2) is obtained. ∎

By Theorem 3.1, we can deduce an explicit expression as follow.

###### Theorem 3.2

. $F(G_{n},x)=$

$\displaystyle 2^{2n}x^{2n}$ $\displaystyle+$ $\displaystyle
x^{n}\sum_{m=0}^{n-1}\Bigg{(}\sum_{i=max\\{\lceil\frac{n}{3}\rceil,m\\}}^{n}\sum_{j=max\\{\lceil\frac{n-i}{2}\rceil,m+n-2i\\}}^{n-i}\sum_{k=m-(i+2j-n)}^{m}(-1)^{i+2j-n}2^{n+2m-i}$
(3.9) $\displaystyle\cdot 3^{i-j-k}{i\choose j}{j\choose n-i-j}{i-j\choose
k}{i+2j-n\choose m-k}-$
$\displaystyle\sum_{i=max\\{\lceil\frac{n-1}{3}\rceil,m\\}}^{n-1}\sum_{j=max\\{\lceil\frac{n-i-1}{2}\rceil,m+n-2i-1\\}}^{n-i-1}\sum_{k=m-(i+2j-n+1)}^{m}(-1)^{i+2j-n+1}2^{n+2m-i-1}$
$\displaystyle\cdot 3^{i-j-k}{i\choose j}{j\choose n-i-j-1}{i-j\choose
k}{i+2j-n+1\choose m-k}\Bigg{)}x^{m}.$

###### Proof.

For convenience, let $F_{n}:=F(G_{n},x)$. Then the generating function of the
sequence $\\{F_{n}\\}_{n=0}^{\infty}$ is

$\displaystyle
G(t)=\sum_{n=0}^{\infty}F_{n}t^{n}=F_{0}t^{0}+F_{1}t^{1}+F_{2}t^{2}+\sum_{n=3}^{\infty}F_{n}t^{n}.$

By Theorem 3.1,

$\displaystyle G(t)$ $\displaystyle=$ $\displaystyle
F_{0}t^{0}+F_{1}t^{1}+F_{2}t^{2}+(4x^{2}+3x)\sum_{n=3}^{\infty}F_{n-1}t^{n}-(8x^{3}+2x^{2})\sum_{n=3}^{\infty}F_{n-2}t^{n}$
$\displaystyle+4x^{3}\sum_{n=3}^{\infty}F_{n-3}t^{n}$ $\displaystyle=$
$\displaystyle
F_{0}t^{0}+F_{1}t^{1}+F_{2}t^{2}+(4x^{2}+3x)t(\sum_{n=0}^{\infty}F_{n}t^{n}-F_{0}t^{0}-F_{1}t^{1})$
$\displaystyle-(8x^{3}+2x^{2})t^{2}(\sum_{n=0}^{\infty}F_{n}t^{n}-F_{0}t^{0})+4x^{3}t^{3}\sum_{n=0}^{\infty}F_{n}t^{n}$
$\displaystyle=$ $\displaystyle
1-xt+((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})G(t).$

So

$\displaystyle G(t)$ $\displaystyle=$
$\displaystyle\displaystyle\frac{1-xt}{1-((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})}$
$\displaystyle=$
$\displaystyle(1-xt)\sum_{i=0}^{\infty}((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})^{i},$

by the binomial theorem

$\displaystyle\sum_{i=0}^{\infty}((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})^{i}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{\infty}x^{i}t^{i}\sum_{j=0}^{i}{i\choose
j}(4x^{2}t^{2}-(8x^{2}+2x)t)^{j}(4x+3)^{i-j}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{\infty}\sum_{j=0}^{i}\sum_{k=0}^{j}(-1)^{j-k}2^{j+k}{i\choose
j}{j\choose k}(4x+3)^{i-j}(4x+1)^{j-k}x^{i+j+k}t^{i+j+k}$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=\lceil\frac{n-i}{2}\rceil}^{n-i}(-1)^{i+2j-n}2^{n-i}{i\choose
j}{j\choose n-i-j}(4x+3)^{i-j}(4x+1)^{i+2j-n}x^{n}t^{n}.$

Similarly,

$\displaystyle
xt\sum_{i=0}^{\infty}((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})^{i}$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=\lceil\frac{n-i-1}{2}\rceil}^{n-i-1}(-1)^{i+2j-n+1}2^{n-i-1}{i\choose
j}{j\choose n-i-j-1}(4x+3)^{i-j}$
$\displaystyle\cdot(4x+1)^{i+2j-n+1}x^{n}t^{n}.$

Therefore

$\displaystyle(1-xt)\sum_{i=0}^{\infty}((4x^{2}+3x)t-(8x^{3}+2x^{2})t^{2}+4x^{3}t^{3})^{i}$
$\displaystyle=$ $\displaystyle
1+\sum_{n=1}^{\infty}x^{n}\Bigg{(}\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=\lceil\frac{n-i}{2}\rceil}^{n-i}(-1)^{i+2j-n}2^{n-i}{i\choose
j}{j\choose n-i-j}(4x+3)^{i-j}$
$\displaystyle\cdot(4x+1)^{i+2j-n}-\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=\lceil\frac{n-i-1}{2}\rceil}^{n-i-1}(-1)^{i+2j-n+1}2^{n-i-1}{i\choose
j}{j\choose n-i-j-1}$
$\displaystyle\cdot(4x+3)^{i-j}(4x+1)^{i+2j-n+1}\Bigg{)}t^{n}$
$\displaystyle=$ $\displaystyle 1+\sum_{n=1}^{\infty}F_{n}t^{n},$

which implies that

$\displaystyle F_{n}$ $\displaystyle=$ $\displaystyle
x^{n}\Bigg{(}\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=\lceil\frac{n-i}{2}\rceil}^{n-i}(-1)^{i+2j-n}2^{n-i}{i\choose
j}{j\choose n-i-j}(4x+3)^{i-j}(4x+1)^{i+2j-n}$ (3.10)
$\displaystyle-\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=\lceil\frac{n-i-1}{2}\rceil}^{n-i-1}(-1)^{i+2j-n+1}2^{n-i-1}{i\choose
j}{j\choose n-i-j-1}(4x+3)^{i-j}$
$\displaystyle\cdot(4x+1)^{i+2j-n+1}\Bigg{)}.$

Moreover,

$\displaystyle(4x+3)^{i-j}(4x+1)^{i+2j-n}$ $\displaystyle=$
$\displaystyle\sum_{m=0}^{2i+j-n}\sum_{k=m-(i+2j-n)}^{m}3^{i-j-k}4^{m}{i-j\choose
k}{i+2j-n\choose m-k}x^{m},$

thus

$\displaystyle\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=\lceil\frac{n-i}{2}\rceil}^{n-i}(-1)^{i+2j-n}2^{n-i}{i\choose
j}{j\choose n-i-j}(4x+3)^{i-j}(4x+1)^{i+2j-n}$ (3.11) $\displaystyle=$
$\displaystyle\sum_{m=0}^{n}\sum_{i=max\\{\lceil\frac{n}{3}\rceil,m\\}}^{n}\sum_{j=max\\{\lceil\frac{n-i}{2}\rceil,m+n-2i\\}}^{n-i}\sum_{k=m-(i+2j-n)}^{m}(-1)^{i+2j-n}2^{n+2m-i}3^{i-j-k}{i\choose
j}$ $\displaystyle\cdot{j\choose n-i-j}{i-j\choose k}{i+2j-n\choose m-k}x^{m}$
$\displaystyle=$ $\displaystyle
2^{2n}x^{n}+\sum_{m=0}^{n-1}\sum_{i=max\\{\lceil\frac{n}{3}\rceil,m\\}}^{n}\sum_{j=max\\{\lceil\frac{n-i}{2}\rceil,m+n-2i\\}}^{n-i}\sum_{k=m-(i+2j-n)}^{m}(-1)^{i+2j-n}2^{n+2m-i}3^{i-j-k}{i\choose
j}$ $\displaystyle\cdot{j\choose n-i-j}{i-j\choose k}{i+2j-n\choose
m-k}x^{m}.$

Similarly,

$\displaystyle\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=\lceil\frac{n-i-1}{2}\rceil}^{n-i-1}(-1)^{i+2j-n+1}2^{n-i-1}{i\choose
j}{j\choose n-i-j-1}(4x+3)^{i-j}(4x+1)^{i+2j-n+1}$ (3.12) $\displaystyle=$
$\displaystyle\sum_{m=0}^{n-1}\sum_{i=max\\{\lceil\frac{n-1}{3}\rceil,m\\}}^{n-1}\sum_{j=max\\{\lceil\frac{n-i-1}{2}\rceil,m+n-2i-1\\}}^{n-i-1}\sum_{k=m-(i+2j-n+1)}^{m}(-1)^{i+2j-n+1}2^{n+2m-i-1}$
$\displaystyle\cdot 3^{i-j-k}{i\choose j}{j\choose n-i-j-1}{i-j\choose
k}{i+2j-n+1\choose m-k}x^{m}.$

Finally, we can obtain Eq. (3.9) by substituting Eqs. (3.11) and (3.12) into
Eq. (3.10). ∎

By Theorem 3.2, $x^{i}$ is a term of $F(G_{n},x)$ for $i=n,n+1,\ldots,2n$,
thus we have the following corollary.

###### Corollary 3.3

.

  1. (1).

$f(G_{n})=n$, $F(G_{n})=2n$;

  2. (2).

Spec${}_{f}(G_{n})=[n,2n]$.

In the following we calculate the degree of freedom of $G_{n}$, and reveal its
asymptotic behavior with respect to $\Phi(G_{n})$.

###### Theorem 3.4

.

$\displaystyle IDF(G_{n})=-4$ $\displaystyle+$
$\displaystyle\frac{50+22\sqrt{5}}{25}(3-\sqrt{5})^{n}+\frac{13-3\sqrt{5}}{10}n(3-\sqrt{5})^{n}$
(3.13) $\displaystyle+$
$\displaystyle\frac{50-22\sqrt{5}}{25}(3+\sqrt{5})^{n}+\frac{13+3\sqrt{5}}{10}n(3+\sqrt{5})^{n}.$

###### Proof.

According to Theorem 3.1,

$\displaystyle\displaystyle\frac{d}{dx}F(G_{n},x)$ $\displaystyle=$
$\displaystyle(8x+3)F(G_{n-1},x)+(4x^{2}+3x)\displaystyle\frac{d}{dx}F(G_{n-1},x)-(24x^{2}+4x)F(G_{n-2},x)$
$\displaystyle-(8x^{3}+2x^{2})\displaystyle\frac{d}{dx}F(G_{n-2},x)+12x^{2}F(G_{n-3},x)+4x^{3}\displaystyle\frac{d}{dx}F(G_{n-3},x).$

For convenience, let $IDF_{n}:=IDF(G_{n})$. Then

$\displaystyle IDF_{n}$ $\displaystyle=$
$\displaystyle\displaystyle\frac{d}{dx}F(G_{n},x)\Big{|}_{x=1}$
$\displaystyle=$ $\displaystyle
7IDF_{n-1}-10IDF_{n-2}+4IDF_{n-3}+11\Phi_{n-1}-28\Phi_{n-2}+12\Phi_{n-3}.$

By Lemma 2.1,

$\displaystyle IDF_{n}$ $\displaystyle=$ $\displaystyle
7IDF_{n-1}-10IDF_{n-2}+4IDF_{n-3}+11\Phi_{n-1}-3(6\Phi_{n-2}-4\Phi_{n-3})-10\Phi_{n-2}$
$\displaystyle=$ $\displaystyle
7IDF_{n-1}-10IDF_{n-2}+4IDF_{n-3}+8\Phi_{n-1}-10\Phi_{n-2}.$

Therefore

$\displaystyle
IDF_{n+1}=7IDF_{n}-10IDF_{n-1}+4IDF_{n-2}+8\Phi_{n}-10\Phi_{n-1},$

and

$\displaystyle IDF_{n+2}$ $\displaystyle=$ $\displaystyle
7IDF_{n+1}-10IDF_{n}+4IDF_{n-1}+8\Phi_{n+1}-10\Phi_{n}.$

Note that

$\displaystyle 8\Phi_{n+1}-10\Phi_{n}$ $\displaystyle=$ $\displaystyle
8(6\Phi_{n}-4\Phi_{n-1})-10(6\Phi_{n-1}-4\Phi_{n-2})$ $\displaystyle=$
$\displaystyle 6(8\Phi_{n}-10\Phi_{n-1})-4(8\Phi_{n-1}-10\Phi_{n-2})$
$\displaystyle=$ $\displaystyle
6(7IDF_{n}-10IDF_{n-1}+4IDF_{n-2}+8\Phi_{n}-10\Phi_{n-1})$
$\displaystyle-4(7IDF_{n-1}-10IDF_{n-2}+4IDF_{n-3}+8\Phi_{n-1}-10\Phi_{n-2})$
$\displaystyle-6(7IDF_{n}-10IDF_{n-1}+4IDF_{n-2})$
$\displaystyle+4(7IDF_{n-1}-10IDF_{n-2}+4IDF_{n-3})$ $\displaystyle=$
$\displaystyle 6IDF_{n+1}-46IDF_{n}+88IDF_{n-1}-64IDF_{n-2}+16IDF_{n-3},$

so

$IDF_{n+2}=13IDF_{n+1}-56IDF_{n}+92IDF_{n-1}-64IDF_{n-2}+16IDF_{n-3}.$ (3.14)

The characteristics equation of Eq. (3.14) is
$x^{5}-13x^{4}+56x^{3}-92x^{2}+64x-16=0$, whose roots are $x_{0}=1$,
$x_{1}=x_{2}=3-\sqrt{5}$, $x_{3}=x_{4}=3+\sqrt{5}$. Suppose the general
solution of (3.14) is
$IDF_{n}=\lambda_{0}+\lambda_{1}(3-\sqrt{5})^{n}+\lambda_{2}n(3-\sqrt{5})^{n}+\lambda_{3}(3+\sqrt{5})^{n}+\lambda_{4}n(3+\sqrt{5})^{n}$.
According to the initial values $IDF_{4}=5948$, $IDF_{5}=38908$,
$IDF_{6}=244348$, $IDF_{7}=1492092$, and $IDF_{8}=8926204$, we can obtain
$\lambda_{0}=-4$, $\lambda_{1}=\frac{50+22\sqrt{5}}{25}$,
$\lambda_{2}=\frac{13-3\sqrt{5}}{10}$, $\lambda_{3}=\frac{50-22\sqrt{5}}{25}$,
and $\lambda_{4}=\frac{13+3\sqrt{5}}{10}$. Therefore Eq. (3.13) holds for
$n\geq 4$. In fact, (3.13) is true for $n=0,1,2,3$ as well, the proof is
completed. ∎

By Theorems 2.2 and 3.4, we have the following corollary.

###### Corollary 3.5

$\lim\limits_{n\rightarrow\infty}\displaystyle\frac{IDF_{n}}{n\Phi_{n}}=\displaystyle\frac{-5+6\sqrt{5}}{5}.$

##  4 Anti-forcing polynomials

The _anti-forcing polynomial_ [15, 22] of a graph $G$ is defined as below:

$Af(G,x)=\sum_{M\in\mathcal{M}(G)}x^{af(G,M)}.$ (4.1)

Thus the following expression is immediate:

$Af(G,x)=\sum_{i=af(G)}^{Af(G)}u(G,i)x^{i},$

where $u(G,i)$ is the number of perfect matchings with the anti-forcing number
$i$.

The anti-forcing polynomial can count the number of perfect matchings with the
same anti-forcing number, that is, the distribution of all anti-forcing
numbers is showed. If $G$ is a null graph or a graph with a unique perfect
matching, then $Af(G,x)=1$. Obviously, $\Phi(G)=Af(G,1)$, and the sum of the
anti-forcing numbers of all perfect matchings is
$\frac{d}{dx}Af(G,x)\big{|}_{x=1}$.

In the following, a recurrence formula of anti-forcing polynomial of $G_{n}$
is showed. First, some useful local lemmas on $H_{n}$ and $G_{n}$ are
discussed.

###### Lemma 4.1

. Let $n$ be a positive integer, and $0\leq k\leq n-1$, and let
$\mathcal{M}_{2k+1}(H_{n})=\\{M\in\mathcal{M}(H_{n})|u_{2k+1}v_{2k+1}\in M$,
and $u_{j}v_{j}\not\in M$ for $j<2k+1\\}$. Then

$\sum_{M\in\mathcal{M}_{2k+1}(H_{n})}x^{af(H_{n},M)}=(x^{3}+3x^{2})^{k}x^{2}Af(G_{n-1-k},x).$

###### Proof.

Up to isomorphism, $H_{n}$ can be split into two subsystems $H_{k}$ ($H_{0}$
is an empty graph) on the left and $H_{n-k}$ on the right by deleting edges
$u_{2k}u_{2k+1}$ and $v_{2k}v_{2k+1}$ from $H_{n}$ (see Fig. 1(b)). Let
$M\in\mathcal{M}_{2k+1}(H_{n})$. Then the restrictions $M^{\prime}$ and
$M^{\prime\prime}$ of $M$ on $H_{k}$ and $H_{n-k}$ are perfect matchings of
$H_{k}$ and $H_{n-k}$, respectively. Let $\mathcal{A}^{\prime}$ and
$\mathcal{A}^{\prime\prime}$ be maximum non-crossing compatible
$M^{\prime}$-alternating set and $M^{\prime\prime}$-alternating set of $H_{k}$
and $H_{n-k}$ with $I(\mathcal{A}^{\prime})$ and
$I(\mathcal{A}^{\prime\prime})$ as small as possible, respectively. Note that
vertical edges $u_{j}v_{j}\not\in M$ for $j\leq 2k$, by Remark 1,
$\mathcal{A}=\mathcal{A}^{\prime}\cup\mathcal{A}^{\prime\prime}$ is a maximum
non-crossing compatible $M$-alternating set of $H_{n}$. According to Lemma
2.8,

$af(H_{n},M)=|\mathcal{A}^{\prime}|+|\mathcal{A}^{\prime\prime}|=af(H_{k},M^{\prime})+af(H_{n-k},M^{\prime\prime}).$
(4.2)

For $af(H_{k},M^{\prime})$, let $N_{i}$ be the substructure consisting of
three squares $s_{i,2}$, $s_{i,3}$ and $s_{i,4}$ $(i=1,2,\ldots,k)$. Then the
restriction of $M^{\prime}$ on $N_{i}$ is a perfect matching of $N_{i}$.
Recall that $u_{2i-1}v_{2i-1},u_{2i}v_{2i}\not\in M^{\prime}$, there are two
cases to be considered. If $u_{2i-1}u_{2i},v_{2i-1}v_{2i}\in M^{\prime}$, then
$s_{i,2}$, $s_{i,3}$ and $s_{i,4}$ all are $M^{\prime}$-alternating squares.
By Remark 1, $s_{i,2}$, $s_{i,3}$ and $s_{i,4}$ all belong to
$\mathcal{A}^{\prime}$. So the substructure $N_{i}$ contributes 3 to
$af(H_{k},M^{\prime})$. If one of $u_{2i-1}u_{2i}$ and $v_{2i-1}v_{2i}$ is not
in $M^{\prime}$, then there are three possible cases such that only $s_{i,2}$
and $s_{i,4}$ are $M^{\prime}$-alternating squares. Hence $N_{i}$ contributes
2 to $af(H_{k},M^{\prime})$. Suppose there are $r(0\leq r\leq k)$
substructures $N_{i}$ contributing 3 to $af(H_{k},M^{\prime})$, then
$af(H_{k},M^{\prime})=3r+2(k-r)$. Let
$\mathcal{M}^{\prime}(H_{k})=\\{M^{\prime}\in\mathcal{M}(H_{k})|u_{i}v_{i}\not\in
M^{\prime},i=1,2,\ldots,2k\\}$. Then

$\sum_{M^{\prime}\in\mathcal{M}^{\prime}(H_{k})}x^{af(H_{k},M^{\prime})}=\sum_{r=0}^{k}{k\choose
r}3^{k-r}x^{2(k-r)}x^{3r}=(x^{3}+3x^{2})^{k}.$ (4.3)

For $af(H_{n-k},M^{\prime\prime})$, we recall that $u_{2k+1}v_{2k+1}\in
M^{\prime\prime}$, so there must be a vertical edge $u_{2m+2}v_{2m+2}\in
M^{\prime\prime}(k\leq m\leq n-1)$ such that every vertical edge
$u_{j}v_{j}(2k+1<j<2m+2)$ is not in $M^{\prime\prime}$. As a consequence, the
fragment of $H_{n-k}$ between the two vertical edges $u_{2k+1}v_{2k+1}$ and
$u_{2m+2}v_{2m+2}$ forms the substructure $W_{m-k+1}$, which also contains the
substructure $L_{2(m-k)+1}$ (see Fig. 2). Note that
$H_{n-k}\ominus\\{u_{2k+1},v_{2k+1},w_{2k+1},w_{2k+2},z_{2k+1},z_{2k+2}\\}$ is
isomorphic to $G_{n-k-1}$, and the restriction $M^{\prime\prime\prime}$ of
$M^{\prime\prime}$ on $G_{n-k-1}$ is a perfect matching of $G_{n-k-1}$. Let
$\mathcal{A}^{\prime\prime\prime}$ be a maximum non-crossing compatible
$M^{\prime\prime\prime}$-alternating set of $G_{n-k-1}$ with
$I(\mathcal{A}^{\prime\prime\prime})$ as small as possible, and let
$P(W_{m-k+1})$ and $P(L_{2(m-k)+1})$ be peripheries of $W_{m-k+1}$ and
$L_{2(m-k)+1}$, respectively. By Remark 1,
$\mathcal{A}^{\prime\prime\prime}\cup\\{P(W_{m-k+1}),P(L_{2(m-k)+1})\\}$ is a
maximum non-crossing compatible $M^{\prime\prime}$-alternating set of
$H_{n-k}$. By Lemma 2.8,
$af(H_{n-k},M^{\prime\prime})=2+|\mathcal{A}^{\prime\prime\prime}|=2+af(G_{n-k-1},M^{\prime\prime\prime})$.
Let
$\mathcal{M}^{\prime\prime}(H_{n-k})=\\{M^{\prime\prime}\in\mathcal{M}(H_{n-k})|u_{2k+1}$
$v_{2k+1}\in M^{\prime\prime}\\}$. Then

$\displaystyle\sum_{M^{\prime\prime}\in\mathcal{M}^{\prime\prime}(H_{n-k})}x^{af(H_{n-k},M^{\prime\prime})}=\sum_{M^{\prime\prime\prime}\in\mathcal{M}(G_{n-k-1})}x^{2+af(G_{n-k-1},M^{\prime\prime\prime})}=x^{2}Af(G_{n-k-1},x).$
(4.4)

By Eqs. (4.2), (4.3) and (4.4),

$\displaystyle\sum_{M\in\mathcal{M}_{2k+1}(H_{n})}x^{af(H_{n},M)}$
$\displaystyle=$
$\displaystyle\sum_{M^{\prime}\in\mathcal{M}^{\prime}(H_{k}),M^{\prime\prime}\in\mathcal{M}^{\prime\prime}(H_{n-k})}x^{af(H_{k},M^{\prime})+af(H_{n-k},M^{\prime\prime})}$
$\displaystyle=$
$\displaystyle\sum_{M^{\prime}\in\mathcal{M}^{\prime}(H_{k})}x^{af(H_{k},M^{\prime})}\sum_{M^{\prime\prime}\in\mathcal{M}^{\prime\prime}(H_{n-k})}x^{af(H_{n-k},M^{\prime\prime})}$
$\displaystyle=$ $\displaystyle(x^{3}+3x^{2})^{k}x^{2}Af(G_{n-k-1},x).$

∎

The following lemma is the case of Eq. (4.3) for $k=n$.

###### Lemma 4.2

. Let $\mathcal{M}_{0}(H_{n})=\\{M\in\mathcal{M}(H_{n})|u_{j}v_{j}\not\in M$
for $j=1,2,\ldots,2n\\}$. Then

$\sum_{M\in\mathcal{M}_{0}(H_{n})}x^{af(H_{n},M)}=(x^{3}+3x^{2})^{n}.$

###### Lemma 4.3

. Let $n$ be a positive integer, and $0\leq k\leq n-1$,
$\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n})=\\{M\in\mathcal{M}(G_{n})|u_{0}v_{0},u_{2k+1}v_{2k+1}\in
M,$ and $u_{j}v_{j}\not\in M$ for $j=1,2,\ldots,2k\\}$. Then

$\displaystyle\sum_{M\in\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}=((x^{3}+3x^{2})^{k}+(x-1)x^{3k})x^{2}Af(G_{n-k-1},x).$

###### Proof.

Let $M\in\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n})$. Then
$M^{\prime}=M\setminus\\{u_{0}v_{0}\\}$ is a perfect matching of
$H_{n}=G_{n}\ominus\\{u_{0},v_{0}\\}$, and $M^{\prime}$ belongs to
$\mathcal{M}_{2k+1}(H_{n})$ (defined in Lemma 4.1). Let $\mathcal{A}^{\prime}$
be a maximum non-crossing compatible $M^{\prime}$-alternating set of $H_{n}$
with $I(\mathcal{A}^{\prime})$ as small as possible. There are two cases to be
considered. If $u_{2i+1}u_{2i+2}$ and $v_{2i+1}v_{2i+2}$ belong to $M$ for all
$i=0,1,\ldots,k-1$, then there is a substructure $L_{2k+1}$ ($L_{1}$ is the
square $s_{1,1}$) between the vertical edges $u_{0}v_{0}$ and
$u_{2k+1}v_{2k+1}$, whose periphery $P(L_{2k+1})$ is an $M$-alternating cycle
(see Fig. 1(a)). By Lemma 2.9 and Remark 1,
$\mathcal{A}^{\prime}\cup\\{P(L_{2k+1})\\}$ is a maximum compatible
$M$-alternating set of $G_{n}$. By Lemma 2.8,
$af(G_{n},M)=1+|\mathcal{A}^{\prime}|=1+af(H_{n},M^{\prime})$. Suppose there
exists a $j(0\leq j\leq k-1)$ such that $u_{2j+1}u_{2j+2}$ or
$v_{2j+1}v_{2j+2}$ does not belong to $M$, then $\mathcal{A}^{\prime}$ can be
a maximum compatible $M$-alternating set of $G_{n}$, so
$af(G_{n},M)=af(H_{n},M^{\prime})$. Analogously,

$\displaystyle\sum_{M\in\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}$
$\displaystyle=$ $\displaystyle(\sum_{r=0}^{k-1}{k\choose
r}3^{k-r}x^{2(k-r)}x^{3r}+x^{3k+1})x^{2}Af(G_{n-k-1},x)$ $\displaystyle=$
$\displaystyle((x^{3}+3x^{2})^{k}+(x-1)x^{3k})x^{2}Af(G_{n-k-1},x).$

∎

###### Lemma 4.4

. Let
$\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})=\\{M\in\mathcal{M}(G_{n})|u_{0}v_{0}\in
M,u_{j}v_{j}\not\in M$ for $j=1,2,\ldots,2n\\}$. Then

$\sum_{M\in\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}=(x^{3}+3x^{2})^{n}.$

###### Proof.

Let $M\in\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})$. Then
$M^{\prime}=M\setminus\\{u_{0}v_{0}\\}\in\mathcal{M}_{0}(H_{n})$. On the other
hand, if $M^{\prime}\in\mathcal{M}_{0}(H_{n})$, then
$M=M^{\prime}\cup\\{u_{0}v_{0}\\}\in\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})$. So
$|\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})|=|\mathcal{M}_{0}(H_{n})|$. Let
$\mathcal{A}^{\prime}$ be a maximum non-crossing compatible
$M^{\prime}$-alternating set of $H_{n}$ with $I(\mathcal{A}^{\prime})$ as
small as possible. By Lemma 2.9 and Remark 1, $\mathcal{A}^{\prime}$ also is a
maximum compatible $M$-alternating set of $G_{n}$. By Lemma 2.8,
$af(G_{n},M)=af(H_{n},M^{\prime})$. According to Lemma 4.2,

$\sum_{M\in\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}=\sum_{M^{\prime}\in\mathcal{M}_{0}(H_{n})}x^{af(H_{n},M^{\prime})}=(x^{3}+3x^{2})^{n}.$

∎

###### Lemma 4.5

. Let
$\mathcal{M}_{\bar{0}}(G_{n})=\\{M\in\mathcal{M}(G_{n})|u_{0}v_{0}\not\in
M\\}$. Then

$\sum_{M\in\mathcal{M}_{\bar{0}}(G_{n})}x^{af(G_{n},M)}=xAf(G_{n-1},x).$

###### Proof.

Let $M\in\mathcal{M}_{\bar{0}}(G_{n})$. Then
$u_{0}u_{1},v_{0}v_{1},w_{1}w_{2},z_{1}z_{2}\in M$, $s_{1,1}$ is an
$M$-alternating square, and the restriction $M^{\prime}$ of $M$ on
$G_{n-1}=G_{n}\ominus\\{u_{0},u_{1},v_{0},v_{1},w_{1},w_{2},z_{1},z_{2}\\}$ is
a perfect matching of $G_{n-1}$, see Fig. 1(a). Let $\mathcal{A}^{\prime}$ be
a maximum non-crossing compatible $M^{\prime}$-alternating set of $G_{n-1}$
with $I(\mathcal{A}^{\prime})$ as small as possible. By Lemma 2.9,
$\mathcal{A}^{\prime}\cup\\{s_{1,1}\\}$ is a maximum compatible
$M$-alternating set of $G_{n}$. By Lemma 2.8,
$af(G_{n},M)=1+af(G_{n-1},M^{\prime})$. Therefore

$\sum_{M\in\mathcal{M}_{\bar{0}}(G_{n})}x^{af(G_{n},M)}=\sum_{M^{\prime}\in\mathcal{M}(G_{n-1})}x^{1+af(G_{n-1},M^{\prime})}=xAf(G_{n-1},x).$

∎

###### Lemma 4.6

. Let $n$ be a positive integer. Then

$Af(H_{n},x)=x^{2}Af(G_{n-1},x)+(x^{3}+3x^{2})Af(H_{n-1},x).$

###### Proof.

We can divide $\mathcal{M}(H_{n})$ into two subsets:
$\mathcal{M}_{1}(H_{n})=\\{M\in\mathcal{M}(H_{n})|u_{1}v_{1}\in M\\}$ and
$\mathcal{M}_{\bar{1}}(H_{n})=\\{M\in\mathcal{M}(H_{n})|u_{1}v_{1}\not\in
M\\}$ (see Fig. 1(b)). In fact, $\mathcal{M}_{1}(H_{n})$ is the case of Lemma
4.1 for $k=0$. So

$\sum_{M\in\mathcal{M}_{1}(H_{n})}x^{af(H_{n},M)}=x^{2}Af(G_{n-1},x).$

Let $M\in\mathcal{M}_{\bar{1}}(H_{n})$. Then $s_{1,2}$ and $s_{1,4}$ have to
be $M$-alternating squares, and the restriction of $M$ on
$H_{n-1}=H_{n}\ominus\\{w_{1},w_{2},u_{1},u_{2},v_{1},v_{2},z_{1},z_{2}\\}$ is
a perfect matching of $H_{n-1}$. Similar to Lemma 4.1,

$\sum_{M\in\mathcal{M}_{\bar{1}}(H_{n})}x^{af(H_{n},M)}=(x^{3}+3x^{2})Af(H_{n-1},x).$

By Eq. (4.1),

$\displaystyle Af(H_{n},x)=\sum_{M\in\mathcal{M}(H_{n})}x^{af(H_{n},M)}$
$\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}_{1}(H_{n})}x^{af(H_{n},M)}+\sum_{M\in\mathcal{M}_{\bar{1}}(H_{n})}x^{af(H_{n},M)}$
$\displaystyle=$ $\displaystyle
x^{2}Af(G_{n-1},x)+(x^{3}+3x^{2})Af(H_{n-1},x)$

∎

###### Theorem 4.7

. For $n\geq 3$,

$\displaystyle Af(G_{n},x)$ $\displaystyle=$
$\displaystyle(3x^{3}+3x^{2}+x)Af(G_{n-1},x)-(2x^{6}+6x^{5}-x^{4}+3x^{3})Af(G_{n-2},x)$
$\displaystyle+(x^{7}+3x^{6})Af(G_{n-3},x),$

where $Af(G_{0},x)=1$, $Af(G_{1},x)=2x^{3}+3x^{2}+x$ and
$Af(G_{2},x)=4x^{6}+9x^{5}+15x^{4}+3x^{3}+x^{2}$.

###### Proof.

By Lemmas 4.3, 4.4 and 4.5, $\mathcal{M}(G_{n})$ can be divided into $n+2$
subsets: $\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})$, $\mathcal{M}_{\bar{0}}(G_{n})$
and $\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n}),k=0,1,2,\ldots,n-1$. By Eq. (4.1),

$\displaystyle Af(G_{n},x)$ $\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}(G_{n})}x^{af(G_{n},M)}$ (4.5)
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}\sum_{M\in\mathcal{M}_{2k+1}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}+\sum_{M\in\mathcal{M}_{\bar{0}}(G_{n})}x^{af(G_{n},M)}+\sum_{M\in\mathcal{M}_{0}^{u_{0}v_{0}}(G_{n})}x^{af(G_{n},M)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}(x^{3}+3x^{2})^{k}x^{2}Af(G_{n-k-1},x)+x^{2}(x-1)\sum_{k=0}^{n-1}x^{3k}Af(G_{n-k-1},x)$
$\displaystyle+xAf(G_{n-1},x)+(x^{3}+3x^{2})^{n}.$

By Lemmas 4.1 and 4.2,

$\displaystyle Af(H_{n},x)$ $\displaystyle=$
$\displaystyle\sum_{M\in\mathcal{M}(H_{n})}x^{af(H_{n},M)}$ (4.6)
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}\sum_{M\in\mathcal{M}_{2k+1}(H_{n})}x^{af(H_{n},M)}+\sum_{M\in\mathcal{M}_{0}(H_{n})}x^{af(H_{n},M)}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{n-1}(x^{3}+3x^{2})^{k}x^{2}Af(G_{n-k-1},x)+(x^{3}+3x^{2})^{n}.$

Substituting Eq. (4.6) into (4.5), then

$\displaystyle
Af(G_{n},x)=Af(H_{n},x)+xAf(G_{n-1},x)+x^{2}(x-1)\sum_{k=0}^{n-1}x^{3k}Af(G_{n-k-1},x).$

So

$\displaystyle x^{3}Af(G_{n},x)$ $\displaystyle=$ $\displaystyle
x^{3}Af(H_{n},x)+x^{4}Af(G_{n-1},x)$ (4.7)
$\displaystyle+x^{2}(x-1)\sum_{k=0}^{n-1}x^{3(k+1)}Af(G_{n-k-1},x)$

and

$\displaystyle
Af(G_{n+1},x)=Af(H_{n+1},x)+xAf(G_{n},x)+x^{2}(x-1)\sum_{k=0}^{n}x^{3k}Af(G_{n-k},x).$
(4.8)

Subtracting Eq. (4.7) from (4.8),

$\displaystyle Af(G_{n+1},x)$ $\displaystyle=$
$\displaystyle(2x^{3}-x^{2}+x)Af(G_{n},x)-x^{4}Af(G_{n-1},x)$ (4.9)
$\displaystyle+Af(H_{n+1},x)-x^{3}Af(H_{n},x).$

According to Lemma 4.6,

$Af(H_{n+1},x)-x^{3}Af(H_{n},x)=x^{2}Af(G_{n},x)+3x^{2}Af(H_{n},x),$

therefore

$\displaystyle Af(G_{n+1},x)$ $\displaystyle=$
$\displaystyle(2x^{3}-x^{2}+x)Af(G_{n},x)-x^{4}Af(G_{n-1},x)$
$\displaystyle+x^{2}Af(G_{n},x)+3x^{2}Af(H_{n},x)$ $\displaystyle=$
$\displaystyle(2x^{3}+x)Af(G_{n},x)-x^{4}Af(G_{n-1},x)+3x^{2}Af(H_{n},x).$

This implies that

$\displaystyle 3x^{2}Af(H_{n},x)$ $\displaystyle=$ $\displaystyle
Af(G_{n+1},x)-(2x^{3}+x)Af(G_{n},x)+x^{4}Af(G_{n-1},x),$ (4.10)

and

$\displaystyle 3x^{2}Af(H_{n-1},x)$ $\displaystyle=$ $\displaystyle
Af(G_{n},x)-(2x^{3}+x)Af(G_{n-1},x)+x^{4}Af(G_{n-2},x).$ (4.11)

By Lemma 4.6,

$3x^{2}Af(H_{n},x)=3x^{4}Af(G_{n-1})+(x^{3}+3x^{2})3x^{2}Af(H_{n-1},x).$
(4.12)

Substituting Eqs. (4.10) and (4.11) into (4.12), we can obtain the following
recurrence formula

$\displaystyle Af(G_{n+1},x)$ $\displaystyle=$
$\displaystyle(3x^{3}+3x^{2}+x)Af(G_{n},x)-(2x^{6}+6x^{5}-x^{4}+3x^{3})Af(G_{n-1},x)$
$\displaystyle+(x^{7}+3x^{6})Af(G_{n-2},x),$

the proof is completed. ∎

According to Theorem 4.7, we can obtain the following expression.

###### Theorem 4.8

.

$Af(G_{n},x)=R_{n}(x)+Q_{n}(x)+3x^{n+1}+x^{n},$ (4.13)

where $R_{n}(x)$ and $Q_{n}(x)$ are listed in the Appendix.

###### Proof.

Let $Af_{n}:=Af(G_{n},x)$. Then the generating function of the sequence
$\\{Af_{n}\\}_{n=0}^{\infty}$ is

$\displaystyle
P(t)=\sum_{n=0}^{\infty}Af_{n}t^{n}=1+Af_{1}t+Af_{2}t^{2}+\sum_{n=3}^{\infty}Af_{n}t^{n}.$

By Theorem 4.7,

$\displaystyle P(t)$ $\displaystyle=$ $\displaystyle
1+Af_{1}t+Af_{2}t^{2}+(3x^{3}+3x^{2}+x)\sum_{n=3}^{\infty}Af_{n-1}t^{n}$
$\displaystyle-(2x^{6}+6x^{5}-x^{4}+3x^{3})\sum_{n=3}^{\infty}Af_{n-2}t^{n}+(x^{7}+3x^{6})\sum_{n=3}^{\infty}Af_{n-3}t^{n}$
$\displaystyle=$ $\displaystyle
1-x^{3}t+((3x^{3}+3x^{2}+x)t-(2x^{6}+6x^{5}-x^{4}+3x^{3})t^{2}+(x^{7}+3x^{6})t^{3})P(t).$

So

$\displaystyle P(t)$ $\displaystyle=$
$\displaystyle\displaystyle\frac{1-x^{3}t}{1-((3x^{3}+3x^{2}+x)t-(2x^{6}+6x^{5}-x^{4}+3x^{3})t^{2}+(x^{7}+3x^{6})t^{3})}$
$\displaystyle=$
$\displaystyle(1-x^{3}t)\sum_{i=0}^{\infty}((3x^{3}+3x^{2}+x)t-(2x^{6}+6x^{5}-x^{4}+3x^{3})t^{2}+(x^{7}+3x^{6})t^{3})^{i}$
$\displaystyle=$
$\displaystyle(1-x^{3}t)\sum_{i=0}^{\infty}\sum_{j=0}^{i}\sum_{k=0}^{i-j}(-1)^{i-j-k}{i\choose
j}{i-j\choose k}(3x^{3}+3x^{2}+x)^{j}(x^{7}+3x^{6})^{k}$
$\displaystyle\cdot(2x^{6}+6x^{5}-x^{4}+3x^{3})^{i-j-k}t^{2i-j+k}.$

Let $n=2i-j+k$. Then

$\displaystyle P(t)$ $\displaystyle=$ $\displaystyle
1+\sum_{n=1}^{\infty}\Bigg{(}\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=max\\{0,2i-n\\}}^{\lfloor\frac{3i-n}{2}\rfloor}(-1)^{3i-2j-n}{i\choose
j}{i-j\choose n-2i+j}(3x^{3}+3x^{2}+x)^{j}$
$\displaystyle\cdot(x^{7}+3x^{6})^{n-2i+j}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n}+$
$\displaystyle\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=max\\{0,2i-n+1\\}}^{\lfloor\frac{3i-n+1}{2}\rfloor}(-1)^{3i-2j-n+2}{i\choose
j}{i-j\choose n-2i+j-1}x^{3}(3x^{3}+3x^{2}+x)^{j}$
$\displaystyle\cdot(x^{7}+3x^{6})^{n-2i+j-1}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n+1}\Bigg{)}t^{n}$
$\displaystyle=$ $\displaystyle 1+\sum_{n=1}^{\infty}Af_{n}t^{n}.$

Therefore,

$\displaystyle Af_{n}$ $\displaystyle=$
$\displaystyle\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=max\\{0,2i-n\\}}^{\lfloor\frac{3i-n}{2}\rfloor}(-1)^{3i-2j-n}{i\choose
j}{i-j\choose n-2i+j}(3x^{3}+3x^{2}+x)^{j}$
$\displaystyle\cdot(x^{7}+3x^{6})^{n-2i+j}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n}+$
$\displaystyle\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=max\\{0,2i-n+1\\}}^{\lfloor\frac{3i-n+1}{2}\rfloor}(-1)^{3i-2j-n+2}{i\choose
j}{i-j\choose n-2i+j-1}x^{3}(3x^{3}+3x^{2}+x)^{j}$
$\displaystyle\cdot(x^{7}+3x^{6})^{n-2i+j-1}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n+1}.$

Furthermore, we can derive the Eq. (4.13) by using the binomial theorem, more
details are listed in the Appendix. ∎

By Theorem 4.8, $x^{i}$ is a term of $Af(G_{n},x)$ for $i=n,n+1,\ldots,3n$,
thus we have the following corollary.

###### Corollary 4.9

.

  1. (1).

$af(G_{n})=n$, $Af(G_{n})=3n$;

  2. (2).

Spec${}_{af}(G_{n})=[n,3n]$.

By Theorem 4.7, we can obtain the exact expression of the sum over all anti-
forcing number of perfect matchings of $G_{n}$.

###### Theorem 4.10

.

$\displaystyle\displaystyle\frac{d}{dx}Af(G_{n},x)\Big{|}_{x=1}$
$\displaystyle=$
$\displaystyle-3+\displaystyle\frac{150+67\sqrt{5}}{100}(3-\sqrt{5})^{n}+\displaystyle\frac{29-10\sqrt{5}}{20}n(3-\sqrt{5})^{n}$
(4.14)
$\displaystyle+\displaystyle\frac{150-67\sqrt{5}}{100}(3+\sqrt{5})^{n}+\displaystyle\frac{29+10\sqrt{5}}{20}n(3+\sqrt{5})^{n}.$

###### Proof.

Recall that $\Phi(G_{n})=Af(G_{n},1)$, for convenience, let
$\Phi_{n}:=\Phi(G_{n})$ and
$A_{n}:=\displaystyle\frac{d}{dx}Af(G_{n},x)\Big{|}_{x=1}$. By Theorem 4.7,

$\displaystyle
A_{n}=7A_{n-1}-10A_{n-2}+4A_{n-3}+16\Phi_{n-1}-47\Phi_{n-2}+25\Phi_{n-3}.$

According to Lemma 2.1,

$\displaystyle 4A_{n}$ $\displaystyle=$ $\displaystyle
28A_{n-1}-40A_{n-2}+16A_{n-3}+64\Phi_{n-1}-188\Phi_{n-2}+100\Phi_{n-3}$
$\displaystyle=$ $\displaystyle
28A_{n-1}-40A_{n-2}+16A_{n-3}+64\Phi_{n-1}-25(6\Phi_{n-2}-4\Phi_{n-3})-38\Phi_{n-2}$
$\displaystyle=$ $\displaystyle
28A_{n-1}-40A_{n-2}+16A_{n-3}+39\Phi_{n-1}-38\Phi_{n-2}.$

So

$4A_{n+1}=28A_{n}-40A_{n-1}+16A_{n-2}+39\Phi_{n}-38\Phi_{n-1}$

and

$4A_{n+2}=28A_{n+1}-40A_{n}+16A_{n-1}+39\Phi_{n+1}-38\Phi_{n}.$ (4.15)

Note that

$\displaystyle 39\Phi_{n+1}-38\Phi_{n}$ $\displaystyle=$ $\displaystyle
39(6\Phi_{n}-4\Phi_{n-1})-38(6\Phi_{n-1}-4\Phi_{n-2})$ $\displaystyle=$
$\displaystyle 6(39\Phi_{n}-38\Phi_{n-1})-4(39\Phi_{n-1}-38\Phi_{n-2})$
$\displaystyle=$ $\displaystyle
6(28A_{n}-40A_{n-1}+16A_{n-2}+39\Phi_{n}-38\Phi_{n-1})$
$\displaystyle-4(28A_{n-1}-40A_{n-2}+16A_{n-3}+39\Phi_{n-1}-38\Phi_{n-2})$
$\displaystyle-6(28A_{n}-40A_{n-1}+16A_{n-2})+4(28A_{n-1}-40A_{n-2}+16A_{n-3})$
$\displaystyle=$ $\displaystyle
24A_{n+1}-184A_{n}+352A_{n-1}-256A_{n-2}+64A_{n-3},$

substituting it into Eq. (4.15),

$A_{n+2}=13A_{n+1}-56A_{n}+92A_{n-1}-64A_{n-2}+16A_{n-3}.$

This recurrence relation is the same as (3.14), by initial values
$A_{4}=7721$, $A_{5}=50541$, $A_{6}=317565$, $A_{7}=1939901$ and
$A_{8}=11608381$, we can prove Eq. (4.14) for $n\geq 4$. Actually, Eq. (4.14)
also holds for $n=0,1,2,3$, so the proof is completed. ∎

By Theorems 2.2 and 4.10, we can obtain the following asymptotic behavior.

###### Corollary 4.11

.

$\lim\limits_{n\rightarrow\infty}\displaystyle\frac{A_{n}}{n\Phi_{n}}=\displaystyle\frac{5+37\sqrt{5}}{40}.$

## References

  * [1] P. Adams, M. Mahdian, E.S. Mahmoodian, On the forced matching numbers of bipartite graphs, Discrete Math. 281 (2004) 1–12.
  * [2] P. Afshani, H. Hatami, E.S. Mahmoodian, On the spectrum of the forced matching number of graphs, Australas. J. Combin. 30 (2004) 147–160.
  * [3] C. Berge, C. Chen, V. Chvátal, C.S. Seow, Combinatorial properties of polyominoes, Combinatorica 1 (1981) 217–224.
  * [4] Z. Che, Z. Chen, Forcing on perfect matchings-A survey, MATCH Commun. Math. Comput. Chem. 66 (2011) 93–136.
  * [5] Z. Che, Z. Chen, Conjugated circuits and forcing edges, MATCH Commun. Math. Comput. Chem. 69 (2013) 721–731.
  * [6] E.J. Cockayne, Chessboard domination problems, Discrete Math. 86 (1990) 13–20.
  * [7] S. J. Cyvin, I. Gutman, Kekulé structures in benzenoid hydrocarbons (Lecture notes in chemistry 46), Springer Verlag, Berlin, 1988.
  * [8] H. Deng, The anti-forcing number of hexagonal chains, MATCH Commun. Math. Comput. Chem. 58 (2007) 675–682.
  * [9] H. Deng, The anti-forcing number of double hexagonal chains, MATCH Commun. Math. Comput. Chem. 60 (2008) 183–192.
  * [10] K. Deng, H. Zhang, Anti-forcing spectra of perfect matchings of graphs, J. Comb. Optim. 33 (2017) 660–680.
  * [11] K. Deng, H. Zhang, Anti-forcing spectrum of any cata-condensed hexagonal system is continuous, Front. Math. China 12 (2017) 19–33.
  * [12] K. Deng, H. Zhang, Extremal anti-forcing numbers of perfect matchings of graphs, Discrete Appl. Math. 224 (2017), 69–79.
  * [13] A.A. Diwan, The minimum forcing number of perfect matchings in the hypercube, Discrete Math. 342 (2019) 1060–1062.
  * [14] F. Harary, D. Klein, T. Živković, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem. 6 (1991) 295–306.
  * [15] H.K. Hwang, H. Lei, Y. Yeh, H. Zhang, Distribution of forcing and anti-forcing numbers of random perfect matchings on hexagonal chains and crowns (preprint, 2015). http://140.109.74.92/hk/?p=873
  * [16] X. Jiang, H. Zhang, On forcing matching number of boron-nitrogen fullerene graphs, Discrete Appl. Math. 159 (2011) 1581–1593.
  * [17] X. Jiang, H. Zhang, The maximum forcing number of cylindrical grid, toroidal 4-8 lattice and Klein bottle 4-8 lattice, J. Math. Chem. 54 (2016) 18–32.
  * [18] P.W. Kasteleyn, The statistics of dimers on a lattice I: the number of dimer arrangements on a quadratic lattice, Phys. 27 (1961), 1209–1225.
  * [19] D. Klein, M. Randić, Innate degree of freedom of a graph, J. Comput. Chem. 8 (1987) 516–521.
  * [20] S. Kleinerman, Bounds on the forcing numbers of bipartite graphs, Discrete Math. 306 (2006) 66–73.
  * [21] F. Lam, L. Pachter, Forcing number for stop signs, Theor. Comput. Sci. 303 (2003) 409–416.
  * [22] H. Lei, Y. Yeh, H. Zhang, Anti-forcing numbers of perfect matchings of graphs, Discrete Appl. Math. 202 (2016) 95–105.
  * [23] X. Li, Hexagonal systems with forcing single edges, Discrete Appl. Math. 72 (1997) 295–301.
  * [24] L. Lovász, M. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol 29. Amsterdam: North-Holland, 1986.
  * [25] C.L. Lucchesi, D.H. Younger, A minimax theorem for directed graphs, J. Lond. Math. Soc. 17 (1978) 369–374.
  * [26] A. Motoyama, H. Hosoya, King and domino polyominals for polyomino graphs, J. Math. Phys. 18 (1997) 1485–1490.
  * [27] L. Pachter, P. Kim, Forcing matchings on square grids, Discrete Math. 190 (1998) 287–294.
  * [28] M. Randić, D. Klein, in _Mathematical and Computational Concepts in Chemistry_ , ed. by N. Trinajstić (Wiley, New York, 1985), pp. 274–282.
  * [29] M. Randić, D. Vukičević, Kekulé structures of fullerene $C_{70}$, Croat. Chem. Acta 79 (2006) 471–481.
  * [30] M.E. Riddle, The minimum forcing number for the torus and hypercube, Discrete Math. 245 (2002) 283–292.
  * [31] L. Shi, H. Zhang, Forcing and anti-forcing numbers of (3,6)-fullerenes, MATCH Commun. Math. Comput. Chem. 76 (2016) 597–614.
  * [32] L. Shi, H. Wang, H. Zhang, On the maximum forcing and anti-forcing numbers of (4,6)-fullerenes, Discrete Appl. Math. 233 (2017) 187–194.
  * [33] L. Shi, H. Zhang, Tight upper bound on the maximum anti-forcing numbers of graphs, Discrete Math. Theor. Comput. Sci. 19(3) (2017) #9.
  * [34] D. Vukičević, I. Gutman, M. Randić, On instability of fullerene $C_{72}$, Croat. Chem. Acta 79 (2006) 429–436.
  * [35] D. Vukičević, M. Randić, On Kekuklé structures of buckminsterfullerene, Chem. Phys. Lett. 401 (2005) 446–450.
  * [36] D. Vukičević, N. Trinajstié, On the anti-forcing number of benzenoids, J. Math. Chem. 42 (2007) 575–583.
  * [37] D. Vukičević, N. Trinajstié, On the anti-Kekulé number and anti-forcing number of cata-condensed bezenoids, J. Math. Chem. 43 (2008) 719–726.
  * [38] H. Wang, D. Ye, H. Zhang, The forcing number of toroidal polyhexes, J. Math. Chem. 43 (2008) 457–475.
  * [39] L. Xu, H. Bian, F. Zhang, Maximum forcing number of hexagonal systems, MATCH Commun. Math. Comput. Chem. 70 (2013) 493–500.
  * [40] Q. Yang, H. Zhang, Y. Lin, On the anti-forcing number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 74 (2015) 681–700.
  * [41] F. Zhang, X. Li, Hexagonal systems with forcing edges, Discrete Math. 140 (1995) 253–263.
  * [42] H. Zhang, K. Deng, Forcing spectrum of a hexagonal system with a forcing edge, MATCH Commun. Math. Comput. Chem. 73 (2015) 457–471.
  * [43] H. Zhang, D. Ye, W.C. Shiu, Forcing matching numbers of fullerene graphs, Discrete Appl. Math. 158 (2010) 573–582.
  * [44] H. Zhang, F. Zhang, Perfect matchings of polyomino graphs, Graphs Combin. 13 (1997) 295–304.
  * [45] H. Zhang, F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291–311.
  * [46] H. Zhang, S. Zhao, R. Lin, The forcing polynomial of catacondensed hexagonal systems, MATCH Commun. Math. Comput. Chem. 73 (2015) 473–490.
  * [47] H. Zhang, X. Zhou, A maximum resonant set of polyomino graphs, Discuss. Math. Graph Theory 36 (2016) 323–337.
  * [48] Q. Zhang, H. Bian, E. Vumar, On the anti-kekulé and anti-forcing number of cata-condensed phenylenes, MATCH Commun. Math. Comput. Chem. 65 (2011) 799–806.
  * [49] S. Zhao, H. Zhang, Forcing polynomials of benzenoid parallelogram and its related benzenoids, Appl. Math. Comput. 284 (2016) 209–218.
  * [50] S. Zhao, H. Zhang, Anti-forcing polynomials for benzenoid systems with forcing edges, Discrete Appl. Math. 250 (2018) 342–356.
  * [51] S. Zhao, H. Zhang, Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids, J. Math. Chem. 57 (2019) 202–225.
  * [52] X. Zhou, H. Zhang, Clar sets and maximum forcing numbers of hexagonal systems, MATCH Commun. Math. Comput. Chem. 74 (2015) 161–174.
  * [53] X. Zhou, H. Zhang, A minimax result for perfect matchings of a polyomino graph, Discrete Appl. Math. 206 (2016) 165–171.

Appendix

$\displaystyle\sum_{i=\lceil\frac{n}{3}\rceil}^{n}\sum_{j=max\\{0,2i-n\\}}^{\lfloor\frac{3i-n}{2}\rfloor}(-1)^{3i-2j-n}{i\choose
j}{i-j\choose
n-2i+j}(3x^{3}+3x^{2}+x)^{j}(x^{7}+3x^{6})^{n-2i+j}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n}$
$\displaystyle=$ $\displaystyle
x^{n}\sum\limits_{q=0}^{2n}\sum\limits_{i=max\\{n-q,\lceil\frac{n}{3}\rceil\\}}^{n}\sum\limits_{j=max\\{0,2i-n\\}}^{min\\{q+3i-2n,\lfloor\frac{4i-q}{2}\rfloor,\lfloor\frac{3i-n}{2}\rfloor\\}}\sum\limits_{k=max\\{0,\lceil\frac{q+4j-4i}{2}\rceil\\}}^{min\\{j,q+3i-j-2n\\}}\sum\limits_{r=max\\{0,q+4j-k-4i\\}}^{min\\{k,q+3i-k-j-2n\\}}\sum\limits_{m=max\\{0,q+5j+n-k-r-6i\\}}^{min\\{\alpha,q+3i-k-
r-j-2n\\}}\sum\limits_{s=max\\{0,\gamma+n-j-q\\}}^{min\\{\beta,\lfloor\frac{\gamma+6i-5j-n-q}{3}\rfloor\\}}$
$\displaystyle\sum\limits_{l=max\\{0,\gamma+3i-3j-2s-q\\}}^{min\\{\beta-s,\lfloor\frac{\gamma+6i-5j-3s-n-q}{2}\rfloor\\}}{i\choose
j}{i-j\choose\alpha}{j\choose k}{k\choose r}{\alpha\choose m}{\beta\choose
s}{\beta-s\choose l}{\beta-s-l\choose\theta}(-1)^{\beta+l}~{}2^{\beta-
s-l}~{}3^{k+i-j-m-l-\theta}x^{q}$ $\displaystyle=$ $\displaystyle
x^{n}\sum\limits_{q=2}^{2n}\sum\limits_{i=max\\{n-q,\lceil\frac{n}{3}\rceil\\}}^{n}\sum\limits_{j=max\\{0,2i-n\\}}^{min\\{q+3i-2n,\lfloor\frac{4i-q}{2}\rfloor,\lfloor\frac{3i-n}{2}\rfloor\\}}\sum\limits_{k=max\\{0,\lceil\frac{q+4j-4i}{2}\rceil\\}}^{min\\{j,q+3i-j-2n\\}}\sum\limits_{r=max\\{0,q+4j-k-4i\\}}^{min\\{k,q+3i-k-j-2n\\}}\sum\limits_{m=max\\{0,q+5j+n-k-r-6i\\}}^{min\\{\alpha,q+3i-k-
r-j-2n\\}}\sum\limits_{s=max\\{0,\gamma+n-j-q\\}}^{min\\{\beta,\lfloor\frac{\gamma+6i-5j-n-q}{3}\rfloor\\}}$
$\displaystyle\sum\limits_{l=max\\{0,\gamma+3i-3j-2s-q\\}}^{min\\{\beta-s,\lfloor\frac{\gamma+6i-5j-3s-n-q}{2}\rfloor\\}}{i\choose
j}{i-j\choose\alpha}{j\choose k}{k\choose r}{\alpha\choose m}{\beta\choose
s}{\beta-s\choose l}{\beta-s-l\choose\theta}(-1)^{\beta+l}~{}2^{\beta-
s-l}~{}3^{k+i-j-m-l-\theta}x^{q}+3x^{n+1}+x^{n}$ $\displaystyle=$
$\displaystyle R_{n}(x)+3x^{n+1}+x^{n}$
$\displaystyle\sum_{i=\lceil\frac{n-1}{3}\rceil}^{n-1}\sum_{j=max\\{0,2i-n+1\\}}^{\lfloor\frac{3i-n+1}{2}\rfloor}(-1)^{3i-2j-n+2}{i\choose
j}{i-j\choose
n-2i+j-1}x^{3}(3x^{3}+3x^{2}+x)^{j}(x^{7}+3x^{6})^{n-2i+j-1}(2x^{6}+6x^{5}-x^{4}+3x^{3})^{3i-2j-n+1}$
$\displaystyle=$ $\displaystyle
x^{n}\sum\limits_{q=2}^{2n}\sum\limits_{i=max\\{n-q+1,\lceil\frac{n-1}{3}\rceil\\}}^{n-1}\sum\limits_{j=max\\{0,2i-n+1\\}}^{min\\{q+3i-2n,\lfloor\frac{4i-q+2}{2}\rfloor,\lfloor\frac{3i-n+1}{2}\rfloor\\}}\sum\limits_{k=max\\{0,\lceil\frac{q+4j-4i-2}{2}\rceil\\}}^{min\\{j,q+3i-j-2n\\}}\sum\limits_{r=max\\{0,q+4j-k-4i-2\\}}^{min\\{k,q+3i-k-j-2n\\}}\sum\limits_{m=max\\{0,q+5j+n-k-r-6i-3\\}}^{min\\{\alpha-1,q+3i-k-
r-j-2n\\}}\sum\limits_{s=max\\{0,\gamma+n-j-q+1\\}}^{min\\{\beta+1,\lfloor\frac{\gamma+6i-5j-n-q+3}{3}\rfloor\\}}$
$\displaystyle\sum\limits_{l=max\\{0,\gamma+3i-3j-2s-q+2\\}}^{min\\{\beta-s+1,\lfloor\frac{\gamma+6i-5j-3s-n-q+3}{2}\rfloor\\}}{i\choose
j}{i-j\choose\alpha-1}{j\choose k}{k\choose r}{\alpha-1\choose
m}{\beta+1\choose s}{\beta-s+1\choose l}{\beta-
s-l+1\choose\theta-2}(-1)^{\beta+l+2}~{}2^{\beta-s-l+1}~{}3^{k+i-j-
m-l-\theta+2}x^{q}$ $\displaystyle=$ $\displaystyle Q_{n}(x)$

Where $n\geq 1$, $\alpha=n-2i+j$, $\beta=3i-2j-n$, $\gamma=k+m+r$,
$\theta=q+3j+2s+l-k-r-m-3i$.