Advances in Applied Mathematics
Vol.
10
No.
08
(
2021
), Article ID:
44787
,
7
pages
10.12677/AAM.2021.108299
Möbius梯状图的完美匹配的反强迫多项式和 卢卡斯数
刘雨童1,韩慧1,王杰彬2*
1西北师范大学,数学与统计学院,甘肃 兰州
2甘肃省酒泉中学,甘肃 酒泉
收稿日期:2021年7月23日;录用日期:2021年8月15日;发布日期:2021年8月26日
摘要
在本文中我们研究了Möbius梯状图MLn的反强迫谱,并得到了一个关于MLn的反强迫多项式和Lucas数列关系的等式。
关键词
Möbius梯状图MLn,完美匹配,反强迫谱,反强迫多项式,Lucas数列
The Anti-Forcing Polynomial of Perfect Matching of Möbius Ladder Graph and Lucas Number
Yutong Liu1, Hui Han1, Jiebin Wang2*
1College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu
2Jiuquan Middle School, Jiuquan Gansu
Received: Jul. 23rd, 2021; accepted: Aug. 15th, 2021; published: Aug. 26th, 2021
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 MLn and Lucas sequence.
Keywords:Möbius Ladder Graph MLn, Perfect Matching, Anti-Forcing Spectrum, Anti-Forcing Polynomial, Lucas Sequence
Copyright © 2021 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
Vukičević、Trinajstić和H. Lei、Y. Yeh、H. Zhang分别介绍了图G的反强迫数 [1]、完美匹配M的反强迫数及反强迫谱 [2]。设M是图G其中的一完美匹配。称子集 为M的反强迫集,若 有惟一的完美匹配M。M的最小反强迫集的大小被称为M的反强迫数,记作 。 。2015年,H. Hwang、H. Lei、Y. Yeh、H. Zhang介绍了图G的反强迫多项式的概念 [3] [4]。
在第1节中,我们介绍了一些定义、符号和结论。在第2节中,我们研究了Möbius梯状图 的反强迫数 和 的反强迫谱 。在第3节中,我们根据完美匹配的反强迫谱 和个数 ,得到了一个关于 的反强迫多项式和Lucas数列的等式。
2. 预备知识
设M是图G的一个完美匹配。
如果G中的两个M-交错圈要么不交,要么只相交在M中的边,则称它们是M-相容的。如果在一个集合 中任选2个M-交错圈都是M-相容的,则 就是一个相容M-交错集。我们用 表示图G的最大相容M-交错集的大小。
定义1 [3] [4] 图G的反强迫多项式定义为:
其中 表示的是反强迫数为i的完美匹配的数目,M表示G的全部完美匹配所组成的集合。
引理1 [2] 若M是图G其中一完美匹配,则 。若图G是平面二部图,则
.
定义2 梯子图 ,现将 水平放置,将其顶点依次标号为 。如图1 [5]。
Figure 1. Ladder graph
图1. 梯子图
在图 中,边 和边 分别被称为竖直边和水平边。设M是图 的完美匹配, 称为M的竖直边, 称为M的水平边。
定义3 在梯子图 上添加边 和 就得到循环梯状图 ,即 ,,如图2 [5]。类似地,在梯子图 上添加边 和 就得到Möbius梯状图 ,如图3 [6]。
Figure 2. Cyclic ladder graph
图2. 循环梯状图
Figure 3. Möbius ladder graph
图3. Möbius梯状图
类比于 ,在图 和 中,类似于 的边叫做竖直边,类似于 的边叫做水平边。设M是图 和 中的一完美匹配, 称作M的竖直匹配边, 称作M的水平匹配边。
在本节的引理中,我们都给定M是 的一个完美匹配,故下面引理中不在赘述。
引理2 [7] 设M有 条竖直匹配边,则 ,并且 。
定理1 [5] 如果 ,,则 ,,, 和 分别是 关于顶点集 和 导出的梯子图。
Lucas数列中 ,,且它的递推关系为 。
引理3 [8] Lucas数列的第n项为 。
显然, 、 、 都是Hamilton圈。
引理4 当 时,从 中删去所有竖直边后,所有水平边(含 和 )构成的图正好是一个2n长的圈 ,一定存在完美匹配。
3. Möbius梯状图的反强迫谱
设M是 中含有p条竖直匹配边的完美匹配,设 。如果边 或 在M-交错圈C中同时存在,则称M-交错圈C跨过 。
引理5 [5] 在 中,如果边 或 在M-交错圈C中同时存在。则当n为奇数时,M-交错圈必然会跨过p条竖直边,从而有且仅有两个 长的M-交错圈;而当n是偶数时,不存在M-交错圈。
我们在边 处把 分裂成了 ,如图4 [6] 所示。在 中,假设 是两条相继竖直边,则由 以及它们中间的全部水平边构成的子图被称为 的片段。
Figure 4. is decomposed into at edge
图4. 在边 处分裂为
同理于 的分解定理,对于 我们有
定理2 设M是 的完美匹配,而且M含有 条竖直匹配边,则 ,,, 是 的p个片段。
引理6 设 ,M是 的完美匹配,且 ,则有 。
证明 当 时,n可以是偶数,也可以是奇数,从而分情况讨论。设 。
情形1:n是偶数时, 。(此时 ,如下图5 [6] )。相容M-交错集 是由 个M-交错4圈及M-交错圈C构成的,从而 ,所以有 。在 中取M的反强迫集 ,且 。所以 。
综上所述,当n是偶数且 时, 。
情形2:n为奇数时, (此时M中水平匹配边不成对出现,如下图6 [6] )。取M-交错圈 ,,,得到相容M-交错集 ,此时 ,所以有 。取 是 的一个反强迫集,并且 ,所以 。
Figure 5. The perfect matching M of
图5. 的完美匹配M
Figure 6. The perfect matching M of
图6. 的完美匹配M
综上所述,当n是奇数且 时, 。
根据引理6,我们有下面的引理。
引理7 设M是 的一个含有p条竖直边的完美匹配。当 ,n可以是偶数,也可以是奇数;只有n是偶数时,水平匹配边才成对出现。而当 时,一定有 ,且 。
引理8 设 ,M是 的完美匹配,且 ,则有 。
证明 当 时,n必为奇数。在 中取M-交错圈 , 和 个与 M-相容的M-交错4圈,得到相容M-交错集 ,所以 ,所以有 。 在中取M的反强迫集 ,且 。所以 。
综上所述,当 是奇数且 时, 。
引理9 设 ,M是 的一个含p条竖直边的完美匹配, ,则M的反强迫数为 。
证明 当 时,在 中,相容M-交错集 中包含 个M-交错4圈和p个M-交错圈,此时 ,所以有 。
在M的p条竖直边处把 分裂成p个片段 ,然后从第一个片段里取出反强迫集 ,从而 的反强迫集的并S就是 的一个反强迫集,并且
,因此有 。
综上所述,可得当 时,有 。
在引理6,引理8,引理9的证明过程中,我们需要借助 [9] 中引理5,从而我们得到了下面的定理。
定理3
从而当 为奇数时 是不连续的;当 为偶数或 时 是连续的。
我们根据定理3,容易得出下面的推论。
推论1 1)
2) 。
4. Möbius梯状图MLn的完美匹配和Lucas数列的关系
定理4 在Möbius梯状图MLn中,设包含2q条水平边的完美匹配一共有 个,则 。
证明 当n是奇数时,p也是奇数。设M是 的一个完美匹配,且M含有2q条水平匹配边必成对
出现,则M含有 条竖直匹配边,其中 ,。
当 时,当我们删掉 这4个顶点后就得到了 ,所以只需要计算出 (含有 条水平匹配边)的完美匹配个数即可,设 有 个完美匹配,故根据 [5] 中推论2得到 。
当 时,设 的完美匹配个数 ,删掉水平边 后就得到了 ,从而我们只需要计算出 (包含2q条水平匹配边)的完美匹配个数即可,故根据 [5] 中推论2可得
。
因此当n为奇数且 时, 。
当n为奇数,且 与 不同时存在时,有 ,且 。
当n是偶数时,p也为偶数。设M是 的一个完美匹配,且M含有2q条水平匹配边必成对出现,则M含有 条竖直匹配边,其中 ,。当 时,类似于n为奇数时,将 化为梯子图计算,就有 ;而当 时, ,就有 。
由定理3和定理4,我们有下面这个定理。
定理5 的反强迫多项式为:
根据引理3和定理5,我们有:
推论2 Möbius梯状图 的完美匹配个数 。
注:这与循环梯状图 中的结论,奇偶是相反的,详细可见 [3]。
基金项目
地区科学基金(12161081)。
文章引用
刘雨童,韩 慧,王杰彬. MO¨bius梯状图的完美匹配的反强迫多项式和卢卡斯数
The Anti-Forcing Polynomial of Perfect Matching of MO¨bius Ladder Graph and Lucas Number[J]. 应用数学进展, 2021, 10(08): 2868-2874. https://doi.org/10.12677/AAM.2021.108299
参考文献
- 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.
NOTES
*通讯作者。