關于幾類圖的(模,整,模整)和數.pdf

1、從實用的觀點來看,和圖標號可用作圖的壓縮表示,即表示圖的數據結構.當利用輸入圖的壓縮表示來工作時,數據壓縮不僅可以節(jié)省內存,還可以加快某些圖算法的運算速度.1990年,Harary提出了和圖的概念,從而開始了對和圖的研究.目前對和圖的研究主要是從一些特殊圖類著手,確定它們的和數、整和數與模和數.迄今為止,已經取得了許多成果.在該文的第一章中,我們主要介紹了文章中所涉及的一些概念、術語和符號;在第二章和第三章中,我們分別確定了扇Fn(n≥

2、2)與圖Kn,n-E(nK2)的和數、整和數以及模和數;在第四章中,我們主要研究完全二分圖與圖Kn-E(Kr)的模和數;最后,在第五章中,我們定義了模整和圖與模整和數的概念,給出了模和數、整和數以及模整和數之間的若干關系,并討論了若干圖類的模整和數.令V(G)表示圖G的頂點集合,|S|表示集合S中元素的個數.令N(Z)表示正整數(整數)集,N(Z)的非空有限子集S的和圖G,'+>(S)是圖(S,E),其中uv∈E當且僅當u+v∈S.一個

3、圖G稱為(整)和圖,若它同構于某個S N(Z)的和圖.(整)和數σ(G)(ζ(G))是使得G U nK<,1>是(整)和圖的非負整數n的最小值.模和圖是取S Z<,m>\{0}且所有算術運算均取模m(≥|S|+1)的和圖.一個圖G的模和數ρ(G)是使得G U ρK<,1>是模和圖的孤立點數ρ的最小值.在該文中,我們主要得到如下定理.定理2.1.1 ρ(F<,4>)=1,對n=3和n≥5有ρ(F<,n>)=2.定理2.2.1對n≥3,σ(

4、F<,n>)=2,n=4,3,n=3或者n≥6且n為偶數,4,n≥5且n為奇數.定理2.2.2當n≥3時,F<,n>是整和圖.定理3.1.1當n≥6時,ρ(K<,n,n>-E(nK<,2>))=n-2.定理3.2.1當n≥6時,σ(K<,n,n>-E(nK<,2>))=2n-3,ζ(K<,n,n>-E(nK<,2>))=2n-5.定理4.1.1對s≥r,ρ(K<,r,s>)=0,s>r=1,或s=r=2,或s>3r-4(r≥2),或3r

5、-4≥s>2r-1,s是偶數,或(5/2)r≤s≤3r-4,s是奇數且5 |s,r,r≤s≤2r-1(r≠2)或s=2r+1(r≥5),0或r,2r+3≤s<(5/2)r,s是奇數,或(5/2)r≤s≤3r-4,s是奇數且不能被5整除.定理4.2.1ρ(K<,n>-E(K<,r>))=0,r=n或r=n-1(n≥3).=1,r=1,2 ≤n≤3.=n,r=1,n≥4.=r,n/2≤r≤n-3.=r-1,r=n-2≥3.∈[n-1,2(n

6、-r)],2≤r且所有算術運算均取模m(≥|S|)的和圖.一個圖G的模整和數ψ(G)是使得G U ψK<,1>是模整和圖的孤立點數ψ的最小值.引理5.1.1對任意的圖G,若不存在度為|V(G)|-1的頂點,則ψ(G)=ρ(G).定理5.1.1對任意的圖G,有ψ(G)≤ ζ(G).定理5.1.2對任意的圖G,若不存在度為|V(G)

7、|-1的頂點或者ζ(G)≠0,則ρ(G)≤ζ(G).推論5.1.1對滿足s≥r和r+s≥3的完全二分圖K<,r,s>有ψ(K<,r,s>)=ρ(K<,r,s>).推論5.1.2ψ(K<,n,n>-E(nK<,2>))=ρ(K<,n,n>-E(nK<,2>)).推論5.1.3扇F<,n>是模整和圖.推論5.1.4輪W<,n>是模整和圖.定理5.2.1ψ(K<,n>-E(K<,r>))=0,r≥n-3,或r=1,或n-r | r.=r,n/