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

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (11): 127-134, 146.doi: 10.6040/j.issn.1671-9352.0.2022.050

•   • 上一篇    下一篇

梯子图双强迫多项式的递推求解

韩慧1,2(),刘雨童2,姚海元1,*()   

  1. 1. 西北师范大学数学与统计学院, 甘肃 兰州 730070
    2. 河北外国语学院, 河北 石家庄 050011
  • 收稿日期:2022-01-05 出版日期:2023-11-20 发布日期:2023-11-07
  • 通讯作者: 姚海元 E-mail:1063064719@qq.com;hyyao@nwnu.edu.cn
  • 作者简介:韩慧(1997—), 女, 硕士研究生, 研究方向为图的匹配理论及其应用. E-mail: 1063064719@qq.com
  • 基金资助:
    国家自然科学基金资助项目(12161081)

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

1

PDF (PC)

109

摘要：

梯子图Ln是路Pn和路P2的笛卡尔积。图的双强迫多项式是Ln的所有完美匹配的强迫数和反强迫数的二元计数多项式。通过对给定顶点关联边的匹配情况的分类讨论和计数, 得出了梯子图双强迫多项式的递推公式, 并由此计算出了其生成函数和一些低阶梯子图的双强迫多项式。

关键词: 梯子图, 完美匹配, 双强迫多项式, 强迫多项式, 反强迫多项式, 递推关系, 生成函数

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

中图分类号: 

  • O157

图1

梯子图Ln"

图2

Ln的对应分解"

图3

不可分解片段"

图4

Ln关于顶点a2关联边的3种匹配情况"

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] 孙晓玲,高玉斌,杜建伟,任建斌. 准树图的零阶广义Randic指数[J]. 《山东大学学报(理学版)》, 2022, 57(12): 96-102.
[2] 杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.
[3] 来金花,刘蒙蒙. 含有完美匹配树的最小Steiner k-Wiener指标[J]. 《山东大学学报(理学版)》, 2022, 57(10): 66-71.
[4] 王霞,边红,于海征. 整可逆图的克罗内克积的逆[J]. 《山东大学学报(理学版)》, 2021, 56(11): 87-92.
[5] 王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[6] 王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 章专 原建利 陈俭金. 基于可限加分解阵的三值ECL电路设计算法[J]. J4, 2010, 45(3): 45 -49 .
[2] 张凤霞1，李莹1,2，郭文彬1，赵建立1. 分块Hermite阵与斜Hermite阵的最大秩与最小秩[J]. J4, 2010, 45(4): 106 -110 .
[3] 靳永刚, 王凡, 胡小鹏. 基于曲率尺度空间的轮廓线匹配方法[J]. 山东大学学报（理学版）, 2014, 49(12): 43 -48 .
[4] 刘汝军,曹玉霞,周 平 . 利用小反馈实现离散非线性混沌系统的反控制[J]. J4, 2007, 42(7): 30 -32 .
[5] 吴松丽1,2,陈桂友3*. 外-扰动与属性合取收缩规律挖掘-分离[J]. 山东大学学报（理学版）, 2014, 49(06): 1 -5 .
[6] 郗亚辉,张明,袁方,王煜. 产品评论挖掘研究综述[J]. J4, 2011, 46(5): 16 -23 .
[7] 杜丽娜, 徐久成, 刘洋洋, 孙林. 基于三支决策风险最小化的风险投资评估应用研究[J]. 山东大学学报（理学版）, 2014, 49(08): 66 -72 .
[8] 罗欣荣, 项世军. 基于整数变换的加密图像可逆信息隐藏算法[J]. 山东大学学报（理学版）, 2016, 51(9): 76 -83 .
[9] 马嘉赛,张永军 . 最小方方法的一种优化方法[J]. J4, 2006, 41(3): 104 -107 .
[10] 胡春梅,刘晓冀*. Banach空间中算子加W-权Drazin逆的分裂法[J]. J4, 2010, 45(10): 24 -26 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发