The number of perfect matchings in two types of particular graphs
TANG Baoxiang1, REN Han2
1. School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, Gansu Province, China;
2. Department of Mathematics, East China Normal University, Shanghai 200062, China
Abstract:Perfect matching counting problems for graphs have been proven to be NP-hard, so it is very difficult to get the number of perfectly matched general graph. The counting formula of the perfect matching for graphs 4-1-nC10and 2-nT2 was made by applying partition, summation and re-recursion. The number of all perfect matchings of many graphs can be calculated by the method presented in this paper. The given method is also able to implement the possibility to obtain the number of all perfect matchings with perfect matching graphs.
唐保祥, 任韩. 2类特殊图中的完美匹配数[J]. 浙江大学学报(理学版), 2017, 44(3): 266-269.
TANG Baoxiang, REN Han. The number of perfect matchings in two types of particular graphs. Journal of ZheJIang University(Science Edition), 2017, 44(3): 266-269.
[1] LOVÁSZ L, PLUMMER M. Matching Theory [M]. New York: North-Holland Press,1986.
[2] KRÁL D, SERENI J S, STIEBITZ M. A new lower bound on the number of perfect matchings in cubic graphs [J]. Discrete Math,2009,23:1465-1483.
[3] KARDOS F, KRÁL D, MISKUF J, et al. Fullerene graphs have exponentially many perfect matchings[J].Journal of Mathematical Chemistry,2009,46:443-447.
[4] 唐保祥,任韩.几类图完美匹配的数目[J].南京师大学报:自然科学版,2010,33(3):1-6. TANG B X, REN H. The number of perfect matching for three specific types of graphs [J].Journal of Nanjing Normal University: Natural Science Edition,2010,33(3):1-6.
[5] 唐保祥,李刚,任韩.3类图完美匹配的数目[J].浙江大学学报:理学版,2011,38(4):387-390. TANG B X, LI G, REN H. The number of perfect matching for three specific types of graphs[J].Journal of Zhejiang University: Science Edition,2011,38(4):387-390.
[6] 唐保祥,任韩.3类特殊图完美对集数的计算[J].南开大学学报:自然科学版,2014,47(5):11-16. TANG B X, REN H. The enumeration of perfect matchings in three types of special graphs[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis,2014,47(5):11-16.
[7] 唐保祥,任韩.4类图完美匹配数目的递推求法[J].数学杂志,2015,353(2):626-634. 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.
[8] 唐保祥,任韩.4类图完美匹配的计数[J].武汉大学学报:理学版,2012,58(5):441-446. TANG B X, REN H. The number of perfect matchings in four types of graphs[J]. Journal of Wuhan University: Natural Science Edition,2011,58(5):441-446.
[9] 唐保祥,任韩.5类图完美匹配的计数[J].中山大学学报:自然科学版,2012,51(4):31-37. TANG B X, REN H. The number of perfect matchings in five types of graphs[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni,2012,51(4):31-37.