唐保祥, 任 韓

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

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

1 基本概念

定義1若圖G有一個(gè)1-正則生成子圖D,則稱(chēng)這個(gè)生成子圖D為圖G的1-因子.

定義2設(shè)圖G是一個(gè)有1-因子的圖,若圖G的2個(gè)1-因子D1和D2中有1條邊不同,則稱(chēng)D1和D2是G的2個(gè)不同的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所示,對(duì)于圖mTn的任意一個(gè)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,于是頂點(diǎn)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的完美對(duì)集數(shù)τ(m,n)=(n!)m.

圖6 圖