幾類圖的（排斥，排斥整，下整）和數(shù).pdf

1、本文僅考慮有限無向簡單圖，所用圖論基本術(shù)語與符號遵循文獻<'[1]> 1990年Harary<'[2]>提出和圖的概念．1994年Harary<'[3]>提出整和圖的概念．令N(Z)表示正整數(shù)(整數(shù))集，N(z)的非空有限子集S的和(整和)圖G<'+>(S)是圖(S,E)，其中uV∈E當且僅當u+v∈S．一個圖G稱為和(整和)圖，若它同構(gòu)于某個ScN(Z)的和(整和)圖．此時我們說S給出了G的一個和(整和)標號，并且將頂點與其標

2、號不加區(qū)分．G的和數(shù)(整和數(shù))σ-(G)(ζ(G))是使得Gu nK<,l>是和圖(整和圖)的非負整數(shù)n的最小值． 2003年Miller<'[4]>等人提出排斥圖的概念．圖GunK<,l>的(整)和標號S稱為排斥的(exclusive)，若對每條邊uv∈E(G)，u+v∈S＼V(G)．圖G的排斥和(整和)數(shù)ε(G)(ζ(G))是使得GunK<,l>有排斥和(整和)標號的非負整數(shù)n的最小值． 2004年李敏<'[5]>提

3、出下整和圖的概念．令Q<'+>表示正有理數(shù)集．Q<'+>的非空有限 子集s的下整和圖G+(s)是圖(s,E)，其中uV∈E當且僅當μ+ν∈S．一個圖G稱為下整和圖，若它同構(gòu)于某個ScQ<'+>的下整和圖．我們說S給出G的一個下整和標號，并且頂點與標號不加區(qū)分．下整和數(shù)σ′(G)是使得GunK<,1>是下整和圖的非負整數(shù)n的最小值． 圖GunK<,1> 的下整和標號S稱為排斥的(exclusive)，若對每條邊uv∈E(G

4、)當且僅當μ+ν∈s＼V(G)．圖G的排斥下整和數(shù)ε′(G)是使得Gu nK<,1l> 有排斥下整和標號的非負整數(shù)n的最小值． 從實用的觀點來看，各種和圖標號都可被計算機用作圖的壓縮表示．當利用它們來工作時，不僅可以節(jié)省內(nèi)存，還可以加快某些圖算法的運算速度． 在本文的第一章中，我們主要介紹了一些文章中所涉及的概念，術(shù)語，符號；第二章介紹了棱柱En(n≥3)、殘棱柱E<'n><'*>(n≥3)、殘皇冠C′<,n>⊙K<,

5、1>(n≥3)、梯子L<，n><,n≥2)、梯子細分圖L<,n><'*>(n≥2)的概念，并給出了它們的排斥(整，下整)和數(shù)；第三章給出了三毛蟲樹，星毛蟲樹，廣義雙星，廣義毛蟲的概念，并證明了這幾類特殊的樹是整和圖。 我們主要得到如下結(jié)果． 定理2.1 設n為大于等于3的自然數(shù)，則ε(E)<，n>=5。 定理2.2 設n為大于等于3的自然數(shù)，則ζ'(E<,n><'*><,n>)=4。 定理2.3

6、 設n為大于等于3的自然數(shù)，則ε(C'<,n>⊙K<,1>)=3。 定理2.4 L<,n>(n≥2)是下整和圖。 定理2.5 設n為大于1的自然數(shù)，則ε'(L<,n>)=1。 定理2.6 設n為大于1的自然數(shù)，則ε(L<,n><'*>)=3。 定理2.7 設n為大于1的自然數(shù)，則ε'(L<,n><'*>)=2。 定理3.1 三毛蟲樹是整和圖。 定理3.2