關(guān)于幾類圖的(模,整,模整)和數(shù).pdf

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

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

3、圖G稱為(整)和圖,若它同構(gòu)于某個S N(Z)的和圖.(整)和數(shù)σ(G)(ζ(G))是使得G U nK<,1>是(整)和圖的非負整數(shù)n的最小值.模和圖是取S Z<,m>\{0}且所有算術(shù)運算均取模m(≥|S|+1)的和圖.一個圖G的模和數(shù)ρ(G)是使得G U ρK<,1>是模和圖的孤立點數(shù)ρ的最小值.在該文中,我們主要得到如下定理.定理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為偶數(shù),4,n≥5且n為奇數(shù).定理2.2.2當(dāng)n≥3時,F<,n>是整和圖.定理3.1.1當(dāng)n≥6時,ρ(K<,n,n>-E(nK<,2>))=n-2.定理3.2.1當(dāng)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是偶數(shù),或(5/2)r≤s≤3r-4,s是奇數(shù)且5 |s,r,r≤s≤2r-1(r≠2)或s=2r+1(r≥5),0或r,2r+3≤s<(5/2)r,s是奇數(shù),或(5/2)r≤s≤3r-4,s是奇數(shù)且不能被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且所有算術(shù)運算均取模m(≥|S|)的和圖.一個圖G的模整和數(shù)ψ(G)是使得G U ψK<,1>是模整和圖的孤立點數(shù)ψ的最小值.引理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/