唐保祥, 任 韓

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,甘肅 天水 741001；2.華東師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院, 上海 200062)

研究圖的1-因子的計數(shù)問題，具有重要的理論價值和現(xiàn)實意義[1-3]，該問題已經(jīng)被證實是NP-困難問題.分類嵌套遞推方法，是求解許多類圖1-因子數(shù)的一種非常有效的方法[4-7].筆者擬構(gòu)造2類新圖mTn和mKn,n,并用分類嵌套遞推方法推導(dǎo)mTn和mKn,n不同1-因子的計數(shù)公式.

1 基本概念

定義1若圖G有一個1-正則生成子圖D,則稱這個生成子圖D為圖G的1-因子.

定義2設(shè)圖G是一個有1-因子的圖,若圖G的2個1-因子D1和D2中有1條邊不同,則稱D1和D2是G的2個不同的1-因子.

圖1 圖mTnFig. 1 Graph of mTn

圖2 圖mKn,nFig. 2 Graph of mKn,n

2 主要結(jié)果及其證明

定理1設(shè)圖mTn的1-因子數(shù)為σ(m,n),則有

圖3 圖

圖4 圖G1Fig. 4 Graph of G1

圖5 圖G2Fig. 5 Graph of G2

如圖1所示,對于圖mTn的任意一個1-因子D,若邊u1jv1,j+1∈D(j≤n-1),則必須有u1,j+1v1j∈D.否則由u1jv1,j+1∈D可得u1,j+1v1,j+2,u1,j+2v1,j+3,…,u1,n-1v1n∈D,于是頂點u1n就不被1-因子D飽和,這與D是圖mTn的1-因子矛盾.由此可知，圖mTn的邊vijui+1,j?D(i=1,2,…m;j=1,2,…,n).

所以圖mTn的1-因子數(shù)

證畢.

定理2圖mKn,n的完美對集數(shù)τ(m,n)=(n!)m.

圖6 圖