Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2019, Vol. 46 Issue (6): 670-675    DOI: 10.3785/j.issn.1008-9497.2019.06.007
数学与计算机科学     
图的1-因子数目的递推求法
唐保祥1, 任韩2
1.天水师范学院 数学与统计学院, 甘肃 天水 741001
2.华东师范大学 数学系, 上海 200062
Recursive method for the number of 1-factors in 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
 全文: PDF(681 KB)   HTML  
摘要： 首先对图的1-因子进行分类，求出每一类1-因子数目的递推关系式；然后对各类1-因子数目的递推式进行求和，得到一组有相互联系的递推关系式；利用递推式之间的相互关系，消去不需要的，得到图的1-因子数目的递推关系式；最后求出此递推式的公式解。
关键词： 1-因子;  线性递推式;  特征方程;  通解    
Abstract: First, we classify the 1-factor of the graph, find the recurrence relation of the number of 1-factors of each class, and then， sum the recursive numbers of 1-factor numbers of each class to obtain a set of interconnected recursive relations. Then, with the relationship between these recursive formulas, we eliminate the unnecessary recurrence relations, obtain the recurrence relation of the 1-factor number of this graph, finally derive the formula solution of this recurrence formula.
Key words: 1-factor    linear recurrence relation    characteristic equation    general solution
收稿日期: 2018-08-17 出版日期: 2019-11-25
CLC:  O157.5  
基金资助: 国家自然科学基金资助项目(11171114).
作者简介: 唐保祥(1961—)，ORCID:http://orcid.org/0000-0002-1631-1482，男，教授，主要从事图论和组合数学研究，E-mail :tbx0618@sina.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
唐保祥
任韩

引用本文:

唐保祥, 任韩. 图的1-因子数目的递推求法[J]. 浙江大学学报（理学版）, 2019, 46(6): 670-675.

TANG Baoxiang, REN Han. Recursive method for the number of 1-factors in graphs. Journal of ZheJIang University(Science Edition), 2019, 46(6): 670-675.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2019.06.007    或    https://www.zjujournals.com/sci/CN/Y2019/V46/I6/670

1VALIANT L G. The complexity of computing the permanent[J]. Theoretical Compute Science, 1979, 8(2):189-201. DOI:10.1016/0304-3975(79)90044-6
2林泓,林晓霞.若干四角系统完美匹配数的计算[J]. 福州大学学报（自然科学版）, 2005, 33(6):704-710,735.DOI:10.3969/j.issn.1000-2243.2005.06.003LIN 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,735 .DOI:10.3969/j.issn.1000-2243.2005.06.003
3唐保祥,李刚,任韩. 3类图完美匹配的数目[J]. 浙江大学学报（理学版）, 2011, 38(4):16-19.DOI:10.3785/j.issn.1008-9497.2011.04.005TANG 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):16-19 .DOI:10.3785/j.issn.1008-9497.2011.04.005
4唐保祥,任韩. 4 类图完美匹配数目的递推求法[J]. 数学杂志, 2015, 35(3):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, 35(3):626-634 .
5唐保祥,任韩. 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 Universitatis Nankaiensis, 2014, 47(5):11-16.
6唐保祥,任韩. 4类图完美匹配的计数[J]. 武汉大学学报（理学版）, 2012, 58(5):441-446.TANG B X, REN H. The number of perfect matchings for four types of graphs[J]. Journal of Wuhan University （Natural Science Edition）, 2012, 58(5):441-446.
7唐保祥,任韩. 两类图完美匹配的计数公式[J]. 吉林大学学报（理学版）, 2016,54(4): 790-792 .DOI:10.13413/j.cnki.jdxblxb.2016.04.20TANG B X, REN H. Counting formulas of perfect matchings of two types of graphs[J]. Journal of Jilin University（ Science Edition）, 2016, 54(4): 790-792.
8唐保祥,任韩. 2类图完美匹配数目的解析式[J]. 中山大学学报（自然科学版）, 2016, 55(4):15-17.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.
9唐保祥,任韩. 2类特殊图中的完美匹配数[J]. 浙江大学学报（理学版）, 2017, 44(3):266-269.DOI:10.3785/j.issn.1008-9497.2017.03.003TANG 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.DOI:10.3785/j.issn.1008-9497.2017.03.003
10唐保祥,任韩. 2类偶图完美匹配的数目[J]. 西南大学学报（自然科学版）, 2012, 34(10):91-95.TANG B X, REN H. The number of perfect matching for two types of bipartite graphs[J]. Journal of Southwest University（Natural Science Edition）, 2012, 34(10):91-95.
11唐保祥,任韩.几类图完美匹配的数目[J]. 南京师范大学学报（自然科学版）,2010,33(3):1-6.DOI:10.3969/j.issn.1001-4616.2010.03.001TANG B X, REN H. The number of perfect matching in several types of graphs[J]. Journal of Nanjing Normal University (Natural Science Edition), 2010, 33(3):1-6.
[1] 周后卿. 几类整循环图的秩的界[J]. 浙江大学学报（理学版）, 2020, 47(3): 301-305.
[2] 包丽娅, 陈祥恩, 王治文. 完全二部图K 10, n (215 ≤ n ≤ 466)的点可区别E-全染色[J]. 浙江大学学报（理学版）, 2020, 47(1): 60-66.
[3] 贾会才. k路覆盖图的新充分条件[J]. 浙江大学学报（理学版）, 2019, 46(6): 666-669.
[4] 柳顺义, 覃忠美. 图的Aα特征多项式系数的一个注记[J]. 浙江大学学报（理学版）, 2019, 46(4): 399-404.
[5] 寇艳芳, 陈祥恩, 王治文. K1,5,p和K1,6,p的点可区别的IE-全染色及一般全染色[J]. 浙江大学学报（理学版）, 2018, 45(5): 533-539.
[6] 郭利涛. 超连通图的充分条件[J]. 浙江大学学报（理学版）, 2018, 45(4): 391-393.
[7] 周后卿. 卡氏积图的Laplacian谱半径的上界[J]. 浙江大学学报（理学版）, 2018, 45(1): 10-13,17.
[8] 王国兴. Cartesian积与邻点可区别着色之间的关系[J]. 浙江大学学报（理学版）, 2017, 44(5): 520-525.
[9] 温艳清, 刘宝亮, 安明强. 若干运算图的倍乘赋权Harary指标[J]. 浙江大学学报（理学版）, 2017, 44(3): 253-260,280.
[10] 唐保祥, 任韩. 2类特殊图中的完美匹配数[J]. 浙江大学学报（理学版）, 2017, 44(3): 266-269.
[11] 吕大梅, 林文松. 关于边-多重路替换图的1,2,3-猜想和1,2-猜想[J]. 浙江大学学报（理学版）, 2016, 43(6): 668-671.
[12] 杜娟, 吕大梅, 张科. Cartesian积的局部边-路替换图的L(2,1)-标号[J]. 浙江大学学报（理学版）, 2016, 43(6): 679-681.
[13] 刘剑萍, 吴先章, 陈锦松. 树状六角系统的增强型萨格勒布指数[J]. 浙江大学学报（理学版）, 2016, 43(6): 664-667.
[14] 周后卿. 循环图的预解Estrada指标[J]. 浙江大学学报（理学版）, 2016, 43(5): 517-520.
[15] 曲慧, 刘伟俊. 几个图运算下的图的惯性指数的界[J]. 浙江大学学报（理学版）, 2016, 43(2): 134-137.