您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2026, Vol. 61 ›› Issue (2): 115-126.doi: 10.6040/j.issn.1671-9352.0.2024.147

• • 上一篇    

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

徐正权,邓凯*   

  1. 北方民族大学数学与信息科学学院, 宁夏 银川 750021
  • 发布日期:2026-02-13
  • 通讯作者: 邓凯(1980— ),男,副教授,硕士生导师,研究方向为图论及其应用. E-mail:dengkai04@126.com
  • 作者简介:徐正权(1999— ),男,硕士研究生,研究方向为图论及其应用. E-mail:xuzhengquan2024@163.com*通信作者:邓凯(1980— ),男,副教授,硕士生导师,研究方向为图论及其应用. E-mail:dengkai04@126.com
  • 基金资助:
    国家自然科学基金(12161002);宁夏高等教育一流学科建设基金项目(NXYLXK2017B09)

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

XU Zhengquan, DENG Kai*   

  1. School of Mathematics and Information Sciences, North Minzu University, Yinchuan 750021, Ningxia, China
  • Published:2026-02-13

PDF (PC)

25

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

关键词: 完美匹配, 强迫数, 反强数, 六角系统

Abstract: Let M be a perfect matching of a graph G, 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

中图分类号: 

  • O157
[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] RANDIC 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, RANDIC 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. 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.
[13] VUKICEVIC D, TRINAJSTIC N. On the anti-forcing number of benzenoids[J]. Journal of Mathematical Chemistry, 2007, 42:575-583.
[14] 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.
[15] DENG Kai, ZHANG Heping. Anti-forcing spectra of perfect matchings of graphs[J]. Journal of Combinatorial Optimization, 2017, 33:660-680.
[16] 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.
[17] 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.
[18] ZHAO Shuang, ZHANG Heping. Anti-forcing polynomials for benzenoid systems with forcing edges[J]. Discrete Applied Mathematics, 2018, 250:342-356.
[19] CYVIN S J, GUTMAN I. Kekulé structures in benzenoid hydrocarbons[M]. Berlin: Springer, 1988:17.
[20] DIAS J R. Isomer enumeration of practical benzenoids[J]. Journal of Mathematical Chemistry, 2008, 44:711-724.
[21] BRUNVOLL J, CYVIN S J, CYVIN B N. Enumeration and classification of benzenoid hydrocarbons[J]. Journal of Computational Chemistry, 1987, 8(3):189-197.
[22] 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.
[23] PACHTER L, KIM P. Forcing matchings on square grids[J]. Discrete Mathematics, 1998, 190:290.
[24] ZHANG Heping, ZHANG Fuji. Plane elementary bipartite graphs[J]. Discrete Applied Mathematics, 2000, 105(1/2/3):294.
[25] 赵爽. 关于一些图类的强迫与反强迫多项式的研究[D]. 兰州:兰州大学,2018. ZHAO Shuang. Research on forcing and anti-forcing polynomials for some classes of graphs[D]. Lanzhou: Lanzhou University, 2018. 附录: 图17个苯环生成的cata-型六角系统 Fig.1Cata-condensed hexagonal systems generated by seven benzene rings 图1(续)7个苯环生成的cata-型六角系统 Fig.1(continued)Cata-condensed hexagonal systems generated by seven benzene rings 图27个苯环生成的peri-型六角系统 Fig.2Peri-condensed hexagonal systems generated by seven benzene rings
[1] 韩慧,刘雨童,姚海元. 梯子图双强迫多项式的递推求解[J]. 《山东大学学报(理学版)》, 2023, 58(11): 127-134, 146.
[2] 孙晓玲,高玉斌,杜建伟,任建斌. 准树图的零阶广义Randic指数[J]. 《山东大学学报(理学版)》, 2022, 57(12): 96-102.
[3] 杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.
[4] 来金花,刘蒙蒙. 含有完美匹配树的最小Steiner k-Wiener指标[J]. 《山东大学学报(理学版)》, 2022, 57(10): 66-71.
[5] 王霞,边红,于海征. 整可逆图的克罗内克积的逆[J]. 《山东大学学报(理学版)》, 2021, 56(11): 87-92.
[6] 张友,黄丽娜,李沐春. 一类六角系统的点可区别边染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 41-47.
[7] 王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[8] 王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.
[9] 周 薇,刘西奎,王文丽 . 六角系统关联色数与邻点可区别关联色数[J]. J4, 2008, 43(9): 57-62 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发