下整和圖與排斥下整和圖.pdf

1、本文所用圖論基本術(shù)語與符號遵循文獻(xiàn). 1990年Harary提出和圖的概念.1994年Harary提出整和圖的概念.令N(Z)表示正整數(shù)(整數(shù))集，N(Z)的非空有限子集S的和(整和)圖G+(S)是圖(S，E)，其中uv∈E當(dāng)且僅當(dāng)u+v∈S.一個(gè)圖G稱為和(整和)圖，若它同構(gòu)于某個(gè)S()N(Z)的和(整和)圖.我們說S給出了G的一個(gè)和(整和)標(biāo)號，并且將頂點(diǎn)與其標(biāo)號不加區(qū)分.G的和數(shù)(整和數(shù))σ(G)(ζ(G))是使得G∪nK

2、1是和圖(整和圖)的非負(fù)整數(shù)n的最小值. 1990年Boland等人提出模和圖的概念.模和圖是取S(){1，2，…，m-1}且所有算術(shù)運(yùn)算均取模m(≥|S|+1)的和圖.由此,2002年Sutton等人提出了模和數(shù)的概念.一個(gè)圖G的模和數(shù)ρ(G)是使得G∪ρK1是模和圖的非負(fù)整數(shù)ρ的最小值. 2003年Miller[6]等人提出排斥圖的概念.圖G∪nK1的(整)和標(biāo)號S稱為排斥的(exclusive)，若對每條邊uv∈E

3、(G)，u+v∈S＼V(G).圖G的排斥和數(shù)ε(G)是使得G∪nK1有排斥和標(biāo)號的非負(fù)整數(shù)n的最小值. 2004年竇文卿提出模整和圖的概念.模整和圖是取S(){0，1，2，…，m-1}且所有算術(shù)運(yùn)算均取模m(≥|S|)的和圖.一個(gè)圖G的模整和數(shù)ψ(G)是使得G∪ψK1是模整和圖的非負(fù)整數(shù)ψ的最小值. 從實(shí)用的觀點(diǎn)來看，各種和圖標(biāo)號都可用作圖的壓縮表示，即表示圖的數(shù)據(jù)結(jié)構(gòu).當(dāng)利用輸入圖的壓縮表示來工作時(shí)，數(shù)據(jù)壓縮不僅可以節(jié)

4、省內(nèi)存，還可以加快某些圖算法的運(yùn)算速度. 本文提出如下定義： 用[x]表示不超過實(shí)數(shù)x的最大整數(shù)(稱為x的下整數(shù))，Q*表示正有理數(shù)集.Q*的非空有限子集S的下整和圖G+(S)是圖(S，E)，其中uv∈E當(dāng)且僅當(dāng)[u+v]∈S.一個(gè)圖G稱為下整和圖，若它同構(gòu)于某個(gè)S()Q*的下整和圖.我們說S給出G的一個(gè)下整和標(biāo)號，并且頂點(diǎn)與標(biāo)號不加區(qū)分.下整和數(shù)σ'(G)是使得G∪nK1是下整和圖的非負(fù)整數(shù)n的最小值. 如果兩

5、條邊有一個(gè)公共的端點(diǎn)，則我們稱這兩條邊是鄰接的.在G∪σ'(G)K1的一個(gè)下整和標(biāo)號中，對于一個(gè)頂點(diǎn)w，如果存在某條邊uv，使得w=[u+v]，則稱w為工作頂點(diǎn).顯然，工作頂點(diǎn)均為整數(shù)點(diǎn).對于邊uv，如果有[u+v]∈V(G)，則稱這條邊是工作的. 假設(shè)S是圖G的下整和標(biāo)號，且整數(shù)點(diǎn)均為工作頂點(diǎn)，則稱S是圖G的標(biāo)準(zhǔn)下整和標(biāo)號. 圖G∪nK1的下整和標(biāo)號S稱為排斥的(exclusive)，若對每條邊uv∈E(G)，[u+v

6、]∈S＼V(G).圖G的排斥下整和數(shù)ε'(G)是使得G∪nK1有排斥下整和標(biāo)號的非負(fù)整數(shù)n的最小值. 下整和標(biāo)號與排斥下整和標(biāo)號是圖的新的壓縮表示. 在本文的第一章中，我們主要介紹(下整)和圖的一些概念，術(shù)語，符號；第二章給出下整和圖與排斥下整和圖的一些結(jié)構(gòu)性質(zhì)；第三章確定了幾類圖的下整和數(shù)與排斥下整和數(shù)，并給出確定某些圖類下整和數(shù)的一種方法；第四章討論了幾類圖的下整和性與排斥下整和性；第五章指出了有待研究的內(nèi)容.若集合

7、S={xi|1≤i≤n}，則令S-[S]={xi-[xi]|1≤i≤n}，且對實(shí)數(shù)k，令k[S]+S={k[xi]+xi|1≤i≤n}，S.+k={xi+k|1≤i≤n}. 我們主要得到如下結(jié)果. 定理2.5設(shè)圖G=(V,E)為非空下整和圖，則a)不存在點(diǎn)v1，v2，v3，v4滿足[v1]=[v4]，[v2]=[v3]，v1v2，v3v4()E，v1v3，v2v4∈E. b)不存在點(diǎn)vi(1≤i≤5)，滿足0＜v

8、i-v5≤1(1≤i≤4)，[v5+v1]=[v5+v4]，v5v1,v5v4，v1v3，v2v4∈E，v1v2，v3v4()E. c)不存在點(diǎn)vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v1v4，v2v4，v1v5，v3v5，v2v6，v3v6∈E,v3v4，v2v5，v1v6()E.d)不存在點(diǎn)vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v1v4，v2v4，v2v5，v2v6，v3v6∈E，v3v4，v1v5

9、，v3v5，v1v6()E.e)不存在點(diǎn)vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v1v4，v2v4，v2v5，v1v6∈E，v3v4，v1v5,v3v5，v2v6，v3v6()E.f)不存在點(diǎn)vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v3v4，v2v5，v1v6∈E，v1v4，v2v4，v1v5，v3v5，v2v6，v3v6()E. 定理2.6設(shè)圖G為下整和圖，S是G的下整和標(biāo)號且max(S-[S])＜1/

10、2，k是非負(fù)整數(shù)，則k[S]+S也是G的下整和標(biāo)號. 定理2.7設(shè)圖G1，G2無孤立點(diǎn)，Si是Gi∪σ'(Gi)K1的下整和標(biāo)號，σ'(Gi)≥1，且max(Si-[Si])＜1/2，Ci是Si中的工作點(diǎn)集(i=1，2)，且C2中存在一點(diǎn)與maxC1互質(zhì)，則σ'(G1∪G2)≤σ'(G1)+σ'(G2)-1. 定理2.8設(shè)圖G無孤立點(diǎn)，S=S1∪S2為G∪σ'(G)K1的下整和標(biāo)號，其中S1為G的標(biāo)號集，S2為孤立點(diǎn)的標(biāo)

11、號集，且min(S1-[S1])≥1/2，k為非負(fù)整數(shù)，則k([S]+1)+S為G∪σ'(G)K1的下整和標(biāo)號. 定理2.9對任意下整和圖G，V(G)={vi|0≤i≤n-1}，若v0vi∈E(1≤i≤4)，v1v2，v3v4∈E，v1v3，v1v4，v2v4()E，則圖G的工作點(diǎn)數(shù)大于1. 在定理2.10～2.13中我們得到下面結(jié)果： 下整和圖若包含C5，C6，K2,2,2或(-P6)作為其導(dǎo)出子圖，則工作點(diǎn)數(shù)

12、大于1.3.1節(jié)主要證明mK2，Kn，Kr,s,Kn-E(Kr)，Kn∪Kr,s,K1,n,1是下整和圖，Km,n,q(m，n，q≥2)的下整和數(shù)為2，C5，C5∪Kn的下整和數(shù)為1. 3.2節(jié)主要證明mK2，Kn，Kr，s，Kn∪Kr,s,Kn-E(Kr)(1≤r≤n-1)，K1,n,q的排斥下整和數(shù)為1，Km,n,q(m，n，q≥2)的排斥下整和數(shù)為2. 3.3節(jié)給出確定圖類下整和數(shù)的一種方法，并以Km，n，q(m，

13、n，q≥2)，Kr，s為例介紹了這種方法.這種方法可讓我們由一類下整和圖構(gòu)造出無數(shù)多類下整和圖，也可由一類圖的下整和數(shù)確定出另一類圖的下整和數(shù)的界.需要用到對稱點(diǎn)的定義和定理3.3.1. vi，vj稱為圖G中的對稱點(diǎn)，如果對圖G中任意不同于vi，vj的點(diǎn)vk，都滿足vivk∈E(G)當(dāng)且僅當(dāng)vjvk∈E(G). 定理3.3.1設(shè)v1，v2為圖G中的兩對稱點(diǎn),G1=G+v1v2(若v1v2∈E(G)，則G1=G)，G2=G

14、-v1v2(若v1v2()E(G)，則G2=G)，則min(σ'(G1)，σ'(G2))≤σ'(G-v1). 4.1節(jié)討論圖Cn(n≥3)，Kn-E(mK2)(2≤2m≤n)，(-)Cn(n≥3)，Kr，s-E(mK2)(r，s≥m)，Wn(n≥3)，F(xiàn)n(n≥2)，Kn-E(Pm)(n≥m)在什么條件下是下整和圖.主要有下面結(jié)果： 定理4.1.1Cn(n≥3)為下整和圖當(dāng)且僅當(dāng)n=3或4. 定理4.1.2Kn-

15、E(mK2)(2≤2m≤n)是下整和圖當(dāng)且僅當(dāng)m=1或2. 定理4.1.3(-Cn)(n≥3)為下整和圖當(dāng)且僅當(dāng)n=3或4. 定理4.1.4Kr,s-E(mK2)(r，s≥m)是下整和圖當(dāng)且僅當(dāng)m=1，2或3. 定理4.1.5Wn(n≥3)為下整和圖當(dāng)且僅當(dāng)n=3或4. 定理4.1.6Fn(n≥2)為下整和圖當(dāng)且僅當(dāng)n=2，3或4. 定理4.1.7Kn-E(Pm)(n≥m)為下整和圖當(dāng)且僅當(dāng)1≤m

16、≤5. 4.2節(jié)討論圖Fn(n≥2)，Wn(n≥3)，Kr，s-E(mK2)(r，s≥m)，Kn-E(mK2)(2≤2m≤n)，Kw-E(Pm)(n≥m)在什么條件下排斥下整和數(shù)為1.主要有下面結(jié)果： 定理4.2.1ε'(Fn)=1(n≥2)當(dāng)且僅當(dāng)n=2，3. 定理4.2.2ε'(Wn)=1(n≥3)當(dāng)且僅當(dāng)n=3. 定理4.2.3ε'(Kr，s-E(mk2))=1(r，s≥m，r，s≥2)當(dāng)且僅當(dāng)m=