2-管状广义富勒烯图双强迫多项式的递推求解

Recursive Solving of Di-Forcing Polynomials for 2-Tubular Generalized Fullerene Graphs

摘要: 2-管状广义富勒烯图是由两端的两个两边形和两个五边形构成的帽子和纯由六边形构成的管身接成的管状广义富勒烯图。图的双强迫多项式是关于该图的所有完美匹配的强迫数和反强迫数的二变量多项式。通过对给定顶点关联边的匹配情况的分类讨论和计数，得出了2-管状广义富勒烯图双强迫多项式的线性递推公式，通项公式以及生成函数。

Abstract: The 2-tubular generalized fullerene graph is a tubular generalized fullerene graph formed by connecting a cap composed of two digons and two pentagons at each end to a tube body composed purely of hexagons. The di-forcing polynomial of the graph is a two-variable polynomial regarding the forcing numbers and anti-forcing numbers of all perfect matchings of the graph. By classifying and counting the matching situations of the edges incident to a given vertex, we derived the linear recurrence formula, general term formula, and generating function for the di-forcing polynomials of 2-tubular generalized fullerene graphs.

1. 引言

图的双强迫多项式是图论中一个新兴的研究方向，图的完美匹配在有机化学中被称为凯库勒结构。1985年，Randic和Klein [1]在研究有机化学分子时第一次提出了凯库勒结构的内自由概念。1991年，Harary等[2]研究六角系统时，将其正式命名为图的完美匹配的强迫数。2007年，Vukiěević和Trinajstić [3]提出反强迫数的概念，Adams等[4]提出了图的强迫谱的概念，即图的所有完美匹配的强迫数构成的集合。2016年，雷洪川[5]提出了图的反强迫谱的概念。为了更好地计数图的所有完美匹配的强迫数和反强迫数，张和平[6]等和Hwang等[7]分别提出了强迫多项式和反强迫多项式的概念。特别的，关于一些图类的强迫多项式和反强迫多项式的计算得到了不少的结论[8]-[12]。2022年，刘雨童，马聪聪，姚海元等[13]提出了图的双强迫多项式的概念，并利用整数线性规划来计算完美匹配的强迫数，反强迫数和双强迫多项式。2023年，韩慧等[14]通过讨论梯子图给定顶点关联边的匹配情况得到了其双强迫多项式的递推公式以及生成函数。2024年，王彦通[15]通过定义删缩$M$ -交错圈的方法，给出了循环梯状图的双强迫多项式的递推关系和生成函数。尽管关于图的强迫多项式和反强迫多项式的研究取得了大量成果，但关于图的双强迫多项式的研究成果较少。本文主要通过对给定顶点关联边的匹配情况的分类讨论和计数，给出了2-管状广义富勒烯图$T_{\text{2},n}$ 的双强迫多项式的递推公式和通项公式。

2. 预备知识

图$G$ 是指一个有序的三元组$\left(V\left(G\right),E\left(G\right),{\psi }_G\right)$ ，其中$V\left(G\right)$ 和$E\left(G\right)$ 分别代表图$G$ 的顶点集和边集，${\psi }_G$ 代表关联函数。$G$ 的完美匹配是指两两无公共端点且关联$G$ 中所有顶点的边的集合。对完美匹配$M$ ，若其子集$S$ 不包含在其他任何完美匹配中，则称$S$ 为$M$ 的强迫集。$M$ 的最小强迫集的大小称为$M$ 的强迫数，记为$f\left(G,M\right)$ 。若图$G$ 中删除边集$S^{\prime }$ 后，能够唯一确定完美匹配$M$ ，则称$S^{\prime }$ 是$M$ 的反强迫集。$M$ 的最小的反强迫集的大小称为$M$ 的反强迫数，记为$af\left(G,M\right)$ 。此外，将图$G$ 中所有完美匹配的最小和最大强迫数分别称为$G$ 的最小强迫数$f\left(G\right)$ 和最大强迫数$F\left(G\right)$ 。相应地，将图$G$ 中所有完美匹配反强迫数的最小值和最大值分别称为$G$ 的最小反强迫数$af\left(G\right)$ 和最大反强迫数$Af\left(G\right)$ 。

图$G$ 的$M$ -交错圈是指图中的某个圈的边交替属于完美匹配$M$ 和其补集。若一组$M$ -交错圈两两不相交或仅共享$M$ 中的边，则称它们为相容的。 图$G$ 的最大不相交和最大不相容$M$ -交错圈的数量分别记作$c\left(G,M\right)$ 和$c^{\prime }\left(G,M\right)$ 。

引理1 [4] [16]设$M$ 为图$G$ 的一个完美匹配，则$S\subseteq M$ 是$M$ 的强迫集当且仅当$S$ 包含$G$ 的每个$M$ -交错圈的至少一条匹配边。

引理2 [5] 设$M$ 为图$G$ 的一个完美匹配，则$S^{\prime }\subseteq E\left(G\right)\backslash M$ 是$M$ 的反强迫集当且仅当$S^{\prime }$ 包含图$G$ 的每个$M$ -交错圈的至少一条非匹配边。

引理3 [17] 设$M$ 为图$G$ 的任一完美匹配，则$f\left(G,M\right)\ge c\left(M\right)$ 。特别的，若图$G$ 是平面二部图，则$f\left(G,M\right)=c\left(M\right)$ 。

引理4 [5] 设$M$ 为图$G$ 的任一完美匹配，则$af\left(G,M\right)\ge c^{\prime }\left(M\right)$ 。特别的，若图$G$ 是平面二部图，则$af\left(G,M\right)=c^{\prime }\left(M\right)$ 。

定义1 [6] 图$G$ 的强迫多项式为

$F\left(G,x\right)={\displaystyle \sum _{M\in ℳ\left(G\right)}{x}^{f\left(G,M\right)}}={\displaystyle \sum _{i=f\left(G\right)}^{F\left(G\right)}w\left(G,i\right)x^i},$

其中$w\left(G,i\right)$ 表示$G$ 的强迫数为$i$ 的完美匹配的个数。

定义2 [7] 图$G$ 的反强迫多项式为

$Af\left(G,x\right)={\displaystyle \sum _{M\in ℳ\left(G\right)}{x}^{af\left(G,M\right)}}={\displaystyle \sum _{i=af\left(G\right)}^{Af\left(G\right)}\mu \left(G,i\right)x^i},$

其中$\mu \left(G,i\right)$ 表示$G$ 的反强迫数为$i$ 的完美匹配的个数。

定义3 [13] 图$G$ 的双强迫多项式为

$Faf\left(G;x,y\right)={\displaystyle \sum _{M\in ℳ\left(G\right)}{x}^{f\left(G,M\right)}}{y}^{af\left(G,M\right)}={\displaystyle \sum _{i,j}\nu \left(G;i,j\right)x^i{y}^j},$

其中$\nu \left(G;i,j\right)$ 表示$G$ 的强迫数为$i$ ，反强迫数为$j$ 的完美匹配的个数。

由此

$\{\begin{array}{l}F\left(G,x\right)=Faf\left(G;x,1\right),\\ Af\left(G,x\right)=Faf\left(G;1,x\right).\end{array}$

3. 2-管状广义富勒烯图的双强迫多项式

2-管状广义富勒烯图是由两端的两个两边形(即两条重边)和两个五边形构成的帽子和纯由六边形构成的管身贴接而成的管状广义富勒烯图，记为$T_{2,n}^{}$ ，其中$n$ 代表环绕管身的4-圈的个数，也称作管状广义富勒烯的层数。通常将其顶点放在两条水平线上，如图1，其顶点从上到下，从左到右依次记为$a_1,a_2,\cdots a_k;b_1,b_2,\cdots b_k$ ，(其中$k=2n+2$ );其边集为与端点$a_1,b_1$ 相连接的重边$e_1,e_2$ ，与$a_k,b_k$ 相连接的重边$e_3,e_4$ ，以及水平边$a_i{a}_{i+1},b_i{b}_{i+1}\left(i=1,2,\cdots ,k-\text{1}\right)$ ，交叉边$a_{2i}{b}_{2i+1},a_{2i+1}{b}_{2i}\left(i=1,\cdots ,n\right)$ 。为方便起见，除水平边以外的其余边统称为竖直边。

Figure 1. 2-Tubular generalized fullerene diagram

图1. 2-管状广义富勒烯图

设$M$ 是2-管状广义富勒烯图为$T_{2,n}$ 的一个完美匹配，$M$ 中的水平边与竖直边分别称为水平匹配边和竖直匹配边。当$a_{2i}{a}_{2i+1},b_{2i}{b}_{2i+1}\in M,$ 则$M$ -交错圈$C=a_{2i}{a}_{2i+1}{b}_{2i}{b}_{2i+1}{a}_{2i}$ 称为水平$M$ -交错4-圈，当$a_{2i}{b}_{2i+1},b_{2i}{a}_{2i+1}\in M$ ，则$M$ -交错圈$C=a_{2i}{b}_{2i+1}{b}_{2i}{a}_{2i+1}{a}_{2i}$ 称为竖直$M$ -交错4-圈。

当$n=1$ 时，左边的帽子和右边的帽子共用4-圈$a_2{a}_3{b}_2{b}_3{a}_2$ ，所以中间没有六边形层，它们通过4-圈粘在一起。如图2所示。

特殊地，当$n=2$ 时，两端的两个帽子通过中间的六边形连接起来。如图3所示。

Figure 2. Illustration of $T_{2,1}$

图2. $T_{2,1}$ 的图示

Figure 3. Illustration of $T_{2,2}$

图3. $T_{2,2}$ 的图示

引理5 设$M$ 是2-管状广义富勒烯图$T_{2,n}$ 的一个至少含一对竖直匹配边的完美匹配，则存在一个最大不交$M$ -交错圈集，包含$n$ 个$M$ -交错4-圈。

证明 如图1可知，$T_{2,n}$ 完美匹配的结构为：

若$a_i{a}_{i+1}\left(i=1,3,\cdots ,k-1\right)\in M$ ，则必然有$b_i{b}_{i+1}\left(i=1,3,\cdots ,k-1\right)\in M$ 。即$M$ 是全由水平匹配边构成的，这种完美匹配是唯一的，记为$M_{\text{0}}$ 。

若$e_1$ 或$e_{\text{2}}\in M$ ，则根据匹配的定义，$a_i{a}_{i+1},b_i{b}_{i+1}\left(i=1,3,\cdots ,k-1\right)\notin M$ ，则$a_{i+1}{a}_{i+2},b_{i+1}{b}_{i+2}\left(i=1,3,\cdots ,k-1\right)\in M$ ，形成水平$M$ -交错4-圈$a_{i+1}{a}_{i+\text{2}}{b}_{i+1}{b}_{i+2}{a}_{i+1}$ 或$a_{i+1}{b}_{i+2},a_{i+2}{b}_{i+1}\left(i=1,3,\cdots ,k-1\right)\in M$ ，形成竖直$M$ -交错4-圈$a_{i+1}{b}_{i+\text{2}}{b}_{i+1}{a}_{i+2}{a}_{i+1}$ 。即这种完美匹配除圈$c_1=\left\{e_1,e_2\right\},c_2=\left\{e_3,e_4\right\}$ 外，环绕管身的4-圈均为交错4-圈。

即由$T_{2,n}$ 的结构可知，除$M_{\text{0}}$ 外，其他完美匹配有$n$ 个交错4-圈并且它们都是独立的。故引理成立。

引理6 设$M$ 是2-管状广义富勒烯图$T_{2,n}$ 至少含一对竖直匹配边的完美匹配，则$M$ 的强迫数为

$f\left(T_{2,n},M\right)=n+2.$

证明 若$e_{\text{1}}\in M$ ，如图4所示，

Figure 4. $T_{2,n}$ , a perfect matching with at least one pair of vertically aligned matching edges

图4. $T_{2,n}$ 至少含一对竖直匹配边的完美匹配

则$a_1{a}_2,b_1{b}_2\notin M$ ，由$T_{\text{2},n}$ 的结构可知$e_3$ 或$e_4\in M$ ，不妨设$e_{\text{3}}\in M$ 。

可知$T_{\text{2},n}$ 中包含2个长度为2的圈，$c_{\text{1}}=\left\{e_1,e_2\right\},c_2=\left\{e_3,e_4\right\}$ ，由引理5可知它们与$T_{\text{2},n}$ 的$n$ 个不交$M$ -交错4-圈构成$T_{\text{2},n}$ 最大不交$M$ -交错圈集$A$ ，则$\left|A\right|=$ $n+2$ 。由于$T_{\text{2},n}$ 不是二部图，根据引理3有$M$ 的强迫数$f\left(T_{2,n},M\right)\ge n+2$ 。又因为$M$ 中的边只出现在$T_{\text{2},n}$ 的两端帽子的二边形和管身的$n$ 个4-圈中，由引理1从这$n+2$ 个偶圈中各取一条匹配边构成$M$ 的一个强迫集$S$ ，则$f\left(T_{2,n},M\right)\le \left|S\right|=n+2$ ，故引理得证。

引理7 设$M$ 是2-管状广义富勒烯图$T_{2,n}$ 至少含一对竖直匹配边的完美匹配，则$M$ 的反强迫数为

$af\left(T_{2,n},M\right)=n+3.$

证明 不妨设$e_1\in M$ ，如图5所示。

Figure 5. $T_{2,n}$ , a perfect matching with at least one pair of vertically aligned matching edges

图5. $T_{2,n}$ 至少含一对竖直匹配边的完美匹配

由引理6可知，$T_{2,n}$ 的所有顶点都被包含在$n+2$ 个独立$M$ -交错圈中，将这些圈中的所有非匹配边(构成一个完美匹配)去掉，就得到一个2-正则子图，该子图必连通(否则两个分支之间连的$M_0$ 中的边将不会被用到)，因而它是一个包含所有匹配边的长为$4\left(n+1\right)$ 的$M$ -交错圈$c^{\prime }$ 。即$c^{\prime }$ 与$T_{2,n}$ 最大不交$M$ -交错圈集构成$T_{2,n}$ 的一个最大相容$M$ -交错圈集$A^{\prime }$ ，且$\left|A^{\prime }\right|=n+3$ 。由于$T_{2,n}$ 不是二部图，根据引理4有$M$ 的反强数$af\left(T_{2,n},M\right)\ge n+3$ 。再由引理2取非匹配边$a_1{a}_2$ 与$n+2$ 个偶圈中各取一条非匹配边可以构成$M$ 的一个反强迫集$S^{\prime }$ ，则$af\left(T_{2,n},M\right)\le \left|S^{\prime }\right|=n+3$ ，综上引理得证。

下面，将给出2-管状广义富勒烯图为$T_{2,n}$ 的双强迫多项式的递推关系，$T_{2,n}$ 双强迫多项式关于层数$n$ 的通项公式，强迫多项式关于层数$n$ 的通项公式，反强迫多项式关于层数$n$ 的通项公式，以及完美匹配个数关于层数$n$ 的通项公式。由此给出删缩$M$ -交错4-圈的定义。

定义4 设$M$ 是2-管状广义富勒烯图$T_{2,n}^{}$ 的一个完美匹配，若

Figure 6. The operation of deleting and condensing M-interleaved 4-cycles in $T_{2,3}$

图6. $T_{2,3}$ 删缩$M$ -交错4-圈的操作

(i) $a_{2i}{a}_{2i+1},b_{2i}{b}_{2i+1}\in M$ ，且$C=a_{2i}{a}_{2i+1}{b}_{2i}{b}_{2i+1}{a}_{2i}$ 构成的$M$ -交错圈为水平$M$ -交错4-圈，删除$C$ 后 (即删除$C$ 的4个顶点)，将$a_{2i-1}$ 与$b_{2i+\text{2}}$ ，$b_{2i-1}$ 与$b_{2i+2}$ 通过非匹配边连接，则$T_{2,n}^{}\to T_{2,n-1}^{}$ ，称为删缩水平$M$ -交错4-圈。

(ii) $a_{2i}{b}_{2i+1},b_{2i}{a}_{2i+1}\in M$ ，且$C=a_{2i}{b}_{2i+1}{b}_{2i}{a}_{2i+1}{a}_{2i}$ 构成的$M$ -交错圈为竖直$M$ -交错4-圈，删除$C$ 后(即删除$C$ 的4个顶点)，将$a_{2i-1}$ 与$a_{2i+2}$ ，$b_{2i-1}$ 与$b_{2i+2}$ 通过非匹配边连接，则$T_{2,n}^{}\to T_{2,n-1}^{}$ ，称为删缩竖直$M$ -交错4-圈。

删缩$M$ -交错4-圈后，$T_{2,n}$ 的整体结构没有改变，依然是退化的2-管状广义富勒烯图。下面给出$T_{2,3}$ 的完美匹配分别删缩水平$M$ -交错4-圈，竖直$M$ -交错4-圈的例子，如图6所示。

下面根据$T_{2,n}$ 的完美匹配类型，进行删缩$M$ -交错4-圈的操作，进而解出$T_{2,n}$ 的双强迫多项式的递推关系。

定理1 当$n\ge \text{1}$ 时，2-管状广义富勒烯图$T_{2,n}$ 的双强迫多项式的递推关系为

$Faf\left(T_{2,n};x,y\right)=2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3+x{y}^2.$

证明 设$M$ 是$T_{2,n}$ 的任意完美匹配，根据顶点$a_1$ 关联边的匹配情况进行讨论，如图7所示。

Figure 7. The matching situation of the edges associated with vertex $a_1$ of $T_{2,n}$

图7. $T_{2,n}$ 的顶点$a_1$ 关联边的匹配情况

情形1 若是全由水平匹配边构成的完美匹配$M_{\text{0}}$ ，如图8所示。

Figure 8. The perfect matching M of the fully horizontal matching edges of $T_{2,n}$ .

图8. $T_{2,n}$ 的全水平匹配边的完美匹配$M_0$

易知$S=\left\{a_1{a}_2\right\}$ 是$M$ 的一个最小强迫集，$S^{\prime }=\left\{e_1,e_2\right\}$ 是最小反强迫集。因此得$T_{2,n}$ 的部分双强迫多项式为

$x{y}^2$ 。

情形2 若$e_1\in M$ ，必有$e_3$ 或$e_4\in M$ 且$M\cap M_0=\varnothing$ ，则$M$ 至少包含一对竖直匹配边且$C_1=a_2{a}_3{b}_2{b}_3{a}_2$ 构成一个$M$ -交错4-圈，由引理5可知存在$T_{2,n}$ 的一个最大不交$M$ -交错圈集包含$C_1$ ，且其余$M$ -交错圈与$C_1$ 都不交，它们在$T_{2,n}$ 删缩$C_1$ 后的子图中找到，故$C_1$ 对最大不交$M$ -交错圈集的贡献是1，进而$C_1$ 对$M$ 的强迫数是1。另一方面由引理7可知，当$T_{2,n}$ 删缩$C_1$ 时，$C_1$ 对最大相容$M$ -交错圈集的贡献是1，则$C_1$ 对$M$ 的反强迫数贡献是1。此外，删缩$C_1$ 后不含$M_0$ 中的边，故$T_{2,n-1}$ 不含情形 1的类型且可以删缩的$M$ -交错4-圈有两种，因此得$T_{2,n}$ 的部分双强迫多项式的递推关系为

$\text{2}xy\left(Faf\left(T_{2,n-1};x,y\right)-x{y}^2\right).$

情形3 若$e_2\in M$ ，这与情形2是等价的。

综上，$T_{2,n}$ 的双强迫多项式为

$\begin{array}{c}Faf\left(T_{2,n};x,y\right)=2xy\left(Faf\left(T_{2,n-1};x,y\right)-x{y}^2\right)+x{y}^2\\ =2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3+x{y}^2.\end{array}$

推论1 当$n\ge \text{1}$ 时，2-管状广义富勒烯图$T_{2,n}$ 的双强迫多项式的一个齐次递推关系为

$Faf\left(T_{2,n};x,y\right)=\left(1+2xy\right)Faf\left(T_{2,n-1};x,y\right)-2xyFaf\left(T_{2,n-2};x,y\right).$

证明 由定理1可知，

$\begin{array}{l}Faf\left(T_{2,n};x,y\right)=2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3+x{y}^2.\\ Faf\left(T_{2,n-1};x,y\right)=2xyFaf\left(T_{2,n-2};x,y\right)-2x^2{y}^3+x{y}^2.\end{array}$

以上两式相减，得

$Faf\left(T_{2,n};x,y\right)-Faf\left(T_{2,n-1};x,y\right)=2xy\left(Faf\left(T_{2,n-1};x,y\right)-Faf\left(T_{2,n-2};x,y\right)\right).$

即

$Faf\left(T_{2,n};x,y\right)=\left(1+2xy\right)Faf\left(T_{2,n-1};x,y\right)-2xyFaf\left(T_{2,n-2};x,y\right).$

推论2 当$n\ge \text{1}$ 时，在2-管状广义富勒烯图$T_{2,n}$ 双强迫多项式的递推关系中，令$x=1,y=\text{1},x=y=1$ ，可得$T_{2,n}$ 反强迫多项式，强迫多项式，完美匹配个数的递推关系

$F\left(T_{2,n},x\right)=2xF\left(T_{2,n-1},x\right)-2x^2+x,$

$Af\left(T_{2,n},y\right)=2yAf\left(T_{2,y-1},y\right)-2y^3+y^2,$

$\left|M\left(T_{2,n}\right)\right|=2\left|M\left(T_{2,n-1}\right)\right|-1.$

根据$T_{2,n}$ 的双强迫多项式的递推关系，先求解其通项公式，可得如下推论。

定理2 2-管状广义富勒烯图$T_{2,n}$ 的双强迫多项式的通项公式为

$Faf\left(T_{2,n};x,y\right)=2^{n+2}{x}^{n+2}{y}^{n+3}+x{y}^2.$

证明 由定理1得$T_{2,n}$ 的递推关系为

$Faf\left(T_{2,n};x,y\right)=2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3+x{y}^2.$

即

$\begin{array}{c}Faf\left(T_{2,n};x,y\right)-x{y}^2=2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3\\ =2xy\left(Faf\left(T_{2,n-1};x,y\right)-x{y}^2\right).\end{array}$

初始条件

$Faf\left(T_{2,1};x,y\right)-x{y}^2=8x^3{y}^4.$

因此

$\begin{array}{c}Faf\left(T_{2,n};x,y\right)-x{y}^2=\text{8}{x}^3{y}^4\cdot {\left(2xy\right)}^{n-1}\\ =2^{n+2}{x}^{n+2}{y}^{n+3}.\end{array}$

即

$Faf\left(T_{2,n};x,y\right)=2^{n+2}{x}^{n+2}{y}^{n+3}+x{y}^2.$

推论3 在$T_{2,n}$ 的双强迫多项式中，令$x=1,y=1,x=y=1$ ，可得2-管状广义富勒烯图$T_{2,n}$ 的反强迫多项式，强迫多项式，完美匹配的个数分别关于$n$ 的通项公式

$Faf\left(T_{2,n};x,y\right)=2^{n+2}{x}^{n+2}{y}^{n+3}+x{y}^2,$

$F\left(T_{2,n},x\right)=2^{n+2}{x}^{n+2}+x,$

$Af\left(T_{2,n},y\right)=2^{n+2}{y}^{n+3}+y^2,$

$\left|M\left(T_{2,n}\right)\right|=2^{n+2}+1.$

定理3 当$n\ge 1$ 时，2-管状广义富勒烯图$T_{2,n}$ 的双强迫多项式的生成函数为

$p\left(x,y,z\right)={\displaystyle \sum _{n\ge 0}Faf\left(T_{2,n};x,y\right)z^n}=\frac{x{y}^2\left(1+4xy\right)-6x^2{y}^{3}z}{\left(1-2xyz\right)\left(1-z\right)}.$

证明

$\begin{array}{c}p\left(x,y,z\right)={\displaystyle \sum _{n\ge 0}Faf\left(T_{2,n};x,y\right)z^n}\\ ={\displaystyle \sum _{n\ge \text{1}}Faf\left(T_{2,n};x,y\right)z^n}+Faf\left(T_{2,0};x,y\right)\\ ={\displaystyle \sum _{n\ge \text{1}}\left(2xyFaf\left(T_{2,n-1};x,y\right)-2x^2{y}^3+x{y}^2\right)z^n}+Faf\left(T_{2,0};x,y\right)\\ =2xyz{\displaystyle \sum _{n\ge 0}Faf\left(T_{2,n};x,y\right)z^n}+{\displaystyle \sum _{n\ge 1}\left(-2x^2{y}^3+x{y}^2\right)z^n}+Faf\left(T_{2,0};x,y\right)\\ =2xyzp\left(x,y,z\right)+\left(-2x^2{y}^3+x{y}^2\right)\frac{z}{1-z}+4x^2{y}^3+x{y}^2.\end{array}$

于是有

$\begin{array}{c}p\left(x,y,z\right)=\frac{\left(-2x^2{y}^3+x{y}^2\right)\cdot z+\left(1-z\right)\left(4x^2{y}^3+x{y}^2\right)}{\left(1-2xyz\right)\left(1-z\right)}\\ =\frac{x{y}^2\left(1+4xy\right)-6x^2{y}^{3}z}{\left(1-2xyz\right)\left(1-z\right)}.\end{array}$

推论4 当$n\ge 1$ 时，由定理3可知，在$T_{2,n}$ 的双强迫多项式的生成函数中，分别令$y=1,x=1$ ，$x=y=1$ 则可推出2-管状广义富勒烯图$T_{2,n}$ 的强迫多项式，反强迫多项式及完美匹配个数的生成函数为

${\displaystyle \sum _{n\ge 0}F\left(T_{2,n},x\right)z^n}=\frac{x\left(4x+1\right)-6x^{2}z}{\left(1-z\right)\left(1-2xz\right)},$

${\displaystyle \sum _{n\ge 0}F\left(T_{2,n},y\right)z^n}=\frac{y^2\left(4y+1\right)-6y^{3}z}{\left(1-z\right)\left(1-2yz\right)},$

${\displaystyle \sum _{n\ge 0}\left|M_{T_{2,n}}\right|z^n}=\frac{5-6z}{\left(1-2z\right)\left(1-z\right)}.$

结论：研究针对2-管状广义富勒烯图$T_{2,n}$ 的强迫谱与反强迫谱展开分析，发现其表现出高度的简并性，核心结构原因可归纳为以下两点：

1) 匹配的等价性。

$T_{2,n}$ 的所有完美匹配分为两个等价类，一类只有唯一的完美匹配$M_0$ ，其他完美匹配都是等价的(交叉的匹配边都可以通过后半截的图上下扭转转化为水平匹配边)，也就是存在$T_{2,n}$ 的自同构，所以它们的强迫数和反强迫数都是一样的。

2) 规则的梯式拓扑结构

$T_{2,n}$ 本质是由重复的4-圈单元沿“管身”方向串联构成的梯图变体，顶点与边的连接具有周期性和对称性。这种高度规则的结构使得不同位置的$M$ -交错圈、完美匹配具有拓扑同构性，因此强迫数与反强迫数的取值被严格限制，无法产生多样的数值分布。

下面给出$T_{2,n}\left(0\le n\le 15\right)$ 的双强迫多项式。

$\begin{array}{l}Faf\left(T_{2,0};x,y\right)=4x^2{y}^3+x{y}^2.\\ Faf\left(T_{2,1};x,y\right)=8x^{3}y{}^4+x{y}^2.\\ Faf\left(T_{2,2};x,y\right)=16x^4{y}^5+x{y}^2.\\ Faf\left(T_{2,3};x,y\right)=32x^5{y}^6+x{y}^2.\\ Faf\left(T_{2,4};x,y\right)=64x^6{y}^7+x{y}^2.\\ Faf\left(T_{2,5};x,y\right)=128x^7{y}^8+x{y}^2.\\ Faf\left(T_{2,6};x,y\right)=256x^8{y}^9+x{y}^2.\\ Faf\left(T_{2,7};x,y\right)=512x^9{y}^{10}+x{y}^2.\\ Faf\left(T_{2,8};x,y\right)=1024x^{10}{y}^{11}+x{y}^2.\\ Faf\left(T_{2,9};x,y\right)=2048x^{11}{y}^{12}+x{y}^2.\\ Faf\left(T_{2,10};x,y\right)=4096x^{12}{y}^{13}+x{y}^2.\\ Faf\left(T_{2,11};x,y\right)=8192x^{13}{y}^{14}+x{y}^2.\\ Faf\left(T_{2,12};x,y\right)=16384x^{14}{y}^{15}+x{y}^2.\\ Faf\left(T_{2,13};x,y\right)=32768x^{15}{y}^{16}+x{y}^2.\\ Faf\left(T_{2,14};x,y\right)=65536x^{16}{y}^{17}+x{y}^2.\\ Faf\left(T_{2,15};x,y\right)=131072x^{17}{y}^{18}+x{y}^2.\end{array}$

基金项目

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

NOTES

^*通讯作者。