几类图的(排斥,排斥整,下整)和数

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:liuaxing1314
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文仅考虑有限无向简单图,所用图论基本术语与符号遵循文献<[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 广义毛虫是整和图。
其他文献
80年代以来,有关非线性时间序列模型的研究,由于它所具有广泛的实际应用背景,受到普遍重视,目前已成为时间序列分析理论发展的一个重要研究方向. 但是在以往的时间序列模型的文
本文利用动力系统分支思想研究了一个广义的正则长波方程(RLW方程),证明了该方程在不同的参数条件下存在光滑和非光滑的行波解(孤立波,扭子和反扭子波以及不可数多周期波解),并
设G是一个有限群。如果存在适当的正整数d使得G(