3類3-正則圖中的1-因子數*

唐保祥，任 韓

(1.天水師范學院數學與統計學院，甘肅 天水 741001;2.華東師范大學數學系，上海 200062)

研究圖的1-因子計數問題[1-4]有重要的理論價值和現實意義,其研究成果已應用于多個領域.分類嵌套遞推方法,是求圖的1-因子數的一種非常有效的方法[4-6].筆者擬利用分類嵌套遞推方法給出3類特殊3-正則圖的1-因子數的計算公式.

1 預備知識

定義1若圖G的2個1-因子M1和M2中有1條邊不同,則稱M1和M2是G的2個不同的1-因子.

定義22條長為n的路為P1=u0u1…un,P2=v0v1…vn,分別連接路P1與P2的頂點ui與vi(i=0,1,…,n)所得到的圖,稱為長為n的梯子,記為Ln.

引理1[4]長為n的梯子Ln的1-因子數用m(Ln)表示,其中n=1,2,3,…,則

2 主要結果及其證明

圖1 2-Z-Ln

(1)

證明圖2-Z-Ln是3-正則3邊連通圖,顯然存在1-因子.圖2-Z-Ln的1-因子按飽和頂點u可分如下幾種情形求得:

情形1n為奇數.

(ⅱ)由m(Ln)的定義,若圖2-Z-Ln某個1-因子包含邊uu10,v10u20,則該1-因子一定包含邊v20v21,u21u22,v22v23,…,v2,n-1v2n,u2nv1n,vu1n,故這類1-因子數為m(Ln-1).

由(ⅰ)(ⅱ)可知,圖2-Z-Ln包含邊uu10的1-因子數為m(Ln)+m(Ln-1).由圖2-Z-Ln對稱性可知,包含邊uv20的1-因子數也為m(Ln)+m(Ln-1).

(ⅲ)由m(Ln)的定義,圖2-Z-Ln包含邊uv,u10u11,v10v11的1-因子數為m(Ln-2)·m(Ln).

(ⅳ)若圖2-Z-Ln的某個1-因子包含邊uv,u10u11,v10u20,則該1-因子一定包含邊v11v12,u12u13,v13v14,…,u1,n-1u1n,v1nu2n,v20v21,u21u22,v22v23,…,v2,n-1v2n,故這類1-因子數為1.

(ⅴ)由m(Ln)的定義,圖2-Z-Ln包含邊uv,u10v10的1-因子數為m(Ln-1)·m(Ln).

于是,當n為奇數時,圖2-Z-Ln的1-因子數為

σ(n)=2m(Ln)+2m(Ln-1)+m(Ln-2)·m(Ln)+m(Ln-1)·m(Ln)+1.

情形2n為偶數.

(ⅰ)由m(Ln)的定義,若圖2-Z-Ln某個1-因子包含邊uu10,v10v11,則該1-因子一定包含邊u11u12,v12v13,u13u14,…,u1,n-1u1n,v1nu2n,v2nv,故這類1-因子數為m(Ln-1).

(ⅱ)由m(Ln)的定義,若圖2-Z-Ln某個1-因子包含邊uu10,v10u20,則該1-因子一定包含邊v20v21,u21u22,v22v23,…,u2,n-1u2n,v2nv,故這類1-因子數為m(Ln-1).

由(ⅰ)(ⅱ)可知,圖2-Z-Ln包含邊uu10的1-因子數為2m(Ln-1).由圖2-Z-Ln對稱性可知,包含邊uv20的1-因子數也為2m(Ln-1).

(ⅲ)由m(Ln)的定義,圖2-Z-Ln包含邊uv,u10u11,v10v11的1-因子數為m(Ln-2)·m(Ln).

(ⅳ)由m(Ln)的定義,圖2-Z-Ln包含邊uv,u10v10的1-因子數為m(Ln-1)·m(Ln).

于是,當n為偶數時,圖2-Z-Ln的1-因子數為

σ(n)=4m(Ln-1)+m(Ln-2)·m(Ln)+m(Ln-1)·m(Ln).

綜上可知，(1)式成立.

定理2設長為n的梯子Ln的頂點集為V(Ln)={u0,u1,…,un,v0,v1,…,vn}.將梯子Ln的頂點u0,un分別與頂點u連接,再將Ln的頂點v0,vn分別與頂點v連接,這樣得到的圖記為H-Ln,如圖2所示.用τ(n)表示圖H-Ln的1-因子數,則

圖2 H-Ln

(2)

證明圖H-Ln是3-正則3邊圖,顯然存在1-因子.圖H-Ln的1-因子按飽和頂點u可分如下幾種情形求得:

情形1n為奇數.

(ⅰ)由m(Ln)的定義,若圖H-Ln某個1-因子包含邊uv,則該1-因子一定包含梯子Ln的1-因子,故圖H-Ln含邊uv的1-因子數為m(Ln).

(ⅱ)由m(Ln)的定義,若圖H-Ln的1-因子包含邊uu10,vv10,則這類1-因子數為m(Ln-1).

(ⅲ)由m(Ln)的定義,若圖H-Ln的1-因子包含邊uu1n,vv1n,則這類1-因子數為m(Ln-1).

于是,當n為奇數時,圖H-Ln的1-因子數為τ(n)=m(Ln)+2m(Ln-1).

情形2n為偶數.

(ⅰ)由m(Ln)的定義,若圖H-Ln某個1-因子包含邊uv,則該1-因子一定包含梯子Ln的1-因子,故圖H-Ln含邊uv的1-因子數為m(Ln).

(ⅱ)圖2-Z-Ln的包含邊uu10,v10v11,u11u12,…,u1,n-1u1n,v1nv的1-因子數為1.

(ⅲ)由m(Ln)的定義,圖H-Ln某個1-因子包含邊的1-因子數為m(Ln-1).

由(ⅱ)和(ⅲ)可知,圖H-Ln包含邊uu10的1-因子數為m(Ln-1)+1.由圖H-Ln對稱性可知,包含邊uu1n的1-因子數也為m(Ln-1)+1.于是,當n為偶數時,圖H-Ln的1-因子數為τ(n)=m(Ln)+2m(Ln-1)+2.

綜上可知，(2)式成立.

定理3設長為n的梯子Ln的頂點集為V(Ln)={u0,u1,…,un,v0,v1,…,vn}.將梯子Ln的頂點u0,v0分別與頂點u連接,再將Ln的頂點un,vn分別與頂點v連接,這樣得到的圖記為Z-Ln,如圖3所示.用φ(n)表示圖Z-Ln的1-因子數,則

圖3 Z-Ln

證明圖Z-Ln是3-正則3邊圖,顯然存在1-因子.圖Z-Ln的1-因子按飽和頂點u可分如下幾種情形求得:

情形1圖Z-Ln的包含邊uv的1-因子.

由m(Ln)的定義,若圖Z-Ln某個1-因子包含邊uv,則該1-因子一定包含梯子Ln的所有1-因子,故圖Z-Ln含邊uv的1-因子數為m(Ln).

情形2圖Z-Ln的不包含邊uv的1-因子.

(ⅰ)當n為奇數時,圖Z-Ln的1-因子有2個:一個是圖Z-Ln的包含邊uu0,v0v1,u1u2,…,vn-1vn,u1nv的1-因子;另一個是圖Z-Ln的包含邊uv0,u0u1,v1v2,…,un-1un,v1nv的1-因子.

(ⅱ)當n為偶數時,圖Z-Ln的1-因子也有2個:一個是圖Z-Ln的包含邊uu0,v0v1,u1u2,…,un-1un,v1nv的1-因子；另一個是圖Z-Ln的包含邊uv0,u0u1,v1v2,…,vn-1vn,u1nv的1-因子.

綜上可知,無論n是奇數還是偶數,都有φ(n)=m(Ln)+2,于是