7个苯环生成的六角系统的自由度与反自由度

Degree of freedom and anti-degree of freedom of a hexagonal system generated by seven benzene rings

摘要

设M是图G的一个完美匹配,S⊆M,S′⊆E(G)\M。若S不被G中除M以外的其它完美匹配所包含,则称S是M的一个强迫集。包含边数最少的强迫集的势称为M的强迫数,图G中所有完美匹配强迫数的和称作图G的自由度。若M是G删去S′中边得到的图GS′中唯一的完美匹配,则称S′是M的一个反强迫集。包含边数最少的反强迫集的势称为M的反强迫数,图G中所有完美匹配反强迫数的和称作图G的反自由度。通过计算强迫和反强迫多项式,得到了由7个苯环生成的所有有完美匹配的六角系统的自由度和反自由度。

Abstract

Let M be a perfect matching of a graph S⊆M, S′⊆E(G)\M. If S is not included in any perfect matching of G except for M, then S is called a forcing set of M. The cardinality of a forcing set of M which has the least number of edges is called the forcing number of M, the sum of forcing numbers of all perfect matchings of G is called the degree of freedom of G. If M is the unique perfect matching of the graph G\S′ obtained by deleting the edges of S′ from G, then S′ is called an anti-forcing set of M. The cardinality of an anti-forcing set of M which has the least number of edges is called the anti-forcing number of M, the sum of anti-forcing numbers of all perfect matchings of G is called the anti-degree of freedom of G. By calculating the forcing and anti-forcing polynomials, the degrees of freedom and anti-degrees of freedom of all hexagonal systems with a perfect matching generated by seven benzene rings are obtained.

关键词

完美匹配 / 强迫数 / 反强数 / 六角系统

Key words

perfect matching / forcing number / anti-forcing number / hexagonal system

参考文献

[1] LOVÁSZ L, PLUMMER M D. Matching theory[M]. Providence: AMS Chelsea Publishing, 2009.

[2] HARARY F, KLEIN D J, ZIVKOVIC T P. Graphical properties of polyhexes: perfect matching vector and forcing[J]. Journal of Mathematical Chemistry, 1991, 6(1): 295-306.

[3] RANDIĆ M, KLEIN D J. Kekulé valence structures revisited. Innate degrees of freedom of π—electron couplings[J]. Mathematical and Computational Concepts in Chemistry, 1985: 274-282.

[4] KLEIN D J, RANDIĆ M. Innate degree of freedom of a graph[J]. Journal of Computational Chemistry, 1987, 8(4): 516-521.

[5] ADAMS P, MAHDIAN M, MAHMOODIAN E S. On the forced matching numbers of bipartite graphs[J]. Discrete Mathematics, 2004, 281(1/2/3): 1-12.

[6] AFSHANI P, HATAMI H, MAHMOODIAN E S. On the spectrum of the forced matching number of graphs[J]. Australasian Journal of Combinatorics, 2004, 30: 147-160.

[7] KLEIN D J, ROSENFELD V. Forcing, freedom and uniqueness in graph theory and chemistry[J]. Croatica Chemica Acta, 2014, 81: 49-59.

[8] ZHANG Heping, ZHAO Shuang, LIN Ruizhi. The forcing polynomial of catacondensed hexagonal systems[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2015, 73: 473-490.

[9] ZHAO Shuang, ZHANG Heping. Forcing polynomials of benzenoid parallelogram and its related benzenoids[J]. Applied Mathematics and Computation, 2016, 284: 209-218.

[10] ZHAO Shuang, ZHANG Heping. Forcing and anti—forcing polynomials of perfect matchings for some rectangle grids[J]. Journal of Mathematical Chemistry, 2019, 57: 202-225.

[11] DENG Kai, LÜ Huazhong, WU Tingzeng. Forcing and anti—forcing polynomials of a type of polyomino graphs[J]. Computational and Applied Mathematics, 2023, 42(2): 91.

[12] 邓凯. 线性亚苯基系统的强迫和反强迫多项式[J]. 高校应用数学学报A辑, 2022, 37(4): 491-500.

[13] DENG Kai. Forcing and anti—forcing polynomials of linear phenylene systems[J]. Applied Mathematics A Journal of Chinese Universities(Ser.A), 2022, 37(4): 491-500.

[14] VUKIČEVIĆ D, TRINAJSTIĆ N. On the anti—forcing number of benzenoids[J]. Journal of Mathematical Chemistry, 2007, 42: 575-583.

[15] LEI H C, YEH Y N, ZHANG H P. Anti—forcing numbers of perfect matchings of graphs[J]. Discrete Applied Mathematics, 2016, 202: 95-105.

[16] DENG Kai, ZHANG Heping. Anti—forcing spectra of perfect matchings of graphs[J]. Journal of Combinatorial Optimization, 2017, 33: 660-680.

[17] HWANG H K, LEI H, YEH Y N, et al. Distribution of forcing and anti—forcing numbers of random perfect matchings on hexagonal chains and crowns[EB/OL]. [ 2015—01—21] (2023—12—07). https://algo.stat.sinica.edu.tw/hk/wp—content/files/2015/01/distribution_of_the_forcing_and_anti—forcing_numbers.pdf.

[18] DENG Kai, LIU Saihua, ZHOU Xiangqian. Forcing and anti—forcing polynomials of perfect matchings of a pyrene system[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2021, 85: 27-46.

[19] ZHAO Shuang, ZHANG Heping. Anti—forcing polynomials for benzenoid systems with forcing edges[J]. Discrete Applied Mathematics, 2018, 250: 342-356.

[20] CYVIN S J, GUTMAN I. Kekulé structures in benzenoid hydrocarbons[M]. Berlin: Springer, 1988: 17.

[21] DIAS J R. Isomer enumeration of practical benzenoids[J]. Journal of Mathematical Chemistry, 2008, 44: 711-724.

[22] BRUNVOLL J, CYVIN S J, CYVIN B N. Enumeration and classification of benzenoid hydrocarbons[J]. Journal of Computational Chemistry, 1987, 8(3): 189-197.

[23] KNOP J V, SZYMANSKI K, JERICEVIC Z, et al. On the total number of polyhexes[J]. MATCH Communications in Mathematical and in Computer Chemistry, 1984, 16: 119-134.

[24] PACHTER L, KIM P. Forcing matchings on square grids[J]. Discrete Mathematics, 1998, 190: 290.

[25] ZHANG Heping, ZHANG Fuji. Plane elementary bipartite graphs[J]. Discrete Applied Mathematics, 2000, 105(1/2/3): 294.

[26] 赵爽. 关于一些图类的强迫与反强迫多项式的研究[D]. 兰州: 兰州大学, 2018.

[27] ZHAO Shuang. Research on forcing and anti—forcing polynomials for some classes of graphs[D]. Lanzhou: Lanzhou University, 2018.

基金资助

国家自然科学基金(12161002)

宁夏高等教育一流学科建设基金项目(NXYLXK2017B09)