论文部分内容阅读
本文仅考虑有限无向简单图,所用图论基本术语与符号遵循文献<[1]>
1990年Harary<[2]>提出和图的概念.1994年Harary<[3]>提出整和图的概念.令N(Z)表示正整数(整数)集,N(z)的非空有限子集S的和(整和)图G<+>(S)是图(S,E),其中uV∈E当且仅当u+v∈S.一个图G称为和(整和)图,若它同构于某个ScN(Z)的和(整和)图.此时我们说S给出了G的一个和(整和)标号,并且将顶点与其标号不加区分.G的和数(整和数)σ-(G)(ζ(G))是使得Gu nK<,l>是和图(整和图)的非负整数n的最小值.
2003年Miller<[4]>等人提出排斥图的概念.图GunK<,l>的(整)和标号S称为排斥的(exclusive),若对每条边uv∈E(G),u+v∈S\V(G).图G的排斥和(整和)数ε(G)(ζ(G))是使得GunK<,l>有排斥和(整和)标号的非负整数n的最小值.
2004年李敏<[5]>提出下整和图的概念.令Q<+>表示正有理数集.Q<+>的非空有限 子集s的下整和图G+(s)是图(s,E),其中uV∈E当且仅当μ+ν∈S.一个图G称为下整和图,若它同构于某个ScQ<+>的下整和图.我们说S给出G的一个下整和标号,并且顶点与标号不加区分.下整和数σ′(G)是使得GunK<,1>是下整和图的非负整数n的最小值.
图GunK<,1> 的下整和标号S称为排斥的(exclusive),若对每条边uv∈E(G)当且仅当μ+ν∈s\V(G).图G的排斥下整和数ε′(G)是使得Gu nK<,1l> 有排斥下整和标号的非负整数n的最小值.
从实用的观点来看,各种和图标号都可被计算机用作图的压缩表示.当利用它们来工作时,不仅可以节省内存,还可以加快某些图算法的运算速度.
在本文的第一章中,我们主要介绍了一些文章中所涉及的概念,术语,符号;第二章介绍了棱柱En(n≥3)、残棱柱E<*>(n≥3)、残皇冠C′<,n>⊙K<,1>(n≥3)、梯子L<,n><,n≥2)、梯子细分图L<,n><*>(n≥2)的概念,并给出了它们的排斥(整,下整)和数;第三章给出了三毛虫树,星毛虫树,广义双星,广义毛虫的概念,并证明了这几类特殊的树是整和图。 我们主要得到如下结果.
定理2.1 设n为大于等于3的自然数,则ε(E)<,n>=5。
定理2.2 设n为大于等于3的自然数,则ζ(E<,n><*><,n>)=4。
定理2.3 设n为大于等于3的自然数,则ε(C<,n>⊙K<,1>)=3。
定理2.4 L<,n>(n≥2)是下整和图。
定理2.5 设n为大于1的自然数,则ε(L<,n>)=1。
定理2.6 设n为大于1的自然数,则ε(L<,n><*>)=3。
定理2.7 设n为大于1的自然数,则ε(L<,n><*>)=2。
定理3.1 三毛虫树是整和图。
定理3.2 偶星毛虫树是整和图。
定理3.3 广义双星是整和图。
定理3.4 广义毛虫是整和图。