The maximum forcing number of cylindrical grid, toroidal 4–8 lattice and Klein bottle 4–8 lattice

Abstract

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matchings of G. The smallest cardinality of a forcing set of M is called forced matching number, denoted by f(G, M). Among all perfect matchings of G, the maximum forcing matching number is called the maximum forcing number of G, denoted by F(G). In this paper, we show that the maximum forcing numbers of cylindrical grid $P_{2m}\times C_{2n+1}$ is $m(n+1)$ by choosing a suitable independent set of this graph. This solves an open problem proposed by Afshani et al. (Australas J Combin 30:147–160, 2004). Moreover, we obtain that the maximum forcing numbers of two classes of toroidal 4–8 lattice and two classes of Klein bottle 4–8 lattice are all equal to the number of squares pq.

1 Introduction

For a simple graph G, we say that M is a $perfect \,matching$ of G if it is a set of disjoint edges in G that covers all vertices of G. Each vertex is uniquely paired with another via an edge of M. A forcing set for a perfect matching M of graph G is a subset S of M such that S is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M, and is denoted by f(G, M). The maximum (resp. minimum) forcing number of G is the maximum (resp. minimum) value of forcing numbers of all perfect matchings of G, denoted by F(G) [resp. f(G)]. The forcing spectrum for a graph G is a set collecting the forcing matching numbers of all perfect matchings of G.

In chemistry, the perfect matching is called Kekulé structure. The study of Kekulé structure of benzenoid systems plays an important role in the study of total $\pi$-electron energy, resonance energy and other chemical properties of benzenoid hydrocarbons. The notion of forcing number originally arose in chemistry in 1987 in the study of molecular resonance structures [9], and is called innate degree of freedom in chemistry. Chemists once found that the Kekulé structure with larger innate degree of freedom contributes more to the stability of molecular in [14]. Later in [7], Harary introduced the concept of the forcing number of a perfect matching and of other concepts in graphs. Since then, papers have appeared on the forced orientation number of graphs [3, 6], dominating set [4], geodetics [5], and polynomial [24].

There has been some study on forcing sets and forcing number of perfect matching of some graphs. The benzenoid systems (the carbon skeletons of benzenoid hydrocarbons) with minimum forcing number one were determined in [11, 18–20]. The minimum forcing number of a graph has been extensively studied in [1, 10, 13, 15, 16, 22]. Adams et al. [1] showed that determining smallest forcing set of a perfect matching of a bipartite graph with maximum degree three is an NP-complete problem. Afshani et al. [2] proved that the smallest forcing number problem of graphs is NP-complete for bipartite graphs with maximum degree four.

Recently, the study of maximum forcing number of a graph draws our interest. Xu et al. [17] showed that the maximum forcing number of a hexagonal system is equal to its Clar numbers, applying this result, they obtained that the maximum forcing number of a hexagonal system can be computed in polynomial time. Afshani et al. [2] obtained the maximum forcing numbers of two classes of Cartesian product.

Theorem 1.1

[2] Let $P_m\times P_n$ admit a perfect matching. Then $F(P_m\times P_n)=\lfloor \frac{m}{2}\rfloor \cdot \lfloor \frac{n}{2}\rfloor .$

Theorem 1.2

[2] For any integer $k, n\ge 1$,

$$\begin{aligned} F(P_{2k}\times C_{2n})=kn \quad and \quad F(P_{2k+1}\times C_{2n})=kn+1. \end{aligned}$$

Then they proposed a problem: what is the maximum forcing number of non-bipartite graph $P_{2m}\times C_{2n+1}$?

For some graphs, the forcing spectra of them are presented, such as hypercubes [1], tubular BN-fullerene graph [8], even polygonal chain [21], hexagonal system [23] and $C_3\times P_{2n}$ [12].

The rest of the paper is organized as follows. In Sect. 2, we proposed “deleting an independent set” method to investigate the maximum forcing number of graphs. By this method, we show that the maximum forcing number of the cartesian product of $P_{2m}$ and $C_{2n+1}$ is $m(n+1)$ in Sect. 3, which answers an open problem proposed by Afshani et al. in [2]. In Sect. 4, we first study the distribution of cycles in two classes of toroidal 4–8 lattice after deleting an independent set, then combining Lemma 2.2 obtain that the maximum forcing numbers of them are both equal to the number of squares pq. In the similar way, we present the maximum forcing numbers of two classes of Klein bottle 4–8 lattice in Sect. 5, which are both pq, too.

2 Preliminary

So far, there are no effective method for computing the maximum forcing number of a graph. In this section, we will consider it from the perspective that deleting an independent set S of G and arrive in the aim to delete a forcing set of any perfect matching of G. This idea has already been shown in the paper [13].

The following lemma gives a characterization of forcing set for some perfect matching of a graph.

Lemma 2.1

[2] Let G be a graph and M be a perfect matching of it. Then $S\subseteq M$ is a forcing set of M if and only if it contains at least one edge of each M-alternating cycle.

The following lemma will be often used in the proof of the main results.

Lemma 2.2

Let G be a connected graph admitting a perfect matching. Let S be an independent set of G. If $G-S$ has no alternating cycle about some perfect matching of G, then $F(G)\le |S|.$

Proof

For any perfect matching M of G, let A be the set of all the edges in M which are incident with some vertex in S. We claim that A is a forcing set of M. If not, suppose that there is an M-alternating cycle C in $G-A$ by Lemma 2.1. Since C does not pass through any vertex of S, C is also an M-alternating cycle of $G-S$, a contradiction. So $f(G,M)\le |A|=|S|.$ By the arbitrariness of M, we obtain $F(G)\le |S|$. $\square$

3 The maximum forcing number of $P_{2m}\times C_{2n+1}$

Definition 3.1

The cartesian product of G and H, written $G\times H$, is the graph with vertex set $V(G)\times V(H)$ specified by putting (u, v) adjacent to $(u', v')$ if and only if

• (1) $u=u'$ and $vv'\in E(H)$, or

• (2) $v=v'$ and $uu'\in E(G)$.

Now we show the result of open problem proposed by Afshani et al. in [2].

Theorem 3.2

$F(P_{2m}\times C_{2n+1})= m(n+1).$

Fig. 1

a $P_8\times C_9$ and b unit

Proof

Let $P_{2m}=u_1u_2\cdots u_{2m}$ and $C_{2n+1}=v_1v_2\cdots v_{2n+1}$. Denote the vertices of $P_{2m}\times C_{2n+1}$ by $(u_i,v_j)$ ($1\le i\le 2m$, $1\le j\le 2n+1$). For any i ($1\le i\le 2m$), we call the cycle induced by $\{(u_i,v_j)| 1\le j\le 2n+1\} i$-th cycle. For any k ($1\le k\le m$), let

$$\begin{aligned} M_k=\{(u_{2k-1}, v_i)(u_{2k},v_i)|\;1\le i\le 2n+1\}. \end{aligned}$$

Then $M_0=M_1 \cup M_2 \cup \cdots \cup M_m$ is a perfect matching of $P_{2m}\times C_{2n+1}$. We will illustrate that $f(G,M_0)=m(n+1)$. For any $1\le k\le m$, let

$$\begin{aligned} S_k=\{(u_{2k-1}, v_i)(u_{2k},v_i)|\;i \text{ is } \text{ odd } \text{ and } i\le 2n+1\}. \end{aligned}$$

Let $S=S_1 \cup S_2 \cup \cdots \cup S_m$, then S is contained in no other perfect matchings of $P_{2m}\times C_{2n+1}$. Hence S is a forcing set of $M_0$ with size $m(n+1)$.

Next we show the minimality of S. By contrary, let $S_0$ be any forcing set of $M_0$ and $|S_0|<m(n+1)$, there will be an integer i ($1\le i\le m$) such that $M_i$ has at most n edges of $S_0$ by Pigeonhole Principle. There will be an $M_0$-alternating cycle of size 4 in the subgraph induced by vertices of $(2i-1)$-th cycle and 2i-th cycle. That is there will be $M_0$-alternating cycle in $P_{2m}\times C_{2n+1}-S_0$, by Lemma 2.1, $S_0$ is not a forcing set of $M_0$, a contradiction. Hence S is a minimum forcing set of $M_0$, and $f(P_{2m}\times C_{2n+1}, M_0)=m(n+1)$.

For convenience, we denote the graph in Fig. 1b by unit. Let

$$\begin{aligned} A:=\{(u_i, v_j)|j\ne 2n+1, i \,\, and \,\, j \text{ are } \text{ both } \text{ odd; } \text{ or } j=2n+1,\; i \text{ is } \text{ even }\}, \end{aligned}$$

see Fig. 1a. Then A is an independent set. Let $G=(P_{2m}\times C_{2n+1})-A$. In the following, we claim that G has no alternating cycle about some perfect matching of $P_{2m}\times C_{2n+1}$. In G, the length of every internal face is eight, which is the boundary of the unit. Let C be any cycle of G, obviously C is an even cycle. Let H denote the subgraph of $P_{2m}\times C_{2n+1}$ induced by the vertices on C and inside C. It is easy to see that H can be filled with units one by one from down up and from left to right. Suppose that there are k units in H, denote the subgraph by $H_i$ after adding the i-th unit, then $H=H_k$. In the following, we prove that the number of internal vertices of H is odd by induction.

$H_1$ contain one unit, the number of internal vertex is 1. Suppose that for $i<k$, the number of internal vertices of $H_i$ is odd. Now we show that $H_k$ contains odd number of internal vertices. The k-th unit added to $H_{k-1}$ has two types as Fig. 2. In Fig. 2a, the number of internal vertices of $H_k$ is two more than $H_{k-1}$. In Fig. 2b, the number of internal vertices of $H_k$ is four more than $H_{k-1}$. Therefore, no matter what type it happens, the number of added internal vertex is even, and it does not change the parity of the number of internal vertex in $H_{k-1}$. So the number of internal vertex in C is odd, and there is no perfect matching M of $P_{2m}\times C_{2n+1}$ such that C is M-alternating. By the arbitrariness of C, we know that G has no alternating cycle about some perfect matching of $P_{2m}\times C_{2n+1}$. By Lemma 2.2, $F(P_{2m}\times C_{2n+1})\le m(n+1).$

Fig. 2

Illustration two types of $H_k$ generated from $H_{k-1}$

Summing up, we obtain that $F(P_{2m}\times C_{2n+1})=m(n+1).$ $\square$

4 The maximum forcing number of toroidal 4–8 lattice

4.1 R-type toroidal 4–8 lattice $T_R(p,q,t)$

A R-type toroidal 4–8 lattice is generated from a $p\times q$-rectangle Q of the 4–8 lattice. A $p\times q$-rectangle Q considered here has two horizontal sides and two vertical sides: two horizontal sides pass p octagons centers, and two vertical sides pass q octagons centers (see Fig. 3). In order to form a R-type toroidal 4–8 lattice, first identify two vertical sides of Q to form a tube, then identify the top side of the tube with its bottom side after rotating it through t octagons. Conveniently, we denote this toroidal 4–8 lattice by $T_R(p,q,t)$.

Fig. 3

$T_R(6, 3, 2)$ and the label of vertices

In $T_R(p,q,t)$, all the vertices of it can be covered by squares. If the segment joining centers of two squares parallels horizontal side of Q, we call the two squares are in the same row, if the segment joining centers of two squares parallels vertical side of Q, we call that the two squares are in the same column. From left to right denote all columns by $L_0, \ldots , L_{p-1}$. From down up, denote all row by $R_0, \ldots , R_{q-1}$. Then we denote the square by ij which locates the intersection of $L_{i}$ and $R_{j}$, where $i\in {\mathcal {Z}}_p:=\{0, 1, \ldots , p-1\}$ and $j\in {\mathcal {Z}}_q:=\{0, 1, \ldots , q-1\}$. From the left vertex of square ij anticlockwise, denote the four vertices of it by $a_{ij}$, $b_{ij}$, $c_{ij}$ and $d_{ij}$, respectively.

Now we define p paths $l_0, l_1, \ldots , l_{p-1}$ of $T_R(p,q,t)$. For any i ($0\le i \le p-1$), let

$$\begin{aligned} l_i:=b_{i0}c_{i0}d_{i0}b_{i1}c_{i1}d_{i1} \cdots b_{i,q-1}c_{i,q-1}d_{i,q-1}. \end{aligned}$$

$b_{i0}$ and $d_{i,q-1}$ are the head and tail of $l_i$, respectively. For $l_i$ and $l_j$, if the head of $l_j$ is adjacent to the tail of $l_i$, we say $l_j$ is the successor of $l_i$. In $T_R(p,q,t)$, the successor of $l_i$ is $l_{i+(p-t)}$.

Lemma 4.1

Let $T'_R$ be the graph obtained from $T_R(p,q,t)$ by deleting $A=\{a_{ij}|\;0\le i\le p-1 \text{ and } 0\le j\le q-1\}$. Then the number of cycles in $T'_R$ is $d=(t,p)$.

Proof

All paths $l_i$ ($0\le i\le p-1$) in $T_S(p,q,t)$ constitute $T'_R$. For any cycle C in $T'_R$, suppose that C contains g columns: $l_i, l_{i+(p-t)}, \ldots , l_{i+(g-1)(p-t)}$. Then $l_{i+g(p-t)}$ coincides with $l_i$, and we have

$$\begin{aligned}{}[i+g(p-t)]-i\equiv 0 \quad (mod \,\, p)\Longrightarrow gt\equiv 0\quad (mod \,\, p), \end{aligned}$$

That is, the number of columns that C contains is the minimum integer g which satisfies formula $gt\equiv 0$ (mod p). Since $gt\equiv 0$ (mod p), there exists integer $\lambda$ such that $gt=\lambda p$.

In the following, we first prove that the maximum common divisor of g and $\lambda$ is 1, that is, $(g,\lambda )=1$. Suppose, to the contrary, that $(g,\lambda )=d_1>1$. Assume that $g=d_1g_1$, $\lambda =d_1\lambda _1$. Put $g=d_1g_1$, $\lambda =d_1\lambda _1$ into $gt=\lambda p$, we obtain $g_1t=\lambda _1 p$, which contradicts the minimality of g. Hence $(g,\lambda )=1$.

Since $d=(t,p)$, assume that $t=dt_1$, $p=dp_1$ and $(t_1, p_1)=1$. Put $t=dt_1$ and $p=dp_1$ into $gt=\lambda p$, we obtain $gt_1=\lambda p_1$. We claim that $g=p_1$. Suppose, to the contrary, that $g\ne p_1$, we assume $g=lp_1$.

Case 1. l is fraction. Let $l=\frac{n}{m}$ ($m>1$ and m, n are integer and $(m,n)=1$). Put $g=lp_1$ into $gt_1=\lambda p_1$, we have $\lambda =lt_1$. By $g=lp_1=\frac{n}{m}p_1$, $\lambda =lt_1=\frac{n}{m}t_1$, $(m, n)=1$ and g, $\lambda$ are both integer, we know that m is the common divisor of $p_1$ and $t_1$, which contradicts $(p_1,t_1)=1$.

Case 2. l is integer ($l>1$). Similarly, put $g=lp_1$ into $gt_1=\lambda p_1$, we have $\lambda =lt_1$. Since $g=lp_1$, l is the common divisor of g and $\lambda$, which contradicts $(g,\lambda )=1$.

By Cases 1 and 2, we obtain $g=p_1$.

So the number of cycles is $\frac{p}{g}=\frac{p}{p_1}=d=(p,t).$ $\square$

Lemma 4.2

Let $d=(p,t)$. For $l_i$ ($0\le i\le p-1$) of $T_R(p,q,t)$, any d consecutive paths are on d different cycles.

Proof

We investigate any d consecutive paths $l_i, l_{i+1},\cdots , l_{i+(d-1)}$. Suppose that $l_j$ and $l_k$ are on the same cycle ($i\le j<k\le i+(d-1)$), then there exists integer $\nu$ such that $j+\nu (p-t)\equiv k$ (mod p), that is, $-\nu t\equiv k-j$ (mod p). According to this, there exists integer $\mu$ such that $\mu p-\nu t=k-j$.

By $d=(t,p)$, we assume $t=dt_1$, $p=dp_1$ and $(t_1, p_1)=1$. Put $t=dt_1$, $p=dp_1$ into $\mu p-\nu t=k-j$, we obtain $(\mu p_1-\nu t_1)d=k-j$. Since $1\le k-j\le d-1<d$, then there does not exist integers $\mu$, $p_1$, $\nu$, $t_1$ such that $(\mu p_1-\nu t_1)d=k-j$. So $l_j$ and $l_k$ are on different cycles. By the arbitrariness of j and k, we obtain the conclusion. $\square$

Fig. 4

Illustration the proof of Case 2 by $T_R(9, 3, 3)$

Theorem 4.3

$F(T_R(p, q, t))=pq.$

Proof

First we select an independent set $A'$ of $T_R(p, q, t)$ such that $T_R(p, q, t)-A'$ has no alternating cycle about some perfect matching of $T_R(p, q, t)$. Let $A=\{a_{ij}|\;0\le i\le p-1 \; and \;0\le j\le q-1\}$.

Case 1. $d=(p, t)=1$. Let $A'=A$. We know that all $l_i$ ($0\le i\le p-1$) construct unique cycle in $T_R(p, q, t)-A'$, denoted by C. In $T_R(p, q, t)-C$ there are only isolated vertices $a_{ij}$ ($0\le i\le p-1 \; and \;0\le j\le q-1$). Hence there does not exist alternating cycle about some perfect matching of $T_R(p, q, t)$.

Case 2. $d=(p, t)>1$. Let M be any perfect matching of $T_R(p, q, t)$. In $T_R(p, q, t)-A$, let $l_i$ ($0\le i\le d-1$) be on cycle $C_i$. For any two adjacent cycles, without loss of generality, suppose they are $C_0$ and $C_1$, it is impossible that they are both M-alternating cycles. Since if not, there is no edge of M to cover vertex $a_{10}$. If $C_0$ is not M-alternating (see Fig. 4). We set

$$\begin{aligned} A_1=\{b_{i0}|\; 1\le i\le d-1\}. \end{aligned}$$

For any square which do not contain vertices of $A_1$, select $a_{ij}$ and they constitute $A_2$. Let $A'=A_1\cup A_2.$ In $T_R(p, q, t)-A'$, there is unique cycle $C_0$ and there does not exist M-alternating cycle. If $C_1$ is not M-alternating, let

$$\begin{aligned} A'_1=\{b_{i0}|\; 2\le i\le d\}. \end{aligned}$$

For any square which do not contain vertices of $A'_1$, select $a_{ij}$ and they constitute $A'_2$. Let $A'=A'_1\cup A'_2.$ In $T_R(p, q, t)-A'$, there is unique cycle $C_1$ and there does not exist M-alternating cycle.

Combining Cases 1, 2 and Lemma 2.2, we can obtain that

$$\begin{aligned} F(T_R(p, q, t))\le pq. \end{aligned}$$

On the other hand, we can find perfect matching $M_0$ of $T_R(p, q, t)$ such that $f(T_R(p, q, t), M_0)\ge pq$: the restriction of $M_0$ on each square of $T_R(p, q, t)$ is $M_0$-alternating. Since there are pq independent $M_0$-alternating squares, by Lemma 2.1, $f(T_R(p, q, t), M_0)\ge pq$.

Summing up, we can obtain $F(T_R(p, q, t))=pq.$ $\square$

4.2 S-type toroidal 4–8 lattice $T_S(p,q,t)$

A S-type toroidal 4–8 lattice is generated from a $p\times q$ parallelogram P of the 4–8 lattice. A $p\times q$-parallelogram P considered here has two horizontal sides and two lateral sides: two lateral sides pass q continuous octagons centers; two horizontal sides pass p pairs squares and octagons centers. In order to form S-type toroidal 4–8 lattice: first identify two lateral sides of P to form a tube, then identify the top side of the tube with its bottom side after rotating it through t pairs squares and octagons. Conveniently we denote S-type toroidal 4–8 lattice by $T_S(p,q,t)$.

In $T_S(p,q,t)$, all the vertices of it can be covered by squares. If the segment joining centers of two squares parallels horizontal side of P, we call the two squares are in the same row; If the segment joining centers of two squares parallels lateral side of P, we call the two squares are in the same column. From left to right denote all columns by $L_0, L_1,\cdots , L_{p-1}$. From down up, denote all rows by $R_0, R_1, \cdots , R_{q-1}$. Thus we denote the square by ij which locates the intersection of $L_i$ and $R_j$, where $i\in {\mathcal {Z}}_p:=\{0, 1, \cdots , p-1\}$ and $j\in {\mathcal {Z}}_q:=\{0, 1, \cdots , q-1\}$. From the left-upper vertex of square ij anticlockwise, denote the four vertices of it by $a_{ij}$, $b_{ij}$, $c_{ij}$ and $d_{ij}$, respectively. See Fig. 5.

Fig. 5

$T_S(6,3,1)$ and the label of vertex

We denote path $d_{i0}b_{i1}c_{i1}d_{i1}b_{i2}c_{i2}d_{i2}\cdots b_{i,q-1}c_{i,q-1}d_{i,q-1}b_{i0}c_{i0}$ by ${\mathcal {I}}_i$ ($0\le i\le p-1$). The vertices $d_{i0}$ and $c_{i0}$ are called the head and tail of ${\mathcal {I}}_i$, respectively. For ${\mathcal {I}}_i$ and ${\mathcal {I}}_j$, if the head of ${\mathcal {I}}_j$ is adjacent to the tail of ${\mathcal {I}}_i$, we say ${\mathcal {I}}_j$ is the successor of ${\mathcal {I}}_i$. The successor of ${\mathcal {I}}_i$ is ${\mathcal {I}}_{i+(p-t)}$ in $T_S(p,q,t)$.

And denote path $d_{i0}a_{i0}c_{i-1,1}d_{i-1,1}a_{i-1,1}c_{i-2,2}d_{i-2,2}a_{i-2,2}\cdots c_{i-(q-1),q-1}d_{i-(q-1),q-1}a_{i-(q-1),q-1}c_{i-q,0}$ by ${\mathcal {II}}_i$ ($0\le i\le p-1$). The vertices $d_{i0}$ and $c_{i-q,0}$ are called the head and tail of ${\mathcal {II}}_i$, respectively. For ${\mathcal {II}}_i$ and ${\mathcal {II}}_j$, if the head of ${\mathcal {II}}_j$ is adjacent to the tail of ${\mathcal {II}}_i$, we say ${\mathcal {II}}_j$ is the successor of ${\mathcal {II}}_i$. The successor of ${\mathcal {II}}_i$ is ${\mathcal {II}}_{i+(p-q-t)}$ in $T_S(p,q,t)$.

Lemma 4.4

Let $T'$ be the graph obtained from $T_S(p,q,t)$ by deleting $A=\{a_{ij}\mid 0\le i\le p-1 \text{ and } 0\le j\le q-1\}.$ Then the number of cycles in $T'$ is $d=(t,p).$

Lemma 4.5

Let $d=(t,p)$. For ${\mathcal {I}}_i$ ($0\le i\le p-1$) of $T_S(p,q,t)$, any d consecutive paths are on d different cycles.

The proof of Lemmas 4.4 and 4.5 is the same as Lemmas 4.1 and 4.2 respectively.

Lemma 4.6

Let $T_0$ be the graph obtained from $T_S(p,q,t)$ by deleting $B=\{b_{ij}|\;0\le i\le p-1 \; and\; 0\le j\le q-1\}$. Then the number of cycles in $T_0$ is $d=(p, \;t+q)$.

Proof

Obviously $T_0$ is the induced graph of p paths ${\mathcal {II}}_0$, ${\mathcal {II}}_1,\ldots , {\mathcal {II}}_{p-1}$. For any cycle C in $T_0$, suppose that C contains g paths: ${\mathcal {II}}_i, {\mathcal {II}}_{i+(p-q-t)},\ldots , {\mathcal {II}}_{i+(g-1)(p-q-t)}$, where ${\mathcal {II}}_{i+g(p-q-t)}$ coincides with ${\mathcal {II}}_i$. So we have

$$\begin{aligned} i+g(p-q-t)-i\equiv 0\;(mod\, p)\rightarrow g(q+t)\equiv 0\;(mod\, p). \end{aligned}$$

That is, the number of column that C contains is the minimum integer g which satisfies formula $g(q+t)\equiv 0 (mod\; p)$. For $g(q+t)\equiv 0\;(mod\; p)$, there exists integer $\lambda$ such that $g(q+t)=\lambda p$.

In the following, we prove that $(g,\lambda )=1$. Suppose, to the contrary, that $(g,\lambda )=d_1>1$. Let $g=d_1f_1$, $\lambda =\lambda _1d_1$ and $(g_1, d_1)=1$. Put $g=d_1f_1$ and $\lambda =\lambda _1d_1$ into $g(q+t)=\lambda p$ and obtain $g_1(q+t)=\lambda _1p$, which contradicts the minimality of g. Hence $(g,\lambda )=1$.

Since $d=(t+q,p)$, assume that $t+q=t_1d$, $p=dp_1$ and $(t_1,p_1)=1$. Put $t+q=t_1d$ and $p=dp_1$ into $g(q+t)=\lambda p$, we obtain $gt_1=\lambda p_1$. We claim $g=p_1$. Suppose, to the contrary, that $g\ne p_1$, then assume $g=lp_1$.

Case 1. l is fraction. Let $l=\frac{n}{m}$ ($m>1$ and m n are integer and $(m,n)=1$). Put $g=lp_1$ into $gt_1=\lambda p_1$, we have $\lambda =lt_1$. Since $(m,n)=1$, $g=lp_1=\frac{n}{m}p_1$, $\lambda =lt_1=\frac{n}{m}t_1$ and g, $\lambda$ are both integer, we know that m is the common divisor of $p_1$ and $t_1$, which contradicts that $(p_1, t_1)=1$.

Case 2. l is integer ($l>1$). Similarly, put $g=lp_1$ into $gt_1=\lambda p_1$ and obtain $\lambda =lt_1$. By $g=lp_1$ and $\lambda =lt_1$, we know that l is common divisor of g and $\lambda$, which contradicts $(g,\lambda )=1$.

By Cases 1 and 2, we obtain $g=p_1$. By the arbitrariness of cycle C, we have the number of cycles in $T_0$ is $\frac{p}{g}=\frac{p}{p_1}=d=(p,t+q)$. $\square$

Lemma 4.7

Let $d=(p, t+q)$. For ${\mathcal {II}}_i$ ($0\le i\le p-1$) of $T_S(p,q,t)$, any d consecutive paths are on d different cycles.

Proof

We investigate d consecutive paths: ${\mathcal {II}}_i$, ${\mathcal {II}}_{i+1}, \ldots , {\mathcal {II}}_{i+(d-1)}$. By contrary, suppose that ${\mathcal {II}}_j$ and ${\mathcal {II}}_k$ are on the same cycle ($i\le j<k\le i+d-1$), then there exists $\nu$ such that $j+\nu (p-q-t)\equiv k$ (mod p), that is, $k-j\equiv -\nu (q+t)$ (mod p). Thus there is some integer $\mu$ such that $k-j=\mu p-\nu (q+t)$. In what follows, we prove that it is impossible. By $d=(p,t+q)$, we assume that $t+q=t_1d$, $p=p_1d$ and $(t_1, p_1)=1$. Put $t+q=dt_1$ and $p=p_1d$ into $k-j=\mu p-\nu (q+t)$, we have $k-j=(\mu p_1-\nu t_1)d$. Since $1\le k-j\le d-1<d$, then there does not exist integers $\nu , p_1, \mu , t$, such that $(\mu p_1-\nu t_1)d=k-j$. Therefore, ${\mathcal {II}}_j$ and ${\mathcal {II}}_k$ are on different cycles. By the arbitrariness of j and k, we obtain the conclusion. $\square$

Lemma 4.8

For $p>1$ and $q>1$, $F(T_S(p,q,t))\le pq.$

Proof

We select an independent set $A_0$ such that $T_S(p, q, t)-A_0$ has no alternating cycle about some perfect matching of $T_S(p, q, t)$. Conveniently, let $A=\{a_{ij}|\;0\le i\le p-1 \; and \;0\le j\le q-1\}$.

Case 1. $d=(p, t)=1$.

Let $A_0=A$. We know that all ${\mathcal {I}}_i$ ($0\le i\le p-1$) construct the unique cycle C in $T_S(p, q, t)-A_0$. However, in $T_S(p, q, t)-C$ there are only isolated vertices $a_{ij}$ ($1\le i\le p-1 \; and \;1\le j\le q-1$). Hence there does not exist alternating cycle about some perfect matching of $T_S(p, q, t)$.

Case 2. $d=(p, t)>1$.

Let M be any perfect matching of $T_S(p, q, t)$. In $T_S(p, q, t)-A$, let ${\mathcal {I}}_i$ be on cycle $C_i$ ($0\le i\le p-1$). For any two adjacent cycles, without loss of generality, suppose they are $C_0$ and $C_1$, it is impossible that they are both M-alternating cycles. Since if not, there is no edge of M to cover vertex $a_{10}$. If $C_0$ is not M-alternating, we set

$$\begin{aligned} A_1=\{b_{i1}|\; 1\le i\le d-1\}. \end{aligned}$$

For any square of the rest which do not contain vertices in $A_1$, select $a_{ij}$ and they constitute $A_2$. Let $A_0=A_1\cup A_2.$ In $T_R(p, q, t)-A_0$, there is unique cycle $C_0$ and there does not exist M-alternating cycle. If $C_1$ is not M-alternating cycle, let

$$\begin{aligned} A'_1=\{b_{i1}|\;2\le i\le d\}. \end{aligned}$$

For any square of the rest which do not contain vertices in $A'_1$, select $a_{ij}$ and they constitute $A'_2$. Let $A_0=A'_1\cup A'_2.$ In $T_R(p, q, t)-A_0$, there is unique cycle $C_1$ and there does not exist M-alternating cycle.

Combining Cases 1, 2 and Lemma 2.2, we can obtain that $F(T_S(p, q, t))\le pq.$ $\square$

For convenience, we call the cycles generated by ${\mathcal {I}}_i$ (resp. ${\mathcal {II}}_i$) ($0\le i\le p-1$) ${\mathcal {I}}$-type (resp. ${\mathcal {II}}$-type).

Lemma 4.9

For $q=1$, $F(T_S(p,q,t))\le p$.

Proof

Suppose that the number of ${\mathcal {I}}$-type cycles is $d_1=(p,t)$ and the number of ${\mathcal {II}}$-type cycles is $d_2=(p, t+1)$ by Lemmas 4.4 and 4.6. Obviously $d_1\ne d_2$.

If $d_1>d_2$ (see Fig. 6), let $A_1=\{a_{00}, b_{00}, a_{10}, b_{10}, \ldots , a_{d_1-1,0}, b_{d_1-1,0}\}.$ Let ${\mathcal {L}}_1$ be the set of paths which are all successors of ${\mathcal {I}}_0, {\mathcal {I}}_1, \ldots , {\mathcal {I}}_{d_1-1}$. Let

$$\begin{aligned} A_2=\{a_{i0}|\;\; {\mathcal {I}}_i\notin {\mathcal {L}}_1 \quad and \quad d_1\le i\le p-1\}. \end{aligned}$$

Let $A=A_1\cup A_2$. In $T_S(p, 1, t)-A$, all ${\mathcal {I}}$-type cycles and ${\mathcal {II}}$-type cycles are destroyed. There are no alternating cycles about some perfect matching of $T_S(p, 1, t)$.

Fig. 6

Illustration the proof of the case $d_1>d_2$ by $T_S(6,1,3)$

If $d_2>d_1$ (see Fig. 7), let $A'_1=\{a_{00}, b_{p-1, 0}, a_{10}, b_{00}, a_{20}, b_{10}, \ldots , a_{d_2-1,0}, b_{d_2-2,0}\}.$ Let ${\mathcal {L}}_2$ be the set of paths which are all ancestors of ${\mathcal {II}}_0, {\mathcal {II}}_1, \ldots , {\mathcal {II}}_{d_2-1}$. Let

$$\begin{aligned} A'_2=\{b_{i0}|\;\;{\mathcal {II}}_i\notin {\mathcal {L}}_2 \quad and \quad d_2\le i\le p-1\}. \end{aligned}$$

Let $A=A'_1\cup A'_2$. In $T_S(p, 1, t)-A$, all ${\mathcal {I}}$-type cycles and ${\mathcal {II}}$-type cycles are destroyed. There is no alternating cycles about some perfect matching of $T_S(p, 1, t)$.

Fig. 7

Illustration the proof of the case $d_2>d_1$ by $T_S(12,1,3)$

Summing up, we obtain $F(T_S(p, 1, t))\le |A|=p$ by Lemma 2.2. $\square$

Lemma 4.10

If $p=1$, $F(T_S(1, q, 0))\le q$.

Proof

Let $A_0=\{d_{00}, a_{01}, \ldots , a_{0,q-1}\},$ see Fig. 8. In $T_S(1, q, 0)-A_0$, there is no cycles. By Lemma 2.2, we know $F(T_S(1, q, 0))\le |A_0|= q$. $\square$

Fig. 8

Illustration the proof of Lemma 4.10 by $T_S(1,6,0)$

By Lemmas 4.8, 4.9 and 4.10, we can obtain the following Theorem.

Theorem 4.11

$F(T_S(p, q, t))=pq.$

Proof

For $T_S(p, q, t)$, we can always find perfect matching $M_0$ such that $f(T_S(p, q, t), M_0)\ge pq$: the edges in $M_0$ result that every square in $T_S(p, q, t)$ is $M_0$-alternating.

Combining Lemmas 4.8, 4.9 and 4.10, we have $F(T_S(p, q, t))=pq$. $\square$

5 The maximum forcing number of Klein bottle 4–8 lattice

Let Q be defined as Sect. 4. 1. A Klein bottle 4–8 lattice $K_R(p,q,t)$ is generated from Q by the following boundary identification: first identify two vertical sides along the same direction, then identify the bottom side to the top side along the reverse directions with a torsion t. In $K_R(p,q,t)$, all the vertices can be covered by squares, see Fig. 9. Similarly, we define all the vertices and paths $l_0, l_1, \cdots , l_{p-1}$ of $K_R(p,q,t)$ as them in $T_R(p,q,t)$. For $0\le i\le t$, $l_i$ and $l_{t-i}$ form a cycle. For $t+1\le i\le p-1$, $l_i$ and $l_{p+t-i}$ form a cycle.

Fig. 9

$K_R(6,2,3)$ and the label of vertex

Theorem 5.1

$F(K_R(p, q, t))=pq.$

Proof

First we prove that $F(K_R(p, q, t))\le pq.$ Let M be any perfect matching of $K_R(p, q, t)$.

Case 1. $t\ge 1$.

Let $A_1=\{b_{i, 0}|\;1\le i\le p-1\}.$ For any square of the rest which do not contain vertices of $A_1$, we select $a_{ij}$ and they constitute $A_2$. Let $A=A_1\cup A_2.$ In $K_R-A$, there is no M-alternating cycle.

Case 2. $t=0$.

Let $l_0$ and $l_1$ be on cycles $C_0$ and $C_1$, respectively. Then $C_0$ and $C_1$ are not both M-alternating cycle, otherwise, there is isolated vertex. If $C_0$ is not M-alternating, let

$$\begin{aligned} A_1=\{b_{i, 0}|\;1\le i\le p-1\}. \end{aligned}$$

For any square of the rest which do not contain vertices of $A_1$, we select $a_{ij}$ and they constitute $A_2$. Let $A=A_1\cup A_2.$ If $C_1$ is not M-alternating, let

$$\begin{aligned} A'_1=\{b_{i, 0}|\;2\le i\le p-1 \text{ or } i=0\}. \end{aligned}$$

For any square of the rest which do not contain vertices of $A'_1$, we select $a_{ij}$ and they constitute $A'_2$. Let $A=A'_1\cup A'_2.$ In $K_R(p, q, t)-A$, there is no M-alternating cycle.

By Cases 1, 2 and Lemma 2.2, we know $F(K_R(p, q, t))\le pq$.

On the other hand, let $M_0$ be a perfect matching of $K_R(p, q, t)$ such that each square is $M_0$-alternating cycle, by Lemma 2.1, $f(K_R(p, q, t), M_0)\ge pq$.

Summing up, we obtain $F(K_R(p, q, t))=pq$. $\square$

A S-type Klein bottle 4–8 lattice $K_S(p,q,t)$ is generated from P (defined as Sect. 4. 2) by the following boundary identification: first identify two lateral sides along the same direction and then identify the two horizontal sides along the reverse directions with a torsion t, see Fig. 10. Similarly, we define all the vertices as them in $T_S(p,q,t)$.

Fig. 10

$K_S(6,2,2)$ and the label of vertex

We denote path $d_{i0}b_{i1}c_{i1}d_{i1}b_{i2}c_{i2}d_{i2}\cdots b_{i,q-1}c_{i,q-1}d_{i,q-1}b_{i0}$ by ${\mathcal {L}}_i$ ($0\le i\le p-1$). For $0\le i\le t$, ${\mathcal {L}}_i$ and ${\mathcal {L}}_{t-i}$ form a cycle. For $t+1\le i\le p-1$, ${\mathcal {L}}_i$ and ${\mathcal {L}}_{p+t-i}$ form a cycle.

Denote path $a_{i0}c_{i-1,1}d_{i-1,1}a_{i-1,1}c_{i-2,2}d_{i-2,2}a_{i-2,2}\cdots c_{i-(q-1),q-1}d_{i-(q-1),q-1}a_{i-(q-1),q-1}c_{i-q,0}$ by ${\mathcal {L}}'_i$ ($0\le i\le p-1$). For $0\le i \le p-1$, ${\mathcal {L}}'_i$ and ${\mathcal {L}}'_{-i-q+t}$ form a cycle.

In $K_S(p, 1, t)$, there is always multiple edge, and in this paper, we consider simple graph. Here we only investigate the case $q>1$ for $K_S(p, q, t)$.

Theorem 5.2

For $q>1$, $F(K_S(p, q, t))=pq.$

Proof

First we prove $F(K_S(p, q, t))\le pq.$ Let M be any perfect matching of $K_S(p, q, t)$.

Case 1. $t\ge 1$.

Let $A_1=\{b_{i, 1}|\;1\le i\le p-1\}$. For other squares which does not contain vertex of $A_1$, we select vertex $a_{ij}$ and they constitute $A_2$. Let $A=A_1\cup A_2.$ In $K_S(p, q, t)-A$, there is no cycles.

Case 2. $t=0$.

Let ${\mathcal {L}}_0$ and ${\mathcal {L}}_1$ be on cycles $C_1$ and $C'_1$. Cycles $C_1$ and $C'_1$ are not both M-alternating cycles. If $C_1$ is not M-alternating cycle, let

$$\begin{aligned} A_1=\{b_{i, 1}|\;1\le i\le p-1\}. \end{aligned}$$

For other squares which does not contain vertex of $A_1$, we select vertex $a_{ij}$ and they constitute set $A_2$. Let $A=A_1\cup A_2.$ If $C'_1$ is not M-alternating, let

$$\begin{aligned} A'_1=\{b_{i, 1}|\;2\le i\le p-1 \text{ or } i=0\}. \end{aligned}$$

For other squares which do not contain vertex of $A'_1$, we select vertex $a_{ij}$ and they constitute $A'_2$. Let $A=A'_1\cup A'_2.$ In $K_S(p, q, t)-A$, there is no cycles.

By Cases 1, 2 and Lemma 2.2, we know $F(K_S(p, q, t))\le pq$.

On the other hand, let $M_0$ be a perfect matching of $K_S(p, q, t)$ such that each square is $M_0$-alternating cycle, by Lemma 2.1, $f(K_S(p, q, t), M_0)\ge pq$. Hence we obtain $F(K_S(p, q, t))=pq.$ $\square$