A Recursive Method for Perfect Matching Number Classified with Saturation of a Certain Vertex

TANG Baoxiang; REN Han

doi:10.6054/j.jscnun.2019092

Journal of South China Normal University (Natural Science Edition) > 2019 > 51(5): 110-114. > DOI: 10.6054/j.jscnun.2019092

TANG Baoxiang, REN Han. A Recursive Method for Perfect Matching Number Classified with Saturation of a Certain Vertex[J]. Journal of South China Normal University (Natural Science Edition), 2019, 51(5): 110-114. DOI: 10.6054/j.jscnun.2019092

Citation:

PDF (525 KB)

A Recursive Method for Perfect Matching Number Classified with Saturation of a Certain Vertex

TANG Baoxiang^1, ,,
REN Han²

1.
School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, China
2.
Department of Mathematics, East China Normal University, Shanghai 200062, China

More Information

Received Date: October 30, 2018
Available Online: March 08, 2021

Graphical Abstract

Abstract

Abstract

Two new graphs 2-2nK₅ and 2-nZ₅ are constructed. Using the nested recursive method, two recursive relations of the perfect matching numbers of graphs 2-2nK₅ and 2-nZ₅ are obtained, and then the two recursive general solutions are solved. Thus, the formula for calculating the perfect matching number of these two types of graphs is obtained.
- perfect matching,
- classification,
- recursive relationship,
- general solution

FullText(HTML)

References (17)

References

[1]	LOVÁSZ L, PLUMMER M. Matching theory[M]. New York:North-Holland Press, 1986.
[2]	ZHANG H P. The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J]. Discrete Mathematics, 1996, 158:257-272. doi: 10.1016/0012-365X(95)00048-2
[3]	ZHANG H P, ZHANG F J. Perfect matchings of polyomino graphs[J]. Graphs and Combinatorics, 1997, 13:259-304. doi: 10.1007-s00373-004-0593-9/
[4]	LI S L, YAN W G. The matching energy of graphs with given parameters[J]. Discrete Applied Mathematics, 2014, 162:415-420. doi: 10.1016/j.dam.2013.09.014
[5]	DONG F M, YAN W G, ZHANG F J. On the number of perfect matchings of line graphs[J]. Discrete Applied Mathematics, 2013, 161:794-801. doi: 10.1016/j.dam.2012.10.032
[6]	YAN W G, ZHANG F J. A quadratic identity for the number of perfect matchings of plane graphs[J]. Theoretical Computer Science, 2008, 409:405-410. doi: 10.1016/j.tcs.2008.08.032
[7]	CHANG A, TIAN F, YU A M. On the index of bicyclic graphs with perfect matchings[J]. Discrete Mathematics, 2004, 283:51-59. doi: 10.1016/j.disc.2004.02.005
[8]	CHANG A, SHIU W C. On the kth eigenvalues of trees with perfect matchings[J]. Discrete Mathematics and Theoretical Computer Science, 2007, 9(1):321-332
[9]	林泓, 林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报(自然科学版), 2005, 33(6):704-710. doi: 10.3969/j.issn.1000-2243.2005.06.003 LIN H, LIN X X. Enumeration of perfect matchings in some type polyminoes[J]. Journal of Fuzhou University(Natural Sciences Edition), 2005, 33(6):704-710. doi: 10.3969/j.issn.1000-2243.2005.06.003
[10]	唐保祥, 李刚, 任韩. 3类图完美匹配的数目[J].浙江大学学报(理学版), 2011, 38(4):16-19. http://d.old.wanfangdata.com.cn/Periodical/zjdxxb201104005 TANG B X, LI G, REN H. The number of perfect mat-ching for three specific types of graphs[J]. Journal of Zhejiang University(Science Edition), 2011, 38(4):16-19. http://d.old.wanfangdata.com.cn/Periodical/zjdxxb201104005
[11]	唐保祥, 任韩. 4类图完美匹配数目的递推求法[J].数学杂志, 2015, 353(2):626-634. http://d.old.wanfangdata.com.cn/Periodical/hnsfdx201401004 TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs[J]. Journal of Mathematics, 2015, 353(2):626-634. http://d.old.wanfangdata.com.cn/Periodical/hnsfdx201401004
[12]	唐保祥, 任韩. 3类特殊图完美对集数的计算[J].南开大学学报(自然科学版), 2014, 47(5):11-16. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=nkdx201405002 TANG B X, REN H. The enumeration of perfect mat-chings in three types of special graphs[J]. Journal of Nankai University(Science Edition), 2014, 47(5):11-16. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=nkdx201405002
[13]	唐保祥, 任韩. 4类图完美匹配的计数[J].武汉大学学报(理学版), 2012, 58(5):441-446. http://d.old.wanfangdata.com.cn/Periodical/whdxxb-zr201205015 TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University(Natural Science Edition), 2012, 58(5):441-446. http://d.old.wanfangdata.com.cn/Periodical/whdxxb-zr201205015
[14]	唐保祥, 任韩.两类图完美匹配的计数公式[J].吉林大学学报(理学版), 2016, 54(4):790-792. http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201604021 TANG B X, REN H. Counting formulas of the number of perfect matchings of the two types of graphs[J]. Journal of Jilin University(Science Edition), 2016, 54(4):790-792. http://d.old.wanfangdata.com.cn/Periodical/jldxzrkxxb201604021
[15]	唐保祥, 任韩. 2类图完美匹配数目的解析式[J].中山大学学报(自然科学版), 2016, 55(4):15-17. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zsdxxb201604003 TANG B X, REN H. The analytic formula of the number of perfect matchings of two types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(4):15-17. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zsdxxb201604003
[16]	唐保祥, 任韩. 2类特殊图中的完美匹配数[J].浙江大学学报(理学版), 2017, 44(3):266-269. http://d.old.wanfangdata.com.cn/Periodical/zjdxxb201703003 TANG B X, REN H. The number of perfect matchings in two types of particular graphs[J]. Journal of Zhejiang University(Science Edition), 2017, 44(3):266-269. http://d.old.wanfangdata.com.cn/Periodical/zjdxxb201703003
[17]	唐保祥, 任韩. 4类图完美匹配数目的递推求法[J].数学杂志, 2015, 353(2):626-634. http://d.old.wanfangdata.com.cn/Periodical/hnsfdx201401004 TANG B X, REN H. Recursive method for finding the number of perfect matchings of the four types of graphs[J]. Journal of Mathematics, 2015, 353(2):626-634. http://d.old.wanfangdata.com.cn/Periodical/hnsfdx201401004

Cited By

Cited by

Periodical cited type(1)

刘威，徐徐，万雅琼，卢晓强，刘立，李佳琦，王雪霁，王翊肖，刘燕. 以海口市为例分析热带地区城市化过程中不同生境鸟类多样性特征. 环境科学研究. 2025(01): 29-38 .

Other cited types(0)

Get Citation

PDF

XML

Article views (1868) PDF downloads (32) Cited by(1)

Turn off MathJax

Article Contents

Abstract

References

A Recursive Method for Perfect Matching Number Classified with Saturation of a Certain Vertex

Abstract

References

Cited by

Periodical cited type(1)

Other cited types(0)

Catalog

Export File

Citation

Format

Content