资源描述：
《C6的排斥下整和数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、的排斥下整和数高秀莲（德州学院数学系,山东德州,,253023）摘要：下整和标号与排斥下整和标号是图的新的压缩表示．一个图G称为下整和图,若它同构于某个SQ+的下整和图.本文证明了的排斥下整和数是2.关键词：；下整和数；下整和标号；下整和图中图分类号：O157.5文中所用图论基本术语与符号遵循文献[1].1990年Harary[2]提出和图的概念；1994年Harary[3]提出整和图的概念.令N(Z)表示正整数(整数)集，N(Z)的非空有限子集S的和(整和)图G+(S)是图其中(S,E)，其中u
2、v∈E当且仅当u+v∈S.一个图G称为和(整和)图,若它同构于某个SN(Z)的和(整和)图.即S给出了G的一个和(整和)标号,并且将顶点与其标号不加区分.G的和数(整和数)（）是使得G∪nK1是和图(整和图)的非负整数n的最小值.2003年Miller[4]等人提出了排斥图的概念.图G∪nK1的(整)和标号S称为排斥的(exclusive)，若对每条边E(G),u+v∈SV(G).如果G∪nK1的任意边的两端点（标号）之和都是孤立点，则G称为排斥图；图G的排斥（整）和数（）是使得G∪nK1有排斥
3、(整)和标号的非负整数n的最小值.显然对任意的图G有≤≤；≤≤.从实用的观点来看,各种和图标号都可用作图的压缩表示，即表示图的数据结构.当利用输入图的压缩表示来工作时,数据压缩不仅可以节省内存,还可以加快某些图算法的运算速度.近年来和图理论发展很快，可参见文献[5][6][7].2004年李敏[8]提出下整和图的概念.用表示不超过实数的最大整数(称为的下整数),Q+表示正有理数集.Q+的非空有限子集S的下整和图G+(S)是图(S,E),其中uv∈E当且仅当∈S.一个图G称为下整和图,若它同构于某个
4、SQ+的下整和图.我们说S给出G的一个下整和标号,并且顶点与标号不加区分.下整和数'(G)是使得G∪nK1是下整和图的非负整数n的最小值.下整和标号是图的新的压缩表示.引理[8]下整和图G若包含作为其导出子图，则工作点数大于1.定理 的排斥下整和数是2．即证明 一方面由引理知.4另一方面设A=｛,,｝,B＝｛，,｝,V(C6)=A∪B，C={,}E()={,,,,,}，S=V()∪C=A∪B∪C．给出∪2K1的一组标号,（其中为充分大的正整数）下面验证所给标号为∪2K1的一个排斥下整和标号．1）显
5、然S中元素互异2）验证任意边和的下整数属于S： 3）验证任意不相邻顶点标号之和下整数不属于S：显然 因此，只需验证任意不相邻顶点标号之和下整数不等于,即可．4(1)A∪B中的元素：（2）A∪B中的元素与C中的元素之间：显然与A∪B间无边相连;（3）显然C间无边相连.综上所述此标号确为∪2K1的一个排斥下整和标号．即.有以上两个方面可知参考文献[1]J.A.Bondy,U.S.R.Murty.GraphTheorywithApplications[M].NewYork,MacmillanLondon
6、andElsevier,1976.[2]F.Harary.Sumgraphsanddifferencegraphs[J].Congr.Numer,1990,72:101—108.[3]F.Harary.Sumgraphsoveralltheintegers[J].DiscreteMath.,1994,124:99—105.[4]M.Miller,J.Ryan,etal.Exclusivesumgraphlabeling[J].DiscreteMath.,preprint,2003.[5]王海棠.和
7、图论与分数图论的若干结果[D].济南:山东师范大学,2005.[6]Z.Chen.Integralsumgraphsfromidentification[J].DiscreteMath,1998,181:77－90.4[7]王海英.几类图的(整,模)和数[D].济南:山东师范大学,2004.[8]李敏.下整和图与排斥下整和图［D］.济南:山东师范大学,2006.TheexclusivelowerintegralsumnumberofgraphXiulianGAO(DepartmentofMathe
8、matics，DezhouUniversity,DezhouShandong253023,China)Abstract:Lowerintegralsumlabelingandexclusivelowerintegralsumlabelingareanotherwaysusedascompressedrepresentationofagraph．AgraphGissaidtobeanlowerintegralsumgraphifitisisomorphictothelowerinte
