（下整）和圖的結(jié)構(gòu)與幾類圖的（下整）和數(shù).pdf

1、本文僅考慮有限無向簡單圖，所用圖論符號及術(shù)語遵循文獻(xiàn)[1]. 1990年，F(xiàn).Harary[2]提出了和圖，和數(shù)的概念，從而開始了對和圖的研究. 1994年，F(xiàn).Harary[3]又介紹了整和圖，整和數(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.一個圖G稱為(整)

2、和圖，若它同構(gòu)于某個S()N(Z)的(整)和圖.圖G的(整)和數(shù)σ(G)((G))是使得G∪nK1是(整)和圖的非負(fù)整數(shù)n的最小值.一個連通圖的最小度δ是其和數(shù)的下界，能達(dá)到此下界的圖稱之為δ-最優(yōu)的. 模和圖的概念是由Boland等人[4]提出的. 模和圖是取S()Zm\{0}且所有算術(shù)運(yùn)算均取模m(≥|S|+1)的和圖.一個圖G的模和數(shù)ρ(G)是使得G∪ρK1是模和圖的孤立點數(shù)ρ的最小值. 2004年，李敏[

3、5]提出下整和圖的概念.用Q+表示正有理數(shù)集.Q+的非空有限子集S的下整和圖G+(S)是圖(S，E)，其中uv∈E當(dāng)且僅當(dāng)「u+v」∈S. 從實用的觀點來看，各種和圖標(biāo)號都可用作表達(dá)圖的數(shù)據(jù)結(jié)構(gòu)，它們比用其他的方式輸入圖更能節(jié)省存儲空間. 到目前為止，和圖方面的研究已取得許多成果，給出了很多的一般性理論.現(xiàn)在研究的重點主要集中在兩個方面：一方面是圖的和數(shù)與它的圖參數(shù)、圖結(jié)構(gòu)方面的聯(lián)系；另一方面確定一些特殊圖類的(模、整、

4、下整)和數(shù). 在本文的第一章中，我們主要介紹了文章中所涉及的一些概念、術(shù)語和符號以及前人關(guān)于和圖的一些重要研究結(jié)果；在第二章中我們給出關(guān)于(下整)和圖的一些結(jié)構(gòu)性結(jié)果；第三章中，我們給出路、毛蟲、皇冠、完全圖不交并等一些特殊圖類的下整和標(biāo)號. 扇Fn是具有頂點集V={c，a1，a2，…，an}和邊集E={ca1，ca2，…，can，a1a2，a2a3，…，an-1an}的圖(V,E)，每條邊cai，i=1，…，n稱為一條

5、輻.在Fn∪σ’(Fn)的一個下整和標(biāo)號中，如果「c+ai」∈V(Fn)，則稱cai為工作輻. 將一個圈Cm的n-個拷貝粘合于同一頂點所形成的圖稱之為風(fēng)車.記作wnm(m≥3).中心粘合點記為c，第i個圈上其余各點分別記作ai，…，aim-1，且aim=c. 毛蟲是這樣的一棵樹，去掉其葉子頂點(即1度頂點)后為一條路. 給定圖G1，G2，設(shè)G1有n個頂點，則G1⊙G2表示這樣的圖：取G2的n個拷貝，且將G1的第i

6、個點與G2的第i個拷貝的每個點連邊所得的圖.則Cn⊙K1(n≥3)稱為皇冠. 樹T被稱作三路樹(three-pathtree)，如果它由具有一個公共端點的三條路組成.當(dāng)它對應(yīng)的三條路分別是Pm，Pn，Pt時，這樣的樹記作P(m，n，t)，它相應(yīng)的三條路分別記作：Pm=(a1，a2，…，am)，Pn=(am，b2，b3，…，bn)，Pt=(am，c2，c3，…，ct)其中am為它們的公共端點. 在本文中，我們主要得到如下定

7、理.定理2.1.1設(shè)圖G1，G2不同為和圖，Li是Gi∪σ(Gi)K1的和標(biāo)號，若存在n∈L2，使得n與maxL1互質(zhì)，則σ(G1∪G2)≤σ(G1)+σ(G2)-1. 定理2.2.1風(fēng)車wnm(m≠4，5)是δ-最優(yōu)的. 定理2.3.1在Fn∪σ'(Fn)K1(n≥5)的一個下整和標(biāo)號中，至少存在一條輻是非工作的. 定理2.4.1設(shè)三路樹P(m，n，t)(m，n，t＞2)存在一組下整和標(biāo)號，則最大整數(shù)標(biāo)號必為一