几类图（排斥，排斥整，下整）和数

《几类图（排斥，排斥整，下整）和数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创声明Y1012480本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得(注：如没有其他需要特别声明的，本栏可空)或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：南秀壹导师签字：学位论文版权使用授权书南黝狻一本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复

2、印件和磁盘，允许论文被查阅和借阅。本人授权』越可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：谭携莲导师签字高蚓钆签字日期：200年月日签字日期：200‘年f『月纠伯山东师范人学硕士学位论文几类图的(排斥，排斥整，下整)和数高秀莲(山东师范大学数学科学学院，济南，山东，250014)中文摘要本文仅考虑有限无向简单图，所用图论基本术语与符号遵循文献‘”．1990年Harary[21提出和图的概念．1994年H

3、arary_『31提出整和图的概念．令N(z)表示正整数(整数)集，N(z)的非空有限子集s的和(整和)图G十(s)是图(s，E)，其中uvEE当且仅当u+vES．一个图G称为和(整和)图，若它同构于某个ScN(Z)的和(整和)图．此时我们说S给出了G的一个和(整和)标号，并且将顶点与其标号不加区分．G的和数(整和数)O-(G)(f(G))是使得GUnKl是和图(整和图)的非负整数n的最小值．2003年Miller[41等人提出排斥图的概念．图GUnKl的(整)和标号s称为排斥的(exclusive)，若对每条边uvEE

4、(G)，u+v∈s＼V(G)．图G的排斥和(整和)数占(G)(f’(G))是使得GUnKl有排斥和(整和)标号的非负整数n的最小值．2004年李敏‘51提出下整和图的概念．令Q+表示正有理数集．O+的非空有限子集s的下整和图G十(S)是图(s，E)，其中UVEE当且仅当bu+VJES．一个图G称为下整和图，若它同构于某个ScO+的下整和图．我们说S给出G的一个下整和标号，并且顶点与标号不加区分．下整和数叮’(G)是使得GUnKl是下整和图的非负整数U的最小值．图GUnKl的下整和标号s称为排斥的(exclusive)，若

5、对每条边uvEE(G)当且仅当bu+vjeS＼V(G)．图G的排斥下整和数占7(G)是使得GUnKi有排斥下整和标号的非负整数n的最小值．从实用的观点来看，各种和图标号都可被计算机用作图的压缩表示．当利用它们来工作时，不仅可以节省内存，还可以加快某些图算法的运算速度．在本文的第一章中，我们主要介绍了一些文章中所涉及的概念，术语，符号；第二章介绍了棱柱EIl(n≥3)、残棱柱E：(il≥3)、残皇冠C：。Kl(n≥3)、梯子山东帅范大学硕十学位论文L。(n≥2)、梯子细分图L：(n≥2)的概念，并给出了1邑们的排斥(整，下

6、整)和数：第三章给出了三毛虫树，星毛虫树，广义双星，广义毛虫的概念，并证明了这几类特殊的树是整和图．我们主要得到如下结果．定理2．1设n为大于等于3的自然数，则s(E)25．定理2．2设n为大于等于3的自然数，则f7(E：)=4．定理2．3设n为大于等于3的自然数，则s(qoKl)23．定理2．4Ln(n≥2)是下整和图．定理2．5设n为大于1的自然数，则占’(匕)=1．定理2．6设n为大于1的自然数，则s(‘)23．定理2．7设n为大于1的自然数，则￡7(t)=2．定理3．1三毛虫树是整和图．定理3．2偶星毛虫树是整和

7、图．定理3．3广义双星是整和图．定理3．4广义毛虫是整和图．关键词：(排斥，下整，整)和图：(排斥，下整，整)和数：(排斥，下整，整)和标号；(残)棱柱；残皇冠；梯子；整和树．分类号：0157．5山东师范大学硕士学位论文The(exclusive，exclusiveintegral，lowerintegral)sumnumbersofseveralkindsofgraphXiulianGaoShandongNormalUniversity,Jinan，Shandong，250014People’sRepublicofCh

8、inaABSTRACTAllgraphconsideredinthispaperarefinite，simpleandundirected．Wefollowingeneralthegraph-theoreticnotationandterminologyof[1】Hararyt21presentedtheconcep