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

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

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

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

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

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

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

7、S={xi|1≤i≤n}，則令S-[S]={xi-[xi]|1≤i≤n}，且對實數(shù)k，令k[S]+S={k[xi]+xi|1≤i≤n}，S.+k={xi+k|1≤i≤n}. 我們主要得到如下結果. 定理2.5設圖G=(V,E)為非空下整和圖，則a)不存在點v1，v2，v3，v4滿足[v1]=[v4]，[v2]=[v3]，v1v2，v3v4()E，v1v3，v2v4∈E. b)不存在點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)不存在點vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v1v4，v2v4，v1v5，v3v5，v2v6，v3v6∈E,v3v4，v2v5，v1v6()E.d)不存在點vi(1≤i≤6)，滿足[vi]=k(1≤i≤3)，v1v4，v2v4，v2v5，v2v6，v3v6∈E，v3v4，v1v5

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

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

11、號集，且min(S1-[S1])≥1/2，k為非負整數(shù)，則k([S]+1)+S為G∪σ'(G)K1的下整和標號. 定理2.9對任意下整和圖G，V(G)={vi|0≤i≤n-1}，若v0vi∈E(1≤i≤4)，v1v2，v3v4∈E，v1v3，v1v4，v2v4()E，則圖G的工作點數(shù)大于1. 在定理2.10～2.13中我們得到下面結果： 下整和圖若包含C5，C6，K2,2,2或(-P6)作為其導出子圖，則工作點數(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為例介紹了這種方法.這種方法可讓我們由一類下整和圖構造出無數(shù)多類下整和圖，也可由一類圖的下整和數(shù)確定出另一類圖的下整和數(shù)的界.需要用到對稱點的定義和定理3.3.1. vi，vj稱為圖G中的對稱點，如果對圖G中任意不同于vi，vj的點vk，都滿足vivk∈E(G)當且僅當vjvk∈E(G). 定理3.3.1設v1，v2為圖G中的兩對稱點,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)在什么條件下是下整和圖.主要有下面結果： 定理4.1.1Cn(n≥3)為下整和圖當且僅當n=3或4. 定理4.1.2Kn-

15、E(mK2)(2≤2m≤n)是下整和圖當且僅當m=1或2. 定理4.1.3(-Cn)(n≥3)為下整和圖當且僅當n=3或4. 定理4.1.4Kr,s-E(mK2)(r，s≥m)是下整和圖當且僅當m=1，2或3. 定理4.1.5Wn(n≥3)為下整和圖當且僅當n=3或4. 定理4.1.6Fn(n≥2)為下整和圖當且僅當n=2，3或4. 定理4.1.7Kn-E(Pm)(n≥m)為下整和圖當且僅當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.主要有下面結果： 定理4.2.1ε'(Fn)=1(n≥2)當且僅當n=2，3. 定理4.2.2ε'(Wn)=1(n≥3)當且僅當n=3. 定理4.2.3ε'(Kr，s-E(mk2))=1(r，s≥m，r，s≥2)當且僅當m=