(下整)和图的结构与几类图的(下整)和数

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:haoxiang123123123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文仅考虑有限无向简单图,所用图论符号及术语遵循文献[1]. 1990年,F.Harary[2]提出了和图,和数的概念,从而开始了对和图的研究. 1994年,F.Harary[3]又介绍了整和图,整和数的概念. 令V(G)表示图G的顶点集合,|S|表示集合S中元素的个数.令N(Z)表示正整数(整数)集,N(Z)的非空有限子集S的(整)和图G+(S)是图(S,E),其中uv∈E当且仅当u+v∈S.一个图G称为(整)和图,若它同构于某个S()N(Z)的(整)和图.图G的(整)和数σ(G)((G))是使得G∪nK1是(整)和图的非负整数n的最小值.一个连通图的最小度δ是其和数的下界,能达到此下界的图称之为δ-最优的. 模和图的概念是由Boland等人[4]提出的. 模和图是取S()Zm{0}且所有算术运算均取模m(≥|S|+1)的和图.一个图G的模和数ρ(G)是使得G∪ρK1是模和图的孤立点数ρ的最小值. 2004年,李敏[5]提出下整和图的概念.用Q+表示正有理数集.Q+的非空有限子集S的下整和图G+(S)是图(S,E),其中uv∈E当且仅当「u+v」∈S. 从实用的观点来看,各种和图标号都可用作表达图的数据结构,它们比用其他的方式输入图更能节省存储空间. 到目前为止,和图方面的研究已取得许多成果,给出了很多的一般性理论.现在研究的重点主要集中在两个方面:一方面是图的和数与它的图参数、图结构方面的联系;另一方面确定一些特殊图类的(模、整、下整)和数. 在本文的第一章中,我们主要介绍了文章中所涉及的一些概念、术语和符号以及前人关于和图的一些重要研究结果;在第二章中我们给出关于(下整)和图的一些结构性结果;第三章中,我们给出路、毛虫、皇冠、完全图不交并等一些特殊图类的下整和标号. 扇Fn是具有顶点集V={c,a1,a2,…,an}和边集E={ca1,ca2,…,can,a1a2,a2a3,…,an-1an}的图(V,E),每条边cai,i=1,…,n称为一条辐.在Fn∪σ’(Fn)的一个下整和标号中,如果「c+ai」∈V(Fn),则称cai为工作辐. 将一个圈Cm的n-个拷贝粘合于同一顶点所形成的图称之为风车.记作wnm(m≥3).中心粘合点记为c,第i个圈上其余各点分别记作ai,…,aim-1,且aim=c. 毛虫是这样的一棵树,去掉其叶子顶点(即1度顶点)后为一条路. 给定图G1,G2,设G1有n个顶点,则G1⊙G2表示这样的图:取G2的n个拷贝,且将G1的第i个点与G2的第i个拷贝的每个点连边所得的图.则Cn⊙K1(n≥3)称为皇冠. 树T被称作三路树(three-pathtree),如果它由具有一个公共端点的三条路组成.当它对应的三条路分别是Pm,Pn,Pt时,这样的树记作P(m,n,t),它相应的三条路分别记作:Pm=(a1,a2,…,am),Pn=(am,b2,b3,…,bn),Pt=(am,c2,c3,…,ct)其中am为它们的公共端点. 在本文中,我们主要得到如下定理.定理2.1.1设图G1,G2不同为和图,Li是Gi∪σ(Gi)K1的和标号,若存在n∈L2,使得n与maxL1互质,则σ(G1∪G2)≤σ(G1)+σ(G2)-1. 定理2.2.1风车wnm(m≠4,5)是δ-最优的. 定理2.3.1在Fn∪σ(Fn)K1(n≥5)的一个下整和标号中,至少存在一条辐是非工作的. 定理2.4.1设三路树P(m,n,t)(m,n,t>2)存在一组下整和标号,则最大整数标号必为一度点. 定理3.1.1路是下整和图. 定理3.2.1毛虫是下整和图. 定理3.3.1皇冠的下整和数为1. 定理3.4.1完全图Kn的不交并的下整和数为1,即σ(rKn)=1(n≥3,r≥2) 推论3.4.1σ’(Kn1∪Kn2∪…∪Knr)=1,这里ni≥3,r≥2,i=1,…r.
其他文献
期刊
本文通过对汝阳县广播电视总台大虎岭转播发射台防雷整改过程,从防雷整改工程的设计和规范的施工,运用全方位的防雷理念,从防直击雷电、感应雷电、雷电波侵入、等电位连接、地电
期刊
期刊
本文主要研究了两类Sobolev方程的非协调H-Galerkin混合有限元方法。 本文针对第一类方程在正则网格下给出了一个新单元的收敛性分析;针对第二类方程在各向异性网格下分析
期刊
设χ是ν,元集,A是X的某些子集(有序子集)的集合,A的元素叫做区组.如果X中任意点对(有序点对)至多出现在A的一个区组中,则称(X,A)为一个填充(有向填充).如果一个填充(有向填充)的区
在教育体制改革和深化的条件下,教学观念和方法等都发生了转变,在初中阶段实施教育过程中,不仅要向学生传授丰富的知识,还要将提升学生身心健康作为主要目标,进而确保学生获
学位
2004年10月28日至29日,山东省委党校在胜利油田组织召开企业党校工作座谈会,胜利石油管理局党委书记王立新、山东省委党校常务副校长李新泰作了讲话,省委党校副校长王士富主
拟差族是拟差集的一个直接推广.本文中通过多种构作方法构作出一些拟差族的无穷类.具体的,利用分圆类理论和weil定理,在GF(q)上构作出(q,3,1,q-1/2)一ADF‘和(q,4,1,4(q-1)/5)-ADF;借助