幾類圖的(整,模)和數(shù).pdf

1、該文僅討論有限無向簡單圖.用N表示自然數(shù)集;N<'+>表示正整數(shù)集;Z表示整數(shù)集.(整)和圖的概念由F.Harary[1,2]提出.設(shè)G=(V(G),E(G))是一個(gè)圖,其中V(G),E(G)分別表示G的頂點(diǎn)集和邊集,簡記為V和E.對(duì)于圖G=(S,E),其中S為N<'+>(z)的非空有限子集,若對(duì)于S中任意互異頂點(diǎn)u和u,都有uu∈E當(dāng)且僅當(dāng)u+u∈S,則稱圖G為S的(整)和圖,記為G<'+>(S).對(duì)于圖G,若 S N<'+>(z),

2、使得G≌G<'+>(S),則稱G為(整)和圖.對(duì)于任意圖G,存在最小的非負(fù)整數(shù)σ=σ(G)(ζ=ζ(G))使得G∪σ(ζ)K<,1>為(整)和圖,稱此數(shù)為G的(整)和數(shù),即:σ=σ(G)=min{s: S N+,使得G ∪ sK<,1>≌G+(S),其中s≥0 }((=((G)=min{s: S z,使得G∪sK1≌G+(S),其中s≥0}).顯然有ζ(G)≤σ(G).為了更好地理解和圖與整和圖的定義,許多作者<'[3]>又給出(整)和

3、標(biāo)號(hào)的定義:圖G的一個(gè)(整)標(biāo)號(hào)是V(G)→N<'+>(z)的一一映射L.如果存在圖G的一個(gè)標(biāo)號(hào)L滿足:對(duì)V(G)中任意兩個(gè)互異頂點(diǎn)u和v,uv∈E(G)←→ w∈V(G)使得L(u)+L(v)=L(w),則稱此標(biāo)號(hào)L為圖G的一個(gè)(整)和標(biāo)號(hào).類似地,如果在上述和圖,和數(shù)與和標(biāo)號(hào)的定義中,加法運(yùn)算均是在取某個(gè)模m意義下進(jìn)行,并且S{1,2....,m-1}(其中m≥|V|+1且m∈N<'+>),則我們就得到了模和圖,模和數(shù)ρ(G)與模和

4、標(biāo)號(hào)的概念.為了方便,在該文中,如果沒有特殊說明,頂點(diǎn)的(整,模)和標(biāo)號(hào)與頂點(diǎn)可以不加區(qū)別.經(jīng)過許多作者的研究,目前已確定一些簡單圖類的和數(shù)與整和數(shù),如:圈C<,n><'[1][4]>,輪W<,n><'[5][6]>,路P<,n><'[1]>,扇F<,n><'[7]>,酒會(huì)圖￣(nK<,2>)[8]和完全圖K<,n><'[9][10][6]>,特別地有:定理E<'[8]>σ(￣nK<,2>)=ζ(￣nK<,2>)=4n-5(n≥2).定

5、理G<'[11]>立方體E<'3>非整和圖.該文第一部分確定了四類圖￣C<,n>,￣W<,n>,￣P<,n>和￣F<,n>的和數(shù)與整和數(shù),主要結(jié)果如下:定理2.1設(shè)n為大于9的自然數(shù),則ζ(￣C<,n>)=σ(￣C<,n>)=2n-7.推論2.2設(shè)n為大于9的自然數(shù),則ζ(￣W<,n>)=σ(￣W<,n>)=2n-8.定理3.1設(shè)n為大于10的自然數(shù),則ζ(￣P<,n>)=σ(￣P<,n>)=2n-7.推論3.2設(shè)n為大于10的自然數(shù),