JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (11): 127-134, 146.doi: 10.6040/j.issn.1671-9352.0.2022.050

Previous Articles     Next Articles

Recursive solving of di-forcing polynomials for ladder graphs

Hui HAN1,2(),Yutong LIU2,Haiyuan YAO1,*()   

  1. 1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, Gansu, China
    2. Hebei Foreign Studies University, Shijiazhuang 050011, Hebei, China
  • Received:2022-01-05 Online:2023-11-20 Published:2023-11-07
  • Contact: Haiyuan YAO E-mail:1063064719@qq.com;hyyao@nwnu.edu.cn

RichHTML

0

PDF (PC)

87

Abstract:

The ladder graph Ln is the Cartesian product of the paths Pn and P2. The di-forcing polynomial of Ln is a binary enumerative polynomial of forcing and anti-forcing numbers of all perfect matchings of the graph. We derive a recurrence formula of the di-forcing polynomial for ladder graphsby classification discussion and enumerating of the matching edge associated with a given vertex. And based on this, wecompute the generating function of the di-forcing polynomials for all ladder graphs anddi-forced polynomials for some ladder graphs with low order.

Key words: ladder graph, perfect matching, di-forcing polynomial, forcing polynomial, anti-forcing polynomial, recursion relationship, generating function

CLC Number: 

  • O157

Fig.1

Ladder graph Ln"

Fig.2

Corresponding decomposition of Ln"

Fig.3

Indecomposable fragment"

Fig.4

3 matching scenarios of Ln about the associated edges of vertex a2"

1 RANDIC M , KLEIN D J . Kekule valence structures revisited. Innate degrees of freedom of π-electron couplings[M]. New York: Wiley, 1985: 274- 282.
2 HARARY F , KLEIN D J , ŽIVKOVIČ T P . Graphical properties of polyhexes: perfect matching vector and forcing[J]. Journal of Mathematical Chemistry, 1991, 6 (1): 295- 306.
doi: 10.1007/BF01192587
3 VUKIĚEVI Ć D , TRINAJSTI Ć N . On the anti-forcing number of benzenoids[J]. Journal of Mathematical Chemistry, 2007, 42 (3): 575- 583.
doi: 10.1007/s10910-006-9133-6
4 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.
5 LEI Hongchuan , YEH Y N , ZHANG Heping . Anti-forcing numbers of perfect matchings of graphs[J]. Discrete Applied Mathematics, 2016, 202 (C): 95- 105.
6 ZHANG Heping , ZHAO Shuang , LIN Ruizhi . The forcing polynomial of catacondensed hexagonal systems[J]. MATCH Commun Math Comput Chem, 2015, 73, 473- 490.
7 HWANG H K, LEI H C, YEH Y N, et al. Distribution of forcing and anti-forcing numbers of random perfect matchings on hexagonal chains and crowns[EB/OL]. [2021-11-05]. https://algo.stat.sinica.edu.tw/hk/wp-content/files/2015/01/distribution_of_the_forcing_and_anti-forcing_numbers.pdf
8 姚海元, 王杰彬, 王旭. 循环梯状图的完美匹配的反强迫谱与卢卡斯数列[J]. 西北师范大学学报(自然科学版), 2018, 54 (2): 21- 25.
YAO Haiyuan , WANG Jiebin , WANG Xu . The anti-forcing spectra of perfect matchings of cyclic ladder g raphs and Lucas sequences[J]. Journal of Northwest Normal University (Natural Science), 2018, 54 (2): 21- 25.
9 韩振云, 姚海元. 删边梯子图和"L"型梯子图的反强迫数[J]. 应用数学进展, 2019, (8): 1352- 1361.
HAN Zhenyun , YAO Haiyuan . The anti-forcing numbers of the edge deleted ladder graphs and the "L" type ladder graphs[J]. Advances in Applied Mathematics, 2019, (8): 1352- 1361.
10 韩振云, 王杰彬. 梯子图完美匹配的反强迫谱与斐波那契数列[J]. 兰州工业学院学报, 2020, 27 (1): 85- 90.
HAN Zhenyun , WANG Jiebin . Anti-forcing spectrum and fibonacci series for perfect ladder graphs matching[J]. Journal of Lanzhou Institute of Technology, 2020, 27 (1): 85- 90.
11 ZHAO S , ZHANG H P . Anti-forcing polynomials for benzenoid systems with forcing edges[J]. Discrete Applied Mathematics, 2018, 250, 342- 356.
12 ZHAO S , ZHANG H P . Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids[J]. Journal of Mathematical Chemistry, 2019, 57 (1): 202- 225.
13 LIU Y T , MA C C , YAO H Y , et al. Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2021, 87 (3): 561- 575.
14 RIDDLE M E . The minimum forcing number for the torus and hypercube[J]. Discrete Mathematics, 2002, 245 (1): 283- 292.
15 PACHTER L , KIM P . Forcing matchings on square grids[J]. Discrete Mathematics, 1998, 190 (1/2/3): 287- 294.
16 王倩倩, 韩振云, 姚海元. "X"型梯状图和"T"型梯状图的反强迫多项式[J]. 应用数学进展, 2020, (9): 1404- 1416.
WANG Qianqian , HAN Zhenyun , YAO Haiyuan . The anti-forcing polynomials of "X" type and "T" type ladderlike graphs[J]. Advances in Applied Mathematics, 2020, (9): 1404- 1416.
[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] . On the spectrum of matching forcing numbers for bipartite graphs [J]. J4, 2009, 44(12): 30-35.
[7] LI Zhi-rong and LI Ying-hui . A new kind of summation formulae involving the Genocchi number and Riemann Zeta function [J]. J4, 2007, 42(4): 79-83 .
[8] LI Zhi-rong . Computational formulae of generalized m-th-order Bell numbers and generalized m-order orderd Bell numbers [J]. J4, 2007, 42(2): 59-63 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHANG Zhuan, YUAN Jian-Li, CHEN Jian-Jin. An algorithm based on the boundary-added decomposition matrix for ternary ECL circuits[J]. J4, 2010, 45(3): 45 -49 .
[2] ZHANG Fengxia1,　LI Ying1,2,　GUO Wenbin1, ZHAO Jianli1. Extremal ranks for block Hermitian and skew-Hermitian matrices[J]. J4, 2010, 45(4): 106 -110 .
[3] JIN Yong-gang, WANG Fan, HU Xiao-peng. Contour matching method based on curvature scale space[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(12): 43 -48 .
[4] LIU Ru-jun,CAO Yu-xia,ZHOU Ping . Anti-control for discrete chaos systems by small feedback[J]. J4, 2007, 42(7): 30 -32 .
[5] WU Song-li1,2, CHEN Gui-you3*. Outer-disturbances and attributes conjunctive shrink#br# law mining and separating[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 1 -5 .
[6] XI Ya-hui, ZHANG Ming, YUAN Fang, WANG Yu. A survey of product reviews mining[J]. J4, 2011, 46(5): 16 -23 .
[7] DU Li-na, XU Jiu-cheng, LIU Yang-yang, SUN Lin. Research on the evaluation of venture investment based on the risk minimization of three-way decision[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 66 -72 .
[8] . Reversible data hiding in encrypted image based on an integer transform[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(9): 76 -83 .
[9] Ma Jia-sai,ZHANG Yong-jun . An optimized method for minimal cubing approach[J]. J4, 2006, 41(3): 104 -107 .
[10] HU Chun-mei，LIU Xiao-ji*. A splitting for the W-weighted Drazin inverse of a linear operator on Banach space[J]. J4, 2010, 45(10): 24 -26 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd