JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2026, Vol. 61 ›› Issue (2): 115-126.doi: 10.6040/j.issn.1671-9352.0.2024.147

Previous Articles    

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)

36

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

CLC Number: 

  • 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] Hui HAN,Yutong LIU,Haiyuan YAO. Recursive solving of di-forcing polynomials for ladder graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 127-134, 146.
[2] SUN Xiao-ling, GAO Yu-bin, DU Jian-wei, REN Jian-bin. Zeroth-order general Randic index of quasi-tree graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 96-102.
[3] YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.
[4] LAI Jin-hua, LIU Meng-meng. On minimum Steiner k-Wiener index of trees with perfect matching [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 66-71.
[5] WANG Xia, BIAN Hong, YU Hai-zheng. Inverse of Kronecker product of integrally invertible graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 87-92.
[6] ZHANG You, HUANG Li-na, LI Mu-chun. Vertex distinguishing edge coloring of a hexagonal system [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 41-47.
[7] WANG Qian. The contractible edges of a spanning tree and a perfect matching in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 29-34.
[8] . On the spectrum of matching forcing numbers for bipartite graphs [J]. J4, 2009, 44(12): 30-35.
[9] ZHOU Wei,LIU Xi-kui,WANG Wen-li . Incidence chromatic number and adjacent vertex-distinguishing incidence
chromatic number of hexagonal systems [J]. J4, 2008, 43(9): 57-62 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd