3類3-正則圖中的1-因子數(shù)*

唐保祥，任 韓

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

研究圖的1-因子計(jì)數(shù)問題[1-4]有重要的理論價(jià)值和現(xiàn)實(shí)意義,其研究成果已應(yīng)用于多個(gè)領(lǐng)域.分類嵌套遞推方法,是求圖的1-因子數(shù)的一種非常有效的方法[4-6].筆者擬利用分類嵌套遞推方法給出3類特殊3-正則圖的1-因子數(shù)的計(jì)算公式.

1 預(yù)備知識(shí)

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

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

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

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

圖1 2-Z-Ln

(1)

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

情形1n為奇數(shù).

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

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

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

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

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

于是,當(dāng)n為奇數(shù)時(shí),圖2-Z-Ln的1-因子數(shù)為

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

情形2n為偶數(shù).

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

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

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

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

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

于是,當(dāng)n為偶數(shù)時(shí),圖2-Z-Ln的1-因子數(shù)為

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

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

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

圖2 H-Ln

(2)

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

情形1n為奇數(shù).

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

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

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

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

情形2n為偶數(shù).

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

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

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

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

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

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

圖3 Z-Ln

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

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

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

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

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

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

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