几类梯状图的完美匹配与Hamilton圈 Perfect Matching of Several Types of Ladder Graphs and Hamilton Cycles

doi:10.12677/PM.2023.136173

Pure Mathematics
Vol. 13 No. 06 ( 2023 ), Article ID: 67849 , 12 pages
10.12677/PM.2023.136173

几类梯状图的完美匹配与Hamilton圈

王彦通

●How to Cite this Article

西北师范大学数学与统计学院，甘肃兰州

收稿日期：2023年5月19日；录用日期：2023年6月20日；发布日期：2023年6月28日

摘要

循环梯状图 $C L_{n}$ 是由圈 $C_{n}$ 和路 $P_{2}$ 的笛卡尔积 $C L_{n} = C_{n} \times P_{2} (n \geq 3)$ ，Möbius梯状图 $M L_{n}$ 是通过梯子图 $L_{n}$ 添加边 $a_{1} b_{n}$ 和 $b_{1} a_{n}$ 得到。删掉 $C L_{n}$ 和 $M L_{n}$ 的一个Hamilton圈(删边不删点)后剩下的子图是它们的一个完美匹配。反之，删掉 $C L_{n}$ 和 $M L_{n}$ 的一个完美匹配后剩下的子图只要是连通的，那一定是原图的Hamilton圈。因此本文通过删除完美匹配的方法给出了 $L_{n}$ ， $C L_{n}$ 和 $M L_{n}$ 的所有Hamilton圈，进而通过Hamilton圈研究了完美匹配之间的关系。

关键词

梯子图 $L_{n}$ ，循环梯状图 $C L_{n}$ ，Möbius梯状图 $M L_{n}$ ，Hamilton圈，完美匹配

Perfect Matching of Several Types of Ladder Graphs and Hamilton Cycles

Yantong Wang

College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu

Received: May 19^th, 2023; accepted: Jun. 20^th, 2023; published: Jun. 28^th, 2023

ABSTRACT

The cyclic ladder graph $C L_{n}$ is obtained from the Cartesian product $C L_{n} = C_{n} \times P_{2} (n \geq 3)$ of cycles $C_{n}$ and paths $P_{2}$ and the Möbius ladder graph $M L_{n}$ is obtained by adding edges $a_{1} b_{n}$ and $b_{1} a_{n}$ to the ladder graph $L_{n}$ . The remaining subgraphs after we delete a Hamilton cycle of $C L_{n}$ and $M L_{n}$ (deleting edges without deleting points) are a perfect matching of them. Conversely, the remaining subgraphs after deleting a perfect matching of $C L_{n}$ and $M L_{n}$ must be a Hamilton cycle of the original graph as long as they are connected. Therefore, this paper gives all Hamilton cycles of $L_{n}$ , $C L_{n}$ and $M L_{n}$ by deleting perfect matching, and then investigates the relationship between perfect matching through Hamilton cycles.

Keywords:Ladder Graph $L_{n}$ , Cyclic Ladder Graph $C L_{n}$ , Möbius Ladder Graph $M L_{n}$ , Hamilton Cycles, Perfect Matching

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图论起源于七桥问题，已经迅速发展到计算机科学，化学，生物学，物理等学科，化学中得到更加广泛的应用。在1985年，Klein和Randić [1] [2] 在研究分子共振结构时发现分子的一个凯库勒结构可以由固定的部分双键来确定，把所需的最少的双键的个数称作这个凯库勒结构的内自由度。Harary和Klein [3] 称其为图的完美匹配的强迫数。Adams [4] 等证明了在最大度为3的二部图中，它的一个完美匹配的强迫数是NP-完全的。Afshani等 [5] 证明了计算最大度为4的二部图的强迫数是NP-完全的。2004年，P. Adams，M. Mahdian和E. Mahmoodian [4] 定义了图G的强迫谱 $S p e c (G)$ ，即图G的所有完美匹配的强迫数构成的集合。张和平，赵爽等 [6] 提出了强迫多项式的概念。1997年，李学良 [7] 研究了具有反强迫边的六角系统。2007年，Vhukičević和Trinajstić [8] 从匹配强迫的对立面出发，提出图的反强迫数。2015年，H. Hwang，H. Lei，Y. Yeh和H. Zhang [9] 介绍了图的反强迫多项式。2016年，雷洪川，叶永南和张和平 [10] 首次提出完美匹配的反强迫数的概念，并给出了图的反强迫谱。2017年，石玲娟，张和平 [11] [12] 给出了图的最大反强迫数的一个新上界，证明了(4,6)-富勒烯图的最大强迫数等于它的Clar数，最大反强迫数等于它的Fris数。邓凯等 [13] [14] 给出了图G的反强迫谱 $S p e c a f (G)$ 的定义，即图G的所有完美匹配的反强迫数构成的集合。2018年，赵爽，张和平 [15] 计算了有强迫边的苯基系统和苯型平行四边形的反强迫多项式。姚海元、王杰彬、韩振云等 [16] [17] 得到了几类梯子图的反强迫谱和Lucas数列、Fibonacci数列之间的一些组合解释。2019年，赵爽，张和平 [18] 计算了 $P_{2} \times P_{n}$ 格子图和 $P_{3} \times P_{2 n}$ 格子图的强迫多项式和反强迫多项式。2021年，邓凯等 [19] 研究了芘系统，方格子系统的强迫和反强迫多项式。马聪聪 [20] 研究了C₆₀的一个比较特殊的同分异构体和C₇₀的完美匹配、强迫数和反强迫数，得到了它们的反强迫多项式，以及一些其它富勒烯图的反强迫多项式。王倩倩 [21] 研究了几类特殊图的反强迫多项式。2022年，刘雨童，马聪聪和姚海元 [22] 提出了图的双强迫多项式。刘雨童 [23] 给出了60阶富勒烯图的双强迫多项式。邓凯 [24] 计算了线性亚苯基系统的强迫和反强迫多项式，得到了它们精确的表达式。

本文主要研究几类梯状图的完美匹配与Hamilton圈的关系。

2. 预备知识

图G的完美匹配是指覆盖G中所有顶点的两两不交的边的集合。包含图G的每个顶点的路我们称为G的Hamilton路，类似地，G的Hamilton圈是指包含图G的每个顶点的圈。

循环梯状图 $C L_{n}$ 是由圈 $C_{n}$ 和路 $P_{2}$ 的笛卡尔积 $C L_{n} = C_{n} \times P_{2} (n \geq 3)$ ，也可以由梯子图通过添加边 $a_{1} a_{n}$ 和边 $b_{1} b_{n}$ 得到，如图1所示。

Figure 1. Cyclic ladder graph $C L_{n}$

图1. 循环梯状图 $C L_{n}$

循环梯状图 $C L_{n}$ 中，我们把类似于的 $a_{i} b_{i}$ 边称为竖直边，类似于 $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} a_{n}, b_{1} b_{n}$ 的边称为水平边。设M是循环梯状图 $C L_{n}$ 的一个完美匹配，M中类似于 $a_{i} b_{i}$ 的边称为竖直匹配边，类似于 $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} a_{n}, b_{1} b_{n}$ 的边称为水平匹配边。

Möbius梯状图 $M L_{n}$ 是通过梯子图 $L_{n}$ 添加边 $a_{1} b_{n}$ 和 $b_{1} a_{n}$ ，如图2所示。

Figure 2. Möbius ladder graph $M L_{n}$

图2. Möbius梯状图 $M L_{n}$

Möbius梯状图 $M L_{n}$ 中，把类似于的 $a_{i} b_{i}$ 边称为竖直边，类似于 $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} b_{n}, b_{1} a_{n}$ 的边称为水平边。设M是循环梯状图 $M L_{n}$ 的一个完美匹配，M中类似于 $a_{i} b_{i}$ 的边称为竖直匹配边，类似于 $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} b_{n}, b_{1} a_{n}$ 的边称为水平匹配边。

Hamilton圈是两个特殊完美匹配的不交并。设 $A, B$ 是两个集合，A和B的对称差我们定义为

$A \oplus B = (A \cup B) (A \cap B),$

特别地，如果 $A \cap B = \emptyset$ ，则 $A \oplus B = A \dot{\cup} B$ ，即A和B的不交并。

下面给出计算循环梯状图 $C L_{n}$ 与Möbius梯状图 $M L_{n}$ 完美匹配个数的两个定理。

定理1 [25] 循环梯状图 $C L_{n}$ 的完美匹配个数 $| M | = {\begin{cases} l_{n}, 若 n \geq 3 是奇数; \\ l_{n} + 2, 若 n \geq 4 是偶数 . \end{cases}$

定理2 [25] Möbius梯状图 $M L_{n}$ 的完美匹配个数 $| M | = {\begin{cases} l_{n} + 2, 若 n \geq 3 是奇数; \\ l_{n}, 若 n \geq 2 是偶数 . \end{cases}$

定理1和2中， $l_{n} = l_{n - 1} + l_{n - 2}$ 为递推关系的Lucas数列，初始值 $l_{0} = 2, l_{1} = 1$ ，它的第n项和 $l_{n} = \sum_{i = 0}^{n} \frac{n}{n - i} (\begin{matrix} n - i \\ i \end{matrix})$ 。当n为偶数时，循环梯状图 $C L_{n}$ 中，多了两个上下交错水平匹配边的完美匹配，在Möbius梯状图 $M L_{n}$ 中，这种情况出现在n为奇数。

3. 主要结论

3.1. 循环梯状图 $C L_{n}$ 与Hamilton圈

下面给出 $C L_{3}$ 的4个完美匹配(图3)：

Figure 3. All 4 perfect matchings of cyclic ladder graph $C L_{3}$

图3. 循环梯状图 $C L_{3}$ 的所有4个完美匹配

$C L_{3}$ 分别删除各完美匹配的子图(图4)：

Figure 4. The graphs of deleting each perfect matchings of cyclic ladder graph $C L_{3}$

图4. 循环梯状图 $C L_{3}$ 分别删除各完美匹配的子图

下面给出循环梯状图 $C L_{3}$ 完美匹配与Hamilton圈的表示(表1)。

Table 1. Representation by perfect matching of 3 Hamilton-cycles of C L 3

表1. $C L_{3}$ 3个Hamilton圈与完美匹配的表示

下面给出 $C L_{4}$ 的9个完美匹配(图5)：

Figure 5. All 9 perfect matchings of cyclic ladder graph $C L_{4}$

图5. 循环梯状图 $C L_{4}$ 的所有9个完美匹配

$C L_{4}$ 分别删除各完美匹配的子图(图6)：

Figure 6. The graphs of deleting each perfect matchings of cyclic ladder graph $C L_{4}$

图6. 循环梯状图 $C L_{4}$ 分别删除各完美匹配的子图

下面给出循环梯状图 $C L_{4}$ 完美匹配与Hamilton圈的表示(表2)。

Table 2. Representation by perfect matching of 6 Hamilton cycles of C L 4

表2. $C L_{4}$ 6个Hamilton圈与完美匹配的表示

下面给出 $C L_{5}$ 的11个完美匹配(图7)：

Figure 7. All 11 perfect matchings of cyclic ladder graph $C L_{5}$

图7. 循环梯状图 $C L_{5}$ 的所有11个完美匹配

$C L_{5}$ 分别删除各完美匹配的子图(图8)：

Figure 8. The graphs of deleting each perfect matchings of cyclic ladder graph $C L_{5}$

图8. 循环梯状图 $C L_{5}$ 分别删除各完美匹配的子图

下面给出循环梯状图 $C L_{5}$ 完美匹配与Hamilton-圈的表示(表3)。

Table 3. Representation by perfect matching of 5 Hamilton cycles of C L 5

表3. $C L_{5}$ 5个Hamilton圈与完美匹配的表示

下面给出主要结论。

引理1 设M是循环梯状图 $C L_{n}$ 的完美匹配，若M含有至少2对水平匹配边，则 $C L_{n} \ M$ 不存在Hamilton圈。

证明：首先，我们考虑n为偶数的情况。当n为偶数，我们根据水平匹配边的个数进行分类讨论。设p为M中成对水平匹配边的个数。

1) 当 $p = 0$ 时，即M中没有水平匹配边或是上下交错出现的水平匹配边。若M中没有水平匹配边， $C L_{n}$ 在 $C L_{n} \ M$ 后，存在两个不交的长度为n的偶圈，此时 $C L_{n} \ M$ 不存在Hamilton圈；若上下交错出现的水平匹配边， $C L_{n}$ 在 $C L_{n} \ M$ 后，存在一个长为2n的Hamilton圈，不存在其它分支，因此 $C L_{n} \ M$ 不存在Hamilton圈。

2) 当 $p = 1$ 时，即M中只含有一对水平匹配边，不妨设 $a_{1} a_{2}, b_{1} b_{2} \in M$ ， $C L_{n}$ 在 $C L_{n} \ M$ 后，如下图所示，删掉这对水平匹配边之后，顶点 $a_{1}, a_{2}$ 和 $b_{1}, b_{2}$ 之间没有边相连，此时通过外水平边 $a_{1} a_{n}, b_{1} b_{n}$ 的路，因此 $C L_{n} \ M$ 存在Hamilton圈且是一个长为2n的偶圈。

3) 当 $2 \leq p \leq \frac{n}{2}$ 时，即M含有至少2对水平匹配边，首先我们看 $p = 2$ 时的情况，如下图所示，不妨设 ${a_{1} a_{2}, b_{1} b_{2}, a_{3} a_{4}, b_{3} b_{4}} \in M$ ，删掉它的匹配边之后，至少会出现两个分支，且都是偶圈，因此不存在Hamilton圈，当随着成对水平匹配边个数的增加，出现偶分支的个数也随之增加。所以当 $2 \leq p \leq \frac{n}{2}$ 时， $C L_{n} \ M$ 不存在Hamilton圈。

综上可得，当n为偶数时，若M含有至少2对水平匹配边，则 $C L_{n} \ M$ 不存在Hamilton圈。同理可得，当n为奇数时，引理成立。即证。

定理3 循环梯状图 $C L_{n}$ 的Hamilton圈的个数 $h (C L_{n})$ 为

$h (C L_{n}) = {\begin{cases} n, 若 n 是奇数; \\ n + 2, 若 n 是偶数 . \end{cases}$

证明：设M是循环梯状图 $C L_{n}$ 的任一完美匹配，由引理1及其证明过程可知，若M中含有上下交错水平匹配边(不成对匹配边)与含有一对水平匹配边(其余全是竖直匹配边)，则 $C L_{n} \ M$ 存在Hamilton圈。因此我们只对这2种情况进行讨论。设所有完美匹配中 $C L_{n} \ M$ 有Hamilton圈的个数记作 $h (C L_{n})$ 。

1) 若M中含有上下交错水平匹配边，只有n为偶数时出现此类情况，这样的完美匹配有2个，它们互相平移可以得到。由引理1可知， $C L_{n} \ M$ 存在2个Hamilton圈，即

$h^{*} (C L_{n}) = 2, n 是偶数 .$

2) 若M中含有一对水平匹配边(其余全是竖直匹配边)，不妨设第一个完美匹配中 $a_{1} a_{2}, b_{1} b_{2} \in M$ ，我们通过平移 $a_{1} a_{2}, b_{1} b_{2}$ 这对水平匹配边，则可得到只含有一对水平匹配边的所有完美匹配。由引理1可知， $C L_{n} \ M$ 存在n个Hamilton圈。即

$h^{*} (C L_{n}) = n .$

综上(1) (2)可得，

$h (C L_{n}) = {\begin{cases} n, 若 n 是奇数; \\ n + 2, 若 n 是偶数 . \end{cases}$

3.2. Möbius梯状图 $M L_{n}$ 与Hamilton圈

下面给出 $M L_{3}$ 的6个完美匹配(图9)：

Figure 9. All 6 perfect matchings of Möbius ladder graph $M L_{3}$

图9. Möbius梯状图 $M L_{3}$ 的所有6个完美匹配

$M L_{3}$ 分别删除各完美匹配的子图(图10)：

Figure 10. The graphs of deleting each perfect matchings of Möbius ladder graph $M L_{3}$

图10. Möbius梯状图 $M L_{3}$ 分别删除各完美匹配的子图

下面给出Möbius梯状图 $M L_{3}$ 完美匹配与Hamilton圈的表示(表4)。

Table 4. Representation by perfect matching of 6 Hamilton-cycles of M L 3

表4. $M L_{3}$ 6个Hamilton-圈与完美匹配的表示

下面给出 $M L_{4}$ 的7个完美匹配(图11)：

Figure 11. All 7 perfect matchings of Möbius ladder graph $M L_{4}$

图11. Möbius梯状图 $M L_{4}$ 的所有7个完美匹配

$M L_{4}$ 分别删除各完美匹配的子图(图12)：

Figure 12. The graphs of deleting each perfect matchings of Möbius ladder graph $M L_{4}$

图12. Möbius梯状图 $M L_{4}$ 分别删除各完美匹配的子图

下面给出 Möbius梯状图 $M L_{4}$ 完美匹配与Hamilton-圈的表示(表5)。

Table 5. Representation by perfect matching of 5 Hamilton cycles of M L 4

表5. $M L_{4}$ 5个Hamilton圈与完美匹配的表示

下面给出 $M L_{5}$ 的13个完美匹配(图13)：

Figure 13. All 13 perfect matchings of Möbius ladder graph $M L_{5}$

图13. Möbius梯状图 $M L_{5}$ 的所有13个完美匹配

$M L_{5}$ 分别删除各完美匹配的子图(图14)：

Figure 14. The graphs of deleting each perfect matchings of Möbius ladder graph $M L_{5}$

图14. Möbius梯状图 $M L_{5}$ 分别删除各完美匹配的子图

下面给出Möbius梯状图 $M L_{5}$ 完美匹配与Hamilton-圈的表示(表6)。

Table 6. Representation by perfect matching of 8 Hamilton cycles of M L 5

表6. $M L_{5}$ 8个Hamilton圈与完美匹配的表示

引理2 设M是Möbius梯状图 $M L_{n}$ 的完美匹配，若M含有至少2对水平匹配边，则 $M L_{n} \ M$ 不存在Hamilton圈。

证明：首先，考虑n为偶数的情况。当n为偶数，我们根据水平匹配边的个数进行分类讨论。设p为M中成对水平匹配边的个数。

1) 当 $p = 0$ 时，即M中没有水平匹配边，如下图所示， $M L_{n}$ 在 $M L_{n} \ M$ 后，存在一个长度为2n的偶圈，不存在其它分支， $C L_{n} \ M$ 存在Hamilton圈。

2) 当 $p = 1$ 时，即M中只含有一对水平匹配边，不妨设 $a_{1} a_{2}, b_{1} b_{2} \in M$ ， $M L_{n}$ 在 $M L_{n} \ M$ 后，如下图所示，删掉这对水平匹配边之后，顶点 $a_{1}, a_{2}$ 和 $b_{1}, b_{2}$ 之间没有边相连，此时通过外水平边 $a_{1} b_{n}, b_{1} a_{n}$ 的路，因此 $M L_{n} \ M$ 存在Hamilton圈且是一个长为2n的偶圈。

3) 当 $2 \leq p \leq \frac{n}{2}$ 时，即M含有至少2对水平匹配边，首先 $p = 2$ 时的情况，如下图所示，不妨设 ${a_{1} a_{2}, b_{1} b_{2}, a_{3} a_{4}, b_{3} b_{4}} \in M$ ，删掉它的匹配边之后，至少会出现两个分支，且都是偶圈，因此不存在Hamilton圈，当随着成对水平匹配边个数的增加，出现偶分支的个数也随之增加。所以当 $2 \leq p \leq \frac{n}{2}$ 时， $M L_{n} \ M$ 不存在Hamilton圈。

综上可得，当n为偶数时，若M含有至少2对水平匹配边，则 $M L_{n} \ M$ 不存在Hamilton圈。同理可得，当n为奇数时，引理成立。即证。

引理3 设M是Möbius梯状图 $M L_{n}$ 的完美匹配，若M是全竖直匹配边，则 $M L_{n} \ M$ 存在Hamilton圈。

定理4 Möbius梯状图 $M L_{n}$ 的Hamilton圈的个数 $h (M L_{n})$ 为

$h (M L_{n}) = {\begin{cases} n + 3, 若 n 是奇数; \\ n + 1, 若 n 是偶数 . \end{cases}$

证明：设M是Möbius梯状图 $M L_{n}$ 的任一完美匹配，由引理2及其证明过程可知，若M中含有上下交错水平匹配边(不成对匹配边)，含有一对水平匹配边(其余全是竖直匹配边)与全竖直匹配边，则 $M L_{n} \ M$ 存在Hamilton圈。因此我们只对这3种情况进行讨论。设所有完美匹配中 $M L_{n} \ M$ 有Hamilton圈的个数记作 $h (M L_{n})$ 。

1) 若M中含有上下交错水平匹配边，只有n为奇数时出现此类情况，这样的完美匹配有2个，它们互相平移可以得到。由引理2知， $M L_{n} \ M$ 存在2个Hamilton圈，即

$h^{*} (M L_{n}) = 2, n 是奇数 .$

2) 若M中含有一对水平匹配边(其余全是竖直匹配边)，不妨设第一个完美匹配中 $a_{1} a_{2}, b_{1} b_{2} \in M$ ，我们通过平移 $a_{1} a_{2}, b_{1} b_{2}$ 这对水平匹配边，则可得到只含有一对水平匹配边的所有完美匹配。由引理2可知， $M L_{n} \ M$ 存在n个Hamilton圈。即

$h^{*} (M L_{n}) = n .$

3) 若M中是全竖直匹配边，由引理2可知， $M L_{n} \ M$ 存在1个Hamilton圈。即

$h^{*} (M L_{n}) = 1.$

综上(1) (2) (3)可得，

$h (M L_{n}) = {\begin{cases} n + 3, 若 n 是奇数; \\ n + 1, 若 n 是偶数 . \end{cases}$

定理3与定理4也可以通过定理5证明得到。

定理5 梯子图 $L_{n}$ 的Hamilton圈的个数 $h (L_{n})$ 为

$h (L_{n}) = 1.$

梯子图 $L_{n}$ 只有唯一的一个Hamilton圈，即

$C = a_{1} a_{2} a_{3} \dots a_{n - 1} a_{n} b_{n} b_{n - 1} \dots a_{3} a_{2} a_{1} .$

当 $C L_{n}$ 与 $M L_{n}$ 不含上下交错边的完美匹配，其它完美匹配删除匹配边后是否有Hamilton圈，可由定理5证明。删除一个水平M-交错4-圈后，其子图若只含有竖直匹配边的完美匹配，则原图一定存在Hamilton圈。由定理3和4的证明过程即得。

基金项目

国家自然科学基金资助项目(12161081)。

文章引用

王彦通. 几类梯状图的完美匹配与Hamilton圈
Perfect Matching of Several Types of Ladder Graphs and Hamilton Cycles[J]. 理论数学, 2023, 13(06): 1696-1707. https://doi.org/10.12677/PM.2023.136173

参考文献

1. Randić, M. and Klein, D.J. (1985) Kekulé Valence Structures Revisited. Innate Degrees of Freedom of π-Electron Couplings. In: Trinajstić, N., Ed., Mathematical and Computational Concepts in Chemistry, Wiley, New York, 274-282.

2. Klein, D.J. and Randić, M. (1987) Innate Degree of Freedom of a Graph. Journal of Computational Chemistry, 8, 516-521. https://doi.org/10.1002/jcc.540080432

3. Harary, F., Klein, D.J. and Živković, T.P. (1991) Graphical Properties of Polyhexes: Perfect Matching Vector and Forcing. Journal of Mathematical Chemistry, 6, 295-306. https://doi.org/10.1007/BF01192587

4. Adams, P., Mahdian, M. and Mahmoodian, E.S. (2004) On the Forced Matching Numbers of Bipartite Graphs. Discrete Mathematics, 281, 1-12. https://doi.org/10.1016/j.disc.2002.10.002

5. Afshani, P., Hatami, H. and Mahmoodian, E.S. (2004) On the Spectrum of the Forced Matching Number of Graphs. The Australasian Journal of Combinatorics, 30, 147-160.

6. Zhang, H., Zhao, S. and Lin, R. (2015) The Forcing Polynomial of Catacondensed Hexagonal Systems. MATCH Communications in Mathematical and in Computer Chemistry, 73, 473-490.

7. Li, X. (1997) Hexagonal Systems with Forcing Single Edges. Discrete Applied Mathematics, 72, 295-301. https://doi.org/10.1016/0166-218X(95)00116-9

8. Vhukičević, D. and Trinajstić, N. (2007) On the Anti-Forcing Number of Benzenoids. Journal of Mathematical Chemistry, 42, 575-583. https://doi.org/10.1007/s10910-006-9133-6

9. Hwang, H., Lei, H., Yeh, Y. and Zhang, H. (2015) Distribution of Forcing and Anti-Forcing Numbers of Random Perfect Matchings on Hexagonal Chains and Crowns. http://140.109.74.92/hk/?p=873

10. Lei, H., Yeh, Y. and Zhang, H. (2016) Anti-Forcing Numbers of Perfect Matchings of Graphs. Discrete Applied Mathematics, 202, 95-105. https://doi.org/10.1016/j.dam.2015.08.024

11. Shi, L. and Zhang, H. (2017) Tight Upper Bound on the Maximum Anti-Forcing Numbers of Graphs. Discrete Mathematics & Theoretical Computer Science, 19, Article No. 9.

12. Shi, L., Wang, H. and Zhang, H. (2017) On the Maximum Forcing and Anti-Forcing Numbers of (4,6)-Fullerenes. Discrete Applied Mathematics, 233, 187-194. https://doi.org/10.1016/j.dam.2017.07.009

13. Deng, K. and Zhang, H. (2017) Anti-Forcing Spectra of Perfect Matchings of Graphs. Journal of Combinatorial Optimization, 33, 660-680. https://doi.org/10.1007/s10878-015-9986-3

14. Deng, K. and Zhang, H. (2017) Anti-Forcing Spectrum of Any Cata-Condensed Hexagonal System Is Continuous. Frontiers of Mathematics in China, 12, 19-33. https://doi.org/10.1007/s11464-016-0605-0

15. Zhao, S. and Zhang, H. (2018) Anti-Forcing Polynomials for Benzenoids Systems with Forcing Edges. Discrete Applied Mathematics, 250, 342-356. https://doi.org/10.1016/j.dam.2018.05.023

16. 姚海元, 王杰彬, 王旭. 循环梯状图的完美匹配的反强迫谱与卢卡斯数[J]. 西北师范大学学报: 自然科学版, 2018, 54(2): 21-25.

17. 韩振云, 王杰彬. 梯子图完美匹配的反强迫谱与斐波那契数列[J]. 兰州工业学院学报, 2020, 27(1): 85-90.

18. Zhao, S. and Zhang, H. (2019) Forcing and Anti-Forcing Polynomials of Perfect Matchings for Some Rectangle Grids. Journal of Mathematical Chemistry, 57, 202-225. https://doi.org/10.1007/s10910-018-0944-z

19. Deng, K., Lü, H. and Wu, T. (2020) Forcing and An-ti-Forcing Polynomials of a Polyomino Graph.

20. 马聪聪. 几类富勒烯图的反强迫多项式[D]: [硕士学位论文]. 兰州: 西北师范大学, 2021.

21. 王倩倩. 几类特殊图的反强迫多项式[D]: [硕士学位论文]. 兰州: 西北师范大学, 2021.

22. Liu, Y.T., Ma, C.C., Yao, H.Y. and Wang, X. (2022) Computing the Forcing and Anti-Forcing Numbers of Perfect Matchings for Graphs by Integer Linear Programmings. MATCH Communications in Mathematical and in Computer Chemistry, 87, 561-575. https://doi.org/10.46793/match.87-3.561L

23. 刘雨童. 60阶富勒烯图的双强迫多项式[D]: [硕士学位论文]. 兰州: 西北师范大学, 2022.

24. 邓凯. 线性亚苯基系统的强迫和反强迫多项式[J]. 高校应用数学学报A辑, 2022, 37(4): 491-500.

25. 王杰彬. 几类特殊图的反强迫谱的研究[D]: [硕士学位论文]. 兰州: 西北师范大学, 2018.

期刊菜单