几类梯状图的完美匹配与Hamilton圈
Perfect Matching of Several Types of Ladder Graphs and Hamilton Cycles
DOI: 10.12677/PM.2023.136173, PDF,    国家自然科学基金支持
作者: 王彦通：西北师范大学数学与统计学院，甘肃 兰州
关键词: 梯子图Ln；循环梯状图CLn；M?bius梯状图MLn；Hamilton圈；完美匹配；Ladder Graph Ln； Cyclic Ladder Graph CLn； M?bius Ladder Graph MLn； Hamilton Cycles； Perfect Matching
摘要: 循环梯状图CLn是由圈Cn和路p2的笛卡尔积CLn=Cn×p2(n≥3)，Möbius梯状图MLn是通过梯子图Ln添加边a1bn和b1an得到。删掉CLn和MLn的一个Hamilton圈(删边不删点)后剩下的子图是它们的一个完美匹配。反之，删掉CLn和MLn的一个完美匹配后剩下的子图只要是连通的，那一定是原图的Hamilton圈。因此本文通过删除完美匹配的方法给出了Ln，CLn和MLn的所有Hamilton圈，进而通过Hamilton圈研究了完美匹配之间的关系。
Abstract: The cyclic ladder graph CLn is obtained from the Cartesian product CLn=Cn×p2(n≥3) of cycles Cn and paths p2 and the Möbius ladder graph MLn is obtained by adding edges a1bn and b1an to the ladder graph Ln. The remaining subgraphs after we delete a Hamilton cycle of CLn and MLn (deleting edges without deleting points) are a perfect matching of them. Conversely, the re-maining subgraphs after deleting a perfect matching of CLn and MLn must be a Hamilton cycle of the original graph as long as they are connected. Therefore, this paper gives all Hamilton cycles of Ln, CLn and MLn by deleting perfect matching, and then investigates the relationship between perfect matching through Hamilton cycles.
文章引用：王彦通. 几类梯状图的完美匹配与Hamilton圈[J]. 理论数学, 2023, 13(6): 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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[4] Adams, P., Mahdian, M. and Mahmoodian, E.S. (2004) On the Forced Matching Numbers of Bipartite Graphs. Discrete Mathematics, 281, 1-12. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[8] Vhukičević, D. and Trinajstić, N. (2007) On the Anti-Forcing Number of Benzenoids. Journal of Mathematical Chemistry, 42, 575-583. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[13] Deng, K. and Zhang, H. (2017) Anti-Forcing Spectra of Perfect Matchings of Graphs. Journal of Combinatorial Optimization, 33, 660-680. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[15] Zhao, S. and Zhang, H. (2018) Anti-Forcing Polynomials for Benzenoids Systems with Forcing Edges. Discrete Applied Mathematics, 250, 342-356. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[23] 刘雨童. 60阶富勒烯图的双强迫多项式[D]: [硕士学位论文]. 兰州: 西北师范大学, 2022.
[24] 邓凯. 线性亚苯基系统的强迫和反强迫多项式[J]. 高校应用数学学报A辑, 2022, 37(4): 491-500.
[25] 王杰彬. 几类特殊图的反强迫谱的研究[D]: [硕士学位论文]. 兰州: 西北师范大学, 2018.

为你推荐