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

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

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

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

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

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

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