MO¨bius梯状图的完美匹配的反强迫多项式和卢卡斯数

期刊菜单

MO^¨bius梯状图的完美匹配的反强迫多项式和卢卡斯数
The Anti-Forcing Polynomial of Perfect Matching of MO ^¨bius Ladder Graph and Lucas Number

DOI:10.12677/AAM.2021.108299,PDF,HTML,XML,被引量下载: 423浏览: 632科研立项经费支持
作者:刘雨童,韩慧：西北师范大学，数学与统计学院，甘肃兰州；王杰彬^*：甘肃省酒泉中学，甘肃酒泉
关键词:MO^¨bius梯状图MLn；完美匹配；反强迫谱；反强迫多项式；Lucas数列；MO^¨bius Ladder Graph MLn；Perfect Matching；Anti-Forcing Spectrum；Anti-Forcing Polynomial；Lucas Sequence

摘要:在本文中我们研究了Möbius梯状图ML _n的反强迫谱，并得到了一个关于MLn的反强迫多项式和Lucas数列关系的等式。

Abstract:In this paper, we study the anti-forcing spectrum of MLn and get an equation about the relationship between the anti-forcing polynomial of ML _nand Lucas sequence.

文章引用：刘雨童, 韩慧, 王杰彬. MO ^¨bius梯状图的完美匹配的反强迫多项式和卢卡斯数[J]. 应用数学进展, 2021, 10(8): 2868-2874. https://doi.org/10.12677/AAM.2021.108299

1. 引言

Vukičević、Trinajstić和H. Lei、Y. Yeh、H. Zhang分别介绍了图G的反强迫数 [1]、完美匹配M的反强迫数及反强迫谱 [2]。设M是图G其中的一完美匹配。称子集 $S_{a} \subseteq E (G) \ M$ 为M的反强迫集，若 $G - S_{a}$ 有惟一的完美匹配M。M的最小反强迫集的大小被称为M的反强迫数，记作 $a f (G, M)$ 。 $S p e c_{a f} (G) = {a f (G, M) | M 是 G 的任一完美匹配}$ 。2015年，H. Hwang、H. Lei、Y. Yeh、H. Zhang介绍了图G的反强迫多项式的概念 [3] [4]。

在第1节中，我们介绍了一些定义、符号和结论。在第2节中，我们研究了Möbius梯状图 $M L_{n}$ 的反强迫数 $a f (M L_{n}, M)$ 和 $M L_{n}$ 的反强迫谱 $S p e c_{a f} (M L_{n})$ 。在第3节中，我们根据完美匹配的反强迫谱 $S p e c_{a f} (M L_{n})$ 和个数 $| M |$ ，得到了一个关于 $M L_{n}$ 的反强迫多项式和Lucas数列的等式。

2. 预备知识

设M是图G的一个完美匹配。

如果G中的两个M-交错圈要么不交，要么只相交在M中的边，则称它们是M-相容的。如果在一个集合 $A$ 中任选2个M-交错圈都是M-相容的，则 $A$ 就是一个相容M-交错集。我们用 $c^{'} (M)$ 表示图G的最大相容M-交错集的大小。

定义1 [3] [4] 图G的反强迫多项式定义为：

$A f (G, x) = \sum_{M \in Μ} x^{a f (G, M)} = \sum_{i = a f (G, M)}^{A f (G, M)} ϖ (G, i) x^{i}$

其中 $ϖ (G, i)$ 表示的是反强迫数为i的完美匹配的数目，M表示G的全部完美匹配所组成的集合。

引理1 [2] 若M是图G其中一完美匹配，则 $a f (G, M) \geq c^{'} (M)$ 。若图G是平面二部图，则

$a f (G, M) = c^{'} (M)$ .

定义2 梯子图 $L_{n} = P_{n} \times P_{2}$ ，现将 $L_{n}$ 水平放置，将其顶点依次标号为 $a_{1}, a_{2}, \dots, a_{n}, b_{1}, b_{2}, \dots, b_{n}$ 。如图1[5]。

Figure 1. Ladder graph $L_{n}$

图1. 梯子图 $L_{n}$

在图 $L_{n}$ 中，边 $a_{i} b_{i}$ 和边 $a_{i} a_{i + 1}, b_{i} b_{i + 1}$ 分别被称为竖直边和水平边。设M是图 $L_{n}$ 的完美匹配， $a_{i} b_{i} \in M$ 称为M的竖直边， $a_{i} a_{i + 1}, b_{i} b_{i + 1} \in M$ 称为M的水平边。

定义3 在梯子图 $L_{n}$ 上添加边 $a_{1} a_{n}$ 和 $b_{1} b_{n}$ 就得到循环梯状图 $C L_{n}$ ，即 $C L_{n} = C_{n} \times P_{2}$ ， $n \geq 3$ ，如图2[5]。类似地，在梯子图 $L_{n}$ 上添加边 $a_{1} b_{n}$ 和 $a_{n} b_{1}$ 就得到Möbius梯状图 $M L_{n}$ ，如图3[6]。

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

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

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

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

类比于 $L_{n}$ ，在图 $C L_{n}$ 和 $M L_{n}$ 中，类似于 $a_{i} b_{i}$ 的边叫做竖直边，类似于 $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} a_{n}, b_{1} b_{n}, a_{1} b_{n}, a_{n} b_{1}$ 的边叫做水平边。设M是图 $C L_{n}$ 和 $M L_{n}$ 中的一完美匹配， $a_{i} b_{i} \in M$ 称作M的竖直匹配边， $a_{i} a_{i + 1}, b_{i} b_{i + 1}, a_{1} a_{n}, b_{1} b_{n}, a_{1} b_{n}, a_{n} b_{1} \in M$ 称作M的水平匹配边。

在本节的引理中，我们都给定M是 $L_{n}$ 的一个完美匹配，故下面引理中不在赘述。

引理2 [7] 设M有 $p (p \geq 1)$ 条竖直匹配边，则 $n \equiv p (\mod 2)$ ，并且 $a_{i} a_{i + 1} \in M \Leftrightarrow b_{i} b_{i + 1} \in M$ 。

定理1 [5] 如果 $a_{i} b_{i} \in M$ ， $2 \leq i \leq n - 1$ ，则 $a f (L_{n}, M) = a f (L^{(1)}, M_{1}) + a f (L^{(2)}, M_{2})$ ， $M_{j} = M \cap E (L^{(j)})$ ， $j = 1, 2$ ， $L^{(1)}$ 和 $L^{(2)}$ 分别是 $L_{n}$ 关于顶点集 ${a_{1}, a_{2}, \dots, a_{i}, b_{1}, b_{2}, \dots, b_{i}}$ 和 ${a_{i}, a_{i + 1}, \dots, a_{n}, b_{i}, b_{i + 1}, \dots, b_{n}}$ 导出的梯子图。

Lucas数列中 $l_{0} = 2$ ， $l_{1} = 1$ ，且它的递推关系为 $l_{n} = l_{n - 1} + l_{n - 2}$ 。

引理3 [8] Lucas数列的第n项为 $l_{n} = \sum_{i = 0}^{n} \frac{n}{n - i} (\begin{matrix} n - i \\ i \end{matrix})$ 。

显然， $L_{n}$ 、 $C L_{n}$ 、 $M L_{n}$ 都是Hamilton圈。

引理4 当 $p = 0$ 时，从 $M L_{n}$ 中删去所有竖直边后，所有水平边(含 $a_{1} b_{n}$ 和 $a_{n} b_{1}$ )构成的图正好是一个2n长的圈 $C_{2 n} = a_{1} a_{2} \dots a_{n} b_{1} b_{2} \dots b_{n} a_{1}$ ，一定存在完美匹配。

3. Möbius梯状图的反强迫谱

设M是 $M L_{n}$ 中含有p条竖直匹配边的完美匹配，设 $a_{1} b_{1} \in M$ 。如果边 $b_{n} a_{1}, a_{1} b_{1}, b_{1} b_{2}$ 或 $a_{n} b_{1}, b_{1} a_{1}, a_{1} a_{2}$ 在M-交错圈C中同时存在，则称M-交错圈C跨过 $a_{1} b_{1}$ 。

引理5 [5] 在 $M L_{n}$ 中，如果边 $b_{n} a_{1}, a_{1} b_{1}, b_{1} b_{2}$ 或 $a_{n} b_{1}, b_{1} a_{1}, a_{1} a_{2}$ 在M-交错圈C中同时存在。则当n为奇数时，M-交错圈必然会跨过p条竖直边，从而有且仅有两个 $n + p$ 长的M-交错圈；而当n是偶数时，不存在M-交错圈。

我们在边 $a_{1} b_{1}$ 处把 $M L_{n}$ 分裂成了 $L_{n + 1}$ ，如图4[6] 所示。在 $L_{n + 1}$ 中，假设 $a_{i} b_{i}, a_{j} b_{j} \in M$ 是两条相继竖直边，则由 $a_{i} b_{i}, a_{j} b_{j}$ 以及它们中间的全部水平边构成的子图被称为 $M L_{n}$ 的片段。

Figure 4. $M L_{n}$ is decomposed into $L_{n + 1}$ at edge $a_{1} b_{1}$

图4. $M L_{n}$ 在边 $a_{1} b_{1}$ 处分裂为 $L_{n + 1}$

同理于 $L_{n}$ 的分解定理，对于 $M L_{n}$ 我们有

定理2 设M是 $M L_{n}$ 的完美匹配，而且M含有 $p (p \geq 2)$ 条竖直匹配边，则 $a f (M L_{n}, M) = a f (L^{(1)}, M_{1}) + a f (L^{(2)}, M_{2}) + \dots + a f (L^{(p)}, M_{p})$ ， $M_{j} = M \cap E (L^{(j)})$ ， $j = 1, 2, \dots, p$ ， $L^{(1)}, L^{(2)}, \dots, L^{(p)}$ 是 $M L_{n}$ 的p个片段。

引理6 设 $n \geq 2$ ，M是 $M L_{n}$ 的完美匹配，且 $p = 0$ ，则有 $a f (M L_{n}, M) = {\begin{array}{l} \frac{n + 2}{2}, & n 为偶数 \\ 3, & n 为奇数 \end{array}$ 。

证明当 $p = 0$ 时，n可以是偶数，也可以是奇数，从而分情况讨论。设 $a_{1} a_{2} \in M$ 。

情形1：n是偶数时， $M = {a_{1} a_{2}, a_{3} a_{4}, \dots, a_{n - 1} a_{n}, b_{1} b_{2}, \dots, b_{n - 1} b_{n}}$ 。(此时 $a_{i} a_{i + 1} \in M \Leftrightarrow b_{i} b_{i + 1} \in M$ ，如下图5[6] )。相容M-交错集 $A$ 是由 $\frac{n}{2}$ 个M-交错4圈及M-交错圈C构成的，从而 $| A | = \frac{n}{2} + 1 = \frac{n + 2}{2}$ ，所以有 $a f (M L_{n}, M) \geq | A | = \frac{n + 2}{2}$ 。在 $M L_{n}$ 中取M的反强迫集 $S = {a_{1} b_{n}, a_{1} b_{1}, a_{3} b_{3}, \dots, a_{n - 1} b_{n - 1}}$ ，且 $| S | = \frac{n + 2}{2}$ 。所以 $a f (M L_{n}, M) \leq | S | = \frac{n + 2}{2}$ 。

综上所述，当n是偶数且 $p = 0$ 时， $a f (M L_{n}, M) = \frac{n + 2}{2}$ 。

情形2：n为奇数时， $M = {a_{1} a_{2}, a_{3} a_{4}, \dots, a_{n - 2} a_{n - 1}, a_{n} b_{1}, b_{2} b_{3}, \dots, b_{n - 1} b_{n}}$ (此时M中水平匹配边不成对出现，如下图6[6] )。取M-交错圈 $C_{1} = b_{1} b_{2} \dots b_{n} a_{n} b_{1}$ ， $C_{2} = b_{1} a_{1} a_{2} \dots a_{n} b_{1}$ ， $C_{3} = a_{1} a_{2} b_{2} b_{3} a_{3} a_{4} \dots b_{n - 1} b_{n} a_{1}$ ，得到相容M-交错集 $A$ ，此时 $| A | = 3$ ，所以有 $a f (M L_{n}, M) \geq | A | = 3$ 。取 $S = {a_{1} b_{n}, a_{1} b_{1}, b_{1} b_{2}}$ 是 $M L_{n}$ 的一个反强迫集，并且 $| S | = 3$ ，所以 $a f (M L_{n}, M) \leq 3$ 。

Figure 5. The perfect matching M of $M L_{n}$

图5. $M L_{n}$ 的完美匹配M

Figure 6. The perfect matching M of $M L_{n}$

图6. $M L_{n}$ 的完美匹配M

综上所述，当n是奇数且 $p = 0$ 时， $a f (M L_{n}, M) = 3$ 。

根据引理6，我们有下面的引理。

引理7 设M是 $M L_{n}$ 的一个含有p条竖直边的完美匹配。当 $p = 0$ ，n可以是偶数，也可以是奇数；只有n是偶数时，水平匹配边才成对出现。而当 $p \geq 1$ 时，一定有 $n \equiv p (\mod 2)$ ，且 $a_{i} a_{i + 1} \in M \Leftrightarrow b_{i} b_{i + 1} \in M$ 。

引理8 设 $n \geq 2$ ，M是 $M L_{n}$ 的完美匹配，且 $p = 1$ ，则有 $a f (M L_{n}, M) = \frac{n + 3}{2}$ 。

证明当 $p = 1$ 时，n必为奇数。在 $M L_{n}$ 中取M-交错圈 $C_{1} = a_{1} a_{2} \dots a_{n} b_{1} a_{1}$ ， $C_{2} = b_{1} b_{2} \dots b_{n} a_{1} b_{1}$ 和 $\frac{n - 1}{2}$ 个与 $C_{1}, C_{2}$ M-相容的M-交错4圈，得到相容M-交错集 $A$ ，所以 $| A | = 2 + \frac{n - 1}{2} = \frac{n + 3}{2}$ ，所以有 $a f (M L_{n}, M) \geq c^{'} (M) \geq | A | = \frac{n + 3}{2}$ 。 $M L_{n}$ 在中取M的反强迫集 $S = {a_{1} b_{n}, a_{1} a_{2}, a_{2} b_{2}, a_{4} b_{4}, \dots, a_{n - 1} b_{n - 1}}$ ，且 $| S | = \frac{n + 3}{2}$ 。所以 $a f (M L_{n}, M) \leq | S | = \frac{n + 3}{2}$ 。

综上所述，当 $n \geq 3$ 是奇数且 $p = 1$ 时， $a f (M L_{n}, M) = \frac{n + 3}{2}$ 。

引理9 设 $n \geq 2$ ，M是 $M L_{n}$ 的一个含p条竖直边的完美匹配， $2 \leq p \leq n$ ，则M的反强迫数为 $a f (M L_{n}, M) = \frac{n + p}{2}$ 。

证明当 $2 \leq p \leq n$ 时，在 $M L_{n}$ 中，相容M-交错集 $A$ 中包含 $\frac{n - p}{2}$ 个M-交错4圈和p个M-交错圈，此时 $| A | = p + \frac{n - p}{2} = \frac{n + p}{2}$ ，所以有 $a f (M L_{n}, M) \geq c^{'} (M) \geq | A | = \frac{n + p}{2}$ 。

在M的p条竖直边处把 $M L_{n}$ 分裂成p个片段 ${d_{1}, d_{2}, \dots, d_{p}}$ ，然后从第一个片段里取出反强迫集 $S_{1} = {a_{1} a_{2}, a_{2} b_{2}, a_{4} b_{4}, \dots, a_{2 i - 2} b_{2 i - 2}}$ ，从而 $d_{i} (1 \leq i \leq p)$ 的反强迫集的并S就是 $M L_{n}$ 的一个反强迫集，并且

$| S | = \frac{n + p}{2}$ ，因此有 $a f (M L_{n}, M) \leq | S | = \frac{n + p}{2}$ 。

综上所述，可得当 $2 \leq p \leq n$ 时，有 $a f (M L_{n}, M) = \frac{n + p}{2}$ 。

在引理6，引理8，引理9的证明过程中，我们需要借助 [9] 中引理5，从而我们得到了下面的定理。

定理3

$S p e c_{a f} (M L_{n}) = {\begin{array}{l} {3}, & n = 3 \\ {3, \frac{n + 3}{2}, \frac{n + 5}{2}, \dots, n}, & n \geq 5 是奇数 \\ {\frac{n + 2}{2}, \frac{n + 4}{2}, \dots, n}, & n \geq 2 是偶数 \end{array}$

从而当 $n \geq 7$ 为奇数时 $S p e c_{a f} (M L_{n})$ 是不连续的；当 $n \geq 2$ 为偶数或 $n = 3, 5$ 时 $S p e c_{a f} (M L_{n})$ 是连续的。

我们根据定理3，容易得出下面的推论。

推论1 1) $a f (M L_{n}) = {\begin{array}{l} 3, 若 n \geq 3 是奇数 \\ \frac{n + 2}{2}, 若 n \geq 2 是偶数 \end{array}$

2) $A f (M L_{n}) = n$ 。

4. Möbius梯状图ML_n的完美匹配和Lucas数列的关系

定理4 在Möbius梯状图ML_n中，设包含2q条水平边的完美匹配一共有 $| M |$ 个，则 $| M | = \frac{n}{n - q} (\begin{matrix} n - q \\ n \end{matrix})$ 。

证明当n是奇数时，p也是奇数。设M是 $M L_{n}$ 的一个完美匹配，且M含有2q条水平匹配边必成对

出现，则M含有 $p = n - 2 q$ 条竖直匹配边，其中 $0 \leq q \leq \frac{n - 1}{2}$ ， $1 \leq p \leq n$ 。

当 $a_{1} b_{n}, b_{1} a_{n} \in M$ 时，当我们删掉 $a_{1}, b_{1}, a_{n}, b_{n}$ 这4个顶点后就得到了 $L_{n - 2}$ ，所以只需要计算出 $L_{n - 2}$ (含有 $2 q - 2$ 条水平匹配边)的完美匹配个数即可，设 $M L_{n}$ 有 $| M_{1} |$ 个完美匹配，故根据 [5] 中推论2得到 $| M_{1} | = (\begin{matrix} \frac{n - 2 - p}{2} + p \\ p \end{matrix}) = (\begin{matrix} \frac{n + p - 2}{2} \\ p \end{matrix}) = (\begin{matrix} n - q - 1 \\ n - 2 q \end{matrix}) = (\begin{matrix} n - q - 1 \\ q - 1 \end{matrix})$ 。

当 $a_{1} b_{n}, b_{1} a_{n} \notin M$ 时，设 $M L_{n}$ 的完美匹配个数 $| M_{2} |$ ，删掉水平边 $a_{1} b_{n}, b_{1} a_{n}$ 后就得到了 $L_{n}$ ，从而我们只需要计算出 $L_{n}$ (包含2q条水平匹配边)的完美匹配个数即可，故根据 [5] 中推论2可得

$| M_{2} | = (\begin{matrix} \frac{n - p}{2} + p \\ p \end{matrix}) = (\begin{matrix} \frac{n + p}{2} \\ p \end{matrix}) = (\begin{matrix} n - q \\ n - 2 q \end{matrix}) = (\begin{matrix} n - q \\ q \end{matrix})$ 。

因此当n为奇数且 $p \geq 1$ 时， $| M | = | M_{1} | + | M_{2} | = \frac{n}{n - q} (\begin{matrix} n - q \\ q \end{matrix})$ 。

当n为奇数，且 $a_{i} a_{i + 1} \in M$ 与 $b_{i} b_{i + 1} \in M$ 不同时存在时，有 $n = q$ ，且 $| M | = 2$ 。

当n是偶数时，p也为偶数。设M是 $M L_{n}$ 的一个完美匹配，且M含有2q条水平匹配边必成对出现，则M含有 $p = n - 2 q$ 条竖直匹配边，其中 $0 \leq q \leq \frac{n}{2}$ ， $0 \leq p \leq n$ 。当 $p \geq 2$ 时，类似于n为奇数时，将 $M L_{n}$ 化为梯子图计算，就有 $| M | = \frac{n}{n - q} (\begin{matrix} n - q \\ q \end{matrix})$ ；而当 $p = 0$ 时， $n = 2 q$ ，就有 $\frac{2 q}{2 q - q} (\begin{matrix} 2 q - q \\ q \end{matrix}) = 2 = | M |$ 。

由定理3和定理4，我们有下面这个定理。

定理5 $M L_{n}$ 的反强迫多项式为：

$A f (M L_{n}, x) = {\begin{cases} 3 x^{2}, n = 2 \\ 6 x^{3}, n = 3 \\ 2 x^{3} + (\frac{n (n^{2} - 1)}{24} + n) x^{\frac{n + 3}{2}} + \sum_{q = 0}^{\frac{n - 5}{2}} \frac{n}{n - q} (\begin{matrix} n - q \\ q \end{matrix}) x^{n - q}, n \geq 5 是奇数 \\ (\frac{n^{2}}{4} + 2) x^{\frac{n + 2}{2}} + \sum_{q = 0}^{\frac{n - 4}{2}} \frac{n}{n - q} (\begin{matrix} n - q \\ q \end{matrix}) x^{n - q}, n \geq 4 是偶数 \end{cases}$

根据引理3和定理5，我们有：

推论2 Möbius梯状图 $M L_{n}$ 的完美匹配个数 $| M | = {\begin{array}{l} l_{n} + 2, & 若 n \geq 3 是奇数 \\ l_{n}, & 若 n \geq 2 是偶数 \end{array}$ 。

注：这与循环梯状图 $C L_{n}$ 中的结论，奇偶是相反的，详细可见 [3]。

基金项目

地区科学基金(12161081)。

NOTES

^*通讯作者。

参考文献

[1]	Vukiě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
[2]	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
[3]	赵爽. 关于一些图类的强迫与反强迫多项式的研究[D]: [博士学位论文]. 兰州: 兰州大学, 2018.
[4]	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
[5]	姚海元, 王杰彬, 王旭. 循环梯状图的完美匹配的反强迫谱与卢卡斯数[J]. 西北师范大学学报(自然科学版), 2018, 54(2): 21-25, 29.
[6]	王杰彬. 几类特殊图的反强迫谱的研究[D]: [硕士学位论文]. 兰州: 西北师范大学, 2018.
[7]	Vukiěević, D. and Trinajstić, N. (2008) On the Anti-Kekule Number and Anti-Forcing Number of Cata-Condensed Benzenoids. Journal of Mathematical Chemistry, 43, 719-726. https://doi.org/10.1007/s10910-006-9223-5
[8]	Koshy, T. (2001) Fibonacci and Lucas Numbers with Applications. Wiley, New York.
[9]	韩振云, 王杰彬. 梯子图的完美匹配的反强迫谱与斐波那契数列[J]. 兰州工业学院学报, 2020, 27(1): 85-90.

为你推荐

友情链接