|
|
一类管状富勒烯图的完美匹配数
|
Abstract:
富勒烯图是3-连通3-正则平面图，并且恰好具有12个五边形面，其余的面都是六边形面。本文研究的富勒烯图是由六个同心的六边形层组成，两端都由一个六边形以及与这个六边形相邻的六个五边形面构成的顶盖封口。我们把该类富勒烯图称为管状富勒烯图。完美匹配计数在量子化学领域以及统计物理领域中具有广泛的应用，并且已被证实完美匹配计数问题是一个NP-难的问题。本文主要通过划分、求和以及嵌套递推的方式求出管状富勒烯图的完美匹配数。
A fullerene graph is 3-connected cubic planar graph, and has exactly 12 pentagonal faces, the rest of which are hexagonal faces. The fullerene graph studied in this paper is composed of six concentric layers of hexagons, capped on each end by a cap formed by a hexagon and six pentagonal faces adjacent to the hexagon. This kind of fullerene graphs is called tubular fullerene graphs. The problem of counting the number of perfect matching is widely used in the field of quantum chemistry and statistical physics, and it has been proved that the problem of counting the number of perfect matching is NP-hard. In this paper, the number of perfect matching of tubular fullerene graphs is obtained by means of partition, summation and nested recursion.
| [1] | 胡启明, 许欢, 袁晓彤. 图的覆盖数与分子的凯库勒结构[J]. 长春师范大学学报, 2022, 41(4): 17-21. |
| [2] | 严正, 娄捷, 陈焱, 漏燕娣, 林志. 对量子dimer模型实现全拓扑类抽样的量子蒙特卡洛方法[P]. 中国专利, 201910162497. X. 2019-06-07. |
| [3] | Smith, D.K., Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1994) Network Flows: Theory, Algorithms, and Applications. The Journal of the Operational Research Society, 45, 1340. https://doi.org/10.2307/2583863 |
| [4] | 黄银峰, 李艳红, 姚静怡, 罗昌银. 基于稀疏采样数据的复杂路网地图匹配算法[J]. 中南民族大学学报(自然科学版), 2024, 43(4): 522-531. |
| [5] | Valiant, L.G. (1979) The Complexity of Computing the Permanent. Theoretical Computer Science, 8, 189-201. https://doi.org/10.1016/0304-3975(79)90044-6 |
| [6] | Kasteleyn, P.W. (1961) The Statistics of Dimers on a Lattice: I. The Number of Dimer Arrangements on a Quadratic Lattice. Physica, 27, 1209-1225. https://doi.org/10.1016/0031-8914(61)90063-5 |
| [7] | Kasteleyn, P.W. (1967) Graph Theory and Crystal Physics. In: Harary, F., Ed., Graph Theory and Theoretical Physics, Academic Press, 43-110. |
| [8] | Little, C.H.C. (1974) An Extension of Kasteleyn’s Method of Enumerating the 1-Factors of Planar Graphs. In: Holton, D.A., Ed., Combinatorial Mathematics, Springer, 63-72. https://doi.org/10.1007/bfb0057377 |
| [9] | Little, C.H.C. (1975) A Characterization of Convertible (0, 1)-Matrices. Journal of Combinatorial Theory, Series B, 18, 187-208. https://doi.org/10.1016/0095-8956(75)90048-9 |
| [10] | Lu, W.T. and Wu, F.Y. (2002) Close-packed Dimers on Nonorientable Surfaces. Physics Letters A, 293, 235-246. https://doi.org/10.1016/s0375-9601(02)00019-1 |
| [11] | Ciucu, M. (1997) Enumeration of Perfect Matchings in Graphs with Reflective Symmetry. Journal of Combinatorial Theory, Series A, 77, 67-97. https://doi.org/10.1006/jcta.1996.2725 |
| [12] | Zhang, F. and Yan, W. (2003) Enumeration of Perfect Matchings in a Type of Graphs with Reflective Symmetry. Match Communications in Mathematical & in Computer Chemistry, 48, 117-124. |
| [13] | Yan, W. and Zhang, F. (2004) Enumeration of Perfect Matchings of Graphs with Reflective Symmetry by Pfaffians. Advances in Applied Mathematics, 32, 655-668. https://doi.org/10.1016/s0196-8858(03)00097-6 |
| [14] | Yan, W. and Zhang, F. (2006) Enumeration of Perfect Matchings of a Type of Cartesian Products of Graphs. Discrete Applied Mathematics, 154, 145-157. https://doi.org/10.1016/j.dam.2005.07.001 |
| [15] | Propp, J. (1999) Enumerations of Matchings: Problems and Progress. In: Billera, L.J., et al., Eds., New Perspectives in Geometric Combinatorics, Cambridge University Press, 255-291. |
| [16] | Chen, H. and Ye, Y. (2023) On the Number of Perfect Matchings in the Line Graph of a Traceable Graph. Discrete Applied Mathematics, 327, 110-118. https://doi.org/10.1016/j.dam.2022.12.011 |
| [17] | 冯星. 图的Pfaffian性与完美匹配计数问题[D]: [博士学位论文]. 厦门: 厦门大学, 2018. |
| [18] | Yan, W., Yeh, Y. and Zhang, F. (2008) Dimer Problem on the Cylinder and Torus. Physica A: Statistical Mechanics and its Applications, 387, 6069-6078. https://doi.org/10.1016/j.physa.2008.06.042 |
| [19] | 张福基, 刘育亭, 郭晓峰. 树状多六边形的完美匹配计数[J]. 新疆大学学报(自然科学版), 1985(3): 7-11. |
| [20] | Zhang, H. and Zhang, F. (1997) Perfect Matchings of Polyomino Graphs. Graphs and Combinatorics, 13, 295-304. https://doi.org/10.1007/bf03353008 |
| [21] | 林泓, 林晓霞. 若干四角系统完美匹配数的计算[J]. 福州大学学报(自然科学版), 2005, 33(6): 704-735. |
| [22] | 唐保祥, 任韩. 3类3-正则图中的完美匹配数[J]. 华中师范大学学报(自然科学版), 2014, 48(5): 637-649. |
| [23] | 马京成, 马登举, 朱珺. 3-正则Halin图的完美匹配数[J]. 昆明理工大学学报(自然科学版), 2015, 40(5): 132-136. |
| [24] | 叶银珠, 陈海燕. 繁星树线图的完美匹配数[J]. 厦门大学学报(自然科学版), 2023, 62(3): 450-453. |
| [25] | Dong, F., Yan, W. and Zhang, F. (2013) On the Number of Perfect Matchings of Line Graphs. Discrete Applied Mathematics, 161, 794-801. https://doi.org/10.1016/j.dam.2012.10.032 |
| [26] | 杨思齐, 边红, 于海征, 魏丽娜. 几类特殊图的完美匹配的计数[J]. 理论数学, 2022, 12(1): 27-35. |
| [27] | 唐保祥, 任韩. 3类特殊图完美匹配数的计算公式[J]. 中山大学学报(自然科学版), 2017, 56(3): 36-40. |
| [28] | Yang, R. and Yuan, M. (2023) The Number of Perfect Matchings in (3, 6)-Fullerene. Wuhan University Journal of Natural Sciences, 28, 192-200. https://doi.org/10.1051/wujns/2023283192 |
| [29] | 刘剑洪, 吴双泉, 何传新, 卓海涛, 朱才镇, 李翠华, 张黔玲. 碳纳米管和碳微米管的结构、性质及其应用[J]. 深圳大学学报(理工版), 2013, 30(1): 1-11. |
| [30] | Iijima, S. (2002) Carbon Nanotubes: Past, Present, and Future. Physica B: Condensed Matter, 323, 1-5. https://doi.org/10.1016/s0921-4526(02)00869-4 |
| [31] | Došlić, T. (1998) On Lower Bounds of Number of Perfect Matchings in Fullerene Graphs. Journal of Mathematical Chemistry, 24, 359-364. https://doi.org/10.1023/a:1019195324778 |
| [32] | Zhang, H. and Zhang, F. (2001) New Lower Bound on the Number of Perfect Matchings in Fullerene Graphs. Journal of Mathematical Chemistry, 30, 343-347. https://doi.org/10.1023/a:1015131912706 |
| [33] | Kardoš, F., Král, D., Miškuf, J. and Sereni, J. (2008) Fullerene Graphs Have Exponentially Many Perfect Matchings. Journal of Mathematical Chemistry, 46, 443-447. https://doi.org/10.1007/s10910-008-9471-7 |
| [34] | 鞠阳. 富勒烯图的不变量及其统计分析[D]: [博士学位论文]. 北京: 清华大学, 2012. |
| [35] | 王芳. 富勒烯图完美匹配数和共振型个数的比较[D]: [硕士学位论文]. 兰州: 兰州大学, 2016. |
| [36] | 钱进. 富勒烯的Kekulé数下界及稳定性研究[D]: [博士学位论文]. 北京: 清华大学, 2020. |
| [37] | Lovász, L. and Plummer, M. (1986) Matching Theory. North-Holland Press. |
| [38] | Esperet, L., Kardoš, F., King, A.D., Král, D. and Norine, S. (2011) Exponentially Many Perfect Matchings in Cubic Graphs. Advances in Mathematics, 227, 1646-1664. https://doi.org/10.1016/j.aim.2011.03.015 |
