（计算机应用技术专业论文）若干图的（d1）全标号和（21）标号的研究.pdf

大连理工大学硕士学位论文 摘要 图的标号问题起始于1 9 6 6 年a r o s a 的著名优美树猜想。一个图的顶点标号是图的 顶点集到整数集的映射，边标号是图的边集到整数集的映射。根据对映射的不同要求产 生了各种类型的标号问题。本文对( 吐1 ) 全标号、( 2 ，1 ) 标号进行了研究。 y e h 等人最先考虑( 2 ，1 ) 标号问题。( 2 ，1 ) 标号问题来自计算机网络里广播频道设置问 题。用非负的整数表示频道，让相近的位置接受不同的频道，并且非常近的位置为了不 相互干扰，它们的频道至少相差2 ( 吐1 ) 全标号是根据( 2 ，1 ) 标号衍变而来。 h a v e t 等人给出对于任意的，正则图g ，乃( g ) d + ，本文证明了对于任意，正 贝i j 非二部图g ，乃：，鸪( g ) d + ，+ 1 本文对广义p e t e r s e n 图、f l o w e rs n a r k 及其相关图和g l o d b e r gs n a r k 及其相关图的 ( 吐1 ) 全标号数进行了研究，得出如下结论： ( 1 ) 当刀是偶数，k 是奇数时，乃2 ( p ( 甩，后) ) = d + 3 ( 2 ) 当刀是奇数或k 是偶数时，乃，( p ( ，z ，后) ) = d + 4 ( 3 ) 当甩是偶数时，乃：( 日。) = 乃2 ：( g 。) = d + 3 ( 4 ) 当疗是奇数时，正( 日。) = 墨( g 。) = 5 ，乃西( h 。) = 乃出( g 。) = d + 4 ( 5 ) 钙( 瓯) = ( t g i ) = 5 ，乃：3 ( q ) = 乃西( 弼t ) = d + 4 对f l o w e rs n a r k 及其相关图的( 2 ，1 ) 标号数进行了研究，得出如下结论： ( 1 ) 当月 3 时，a ( 日。) = 2 ( g 。) = 6 ( 2 ) 当n = 3 时，a ( n 3 ) = 7 ，五( g 3 ) = 6 关键词：广义p e t e r s e n 图；f l o w e rs n a r k ；6 0 l d b e r gs n a r k ；全标号数 大连理工大学硕士学位论文 t h er e s e a r c ho n ( z1 ) 一l a b e l l i n ga n d ( 2 ，1 ) 一l a b e l l i n gi ns o m eg r a p h s a b s t r a c t g r a p hl a b e l l i n gt r a c e si t so r i g i nt ot h ef a m o u sc o n j e c t u r et h a ta l lt r e e sa r eg r a c e f u lp r e s e n t e db ya r o s ai n19 6 6 v e r t e x l a b e l l i n gi sam a p p m gt h a tm a p st h ev e r t e xs e ti n t oi n t e g e rs e t e d g el a b e l l i n gi sam a p p i n gt h a tm a p st h ee d g es e ti n t oi n t e g e rs e t a c c o r d i n gt ot h ed i f f e r e n t r e q u i r e m e n t sf o rt h em a p p i n g ，m a n yv a r i a t i o n so fg r a p hl a b e l l i n g sh a v eb e e ne v o l v e d i nt h i s p a p e r ，t w oc l a s s e so fg r a p hl a b e l l i n g s ： 1 ) 一t o t a ll a b e l l i n g ，( 2 ，1 ) 一l a b e l l i n ga r er e s e a r c h e d y e ha n dt h e ng r i g g sf i r s tc o n s i d e r ( 2 ，1 ) 一l a b e l l i n g ( 2 ，1 ) - l a b e l l i n gi sm o t i v a t e db yt h e r a d i oc h a n n e l sa s s i g n m e n tp r o b l e mi nc o m p u t e rn e t w o r k u s i n gn o n n e g a t i v ei n t e g e r st or e p r e s e n tc h a n n e l s ，s ot h a tc l o s el o c a t i o n sr e c e i v ed i f f e r e n tc h a n n e l s ，a n dc h a n n e l sf o rv e r yc l o s e l o c a t i o n sa l ea tl e a s tt w oa p a r ts u c ht h a tt h e s ec h a n n e l sw o u l dn o ti n t e r f e r e 、析t he a c ho t h e r ( 吐1 ) t o t a ll a b e l l i n gi sm o t i v a t e df r o m ( 2 ，1 ) l a b e l l i n g h a v e tp r o v e d 乃( g ) d + ，f o r ，- r e g u l a rg r a p h i nt h i sp a p e r ，w ep r o v et h a t 乃( g ) d + ，+ 1f o r r - r e g u l a rn o n b i p a r t i t eg r a p h 、访t hd 厂3 1 ) - t o t a ln u m b e r so f t h eg e n e r a l i z e dp e t e r s e ng r a p h s ，f l o w e rs n a r kg r a p h sa n di t sr e l - a t e dg r a p h sa n dg o l d b e r gs n a r kg r a p h sa n di t sr e l a t e dg r a p h sa r er e s e a r c h e di nt h i sp a p e r ，a n d w eo b t a i nt h ef o l l o w i n gr e s u l t s ： ( 1 ) f o re v e n 珂a n do d d 毛乃2 2 ( p ( n ，后) ) = d + 3 ( 2 ) f o ro d d 胛o re v e n 屯乃日( 尸( ，z ，七) ) = 洲 ( 3 ) f o r e v e nn ，乃2 ( h 。) = 乃2 2 ( g 。) = d + 3 ( 4 ) f o ro d d 船，z ( 日。) = 置( g 。) = 5 ，乃日( h 。) = 乃日( g 。) = d + 4 ( 5 ) 墨( g i ) = 礁( t g t ) = 5 ，乃日( g 女) = 乃：3 ( t g ) = d + 4 ( 2 ，1 ) 一l a b e l l i n gn u m b e r so ff l o w e rs n a r kg r a p h sa n di t sr e l a t e dg r a p h sa r er e s e a r c h e di n t l l i sp a p e r a n dw eo b t a i nt h ef o l l o w i n gc o n c l u s i o n s ： ( 1 ) f o rn 3 ，2 ( h 。) = 2 ( g 。) = 6 ( 2 ) f o rn = 3 ，2 ( h 。) = 7 ，旯( g 。) = 6 k e yw o r d s ：g e n e r a l i z e dp e r t e r s e ng r a p h s ；f l o w e rs n a r k ；g o l d b e r gs n a r k ；( 以1 ) - t o t a l n u m b e r 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：垄! 塑堕竺2 垒翅：多垒! ：2 塑圭坠塑盘 作者签名：i 盘坠里 日期：墨! ! 年旦月j l 日 大连理工大学硕上研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文王作的知识产权属于大连理王大学，允许论文被查阅和借阕。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题西：薹! 竭坠竺：2 叁盟兰竺! 竺：! l ! 查j 堕塑皇 作者签名： 导师签名： 日期： 曼：曼年生月! l 日 日期：至! 芝年旦月竺西 大连理工大学硕上学位论文 己i吉 _ jl 口 图论是研究某些事物及它们之间关系的学科。现实世界中的许多事物( 或对象) 能用 图表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论对这些问 题做出分析和判断。因此，图论在自然科学和社会科学的许多领域有着广泛的应用，同 时也是计算机科学的重要基础。 1 7 3 6 年，e u l e r 解决了k 6 n i g s b e r g 七桥问题，这是有文字记载的最早的图论研究文 献。因此，这一事件被大家认为是图论作为一门独立的学科出现的标志。1 8 4 7 年，k i r c h h o f f 为了解一类线性联立方程组而发展了树的理论。1 8 5 7 年，c a y l e y 在研究有机化学 领域的问题时，也研究了树的理论。在e u l e r 之后的二百年中，许多数学家各自独立地 研究了图论中的一些问题，但是其研究结果并没有形成一个较为完善的体系。由于图论 长期以来不是数学研究的主流领域，图论一直在缓慢地发展着。1 9 3 6 年，k 6 n i g 编写了 第一本图论专著，总结了图论二百年发展的主要成果。 近年来，图论在科学界非常活跃，原因有两条：一是现代生物技术和科学技术提出 越来越多的图论问题要求解决；二是计算机技术的迅猛发展，为图论及其算法的解决提 供了强大的计算与证明的手段，如1 9 7 6 年，美国伊利诺大学的a p p e l 与h a k e n 在k o c h 的协助下，用计算机证明了悬挂多年的四色猜想是正确的。 图论最吸引人的特色是它蕴含着大量强有力的思想、漂亮的图形和巧妙的论证。同 时，图论又是最接近群众生活，最易于向科学水准低的人民阐述的- - i - j 学科，即使是非 常困难的尚未解决的问题也易于表达。问题外表的简单朴素和本质上的难以解决，使每 个搞图论的人在图论问题面前都必须谨慎严肃地思考问题，常常是一个貌似简单的问 题，即使是幸运地得出证明，证明中包含的细节也十分繁琐，并且往往运用了极艰苦的 计算。 图论发展至今，已经积累了许多难题，至今仍找不到有效的算法去解决，如求图中 h a m i l t o n 回路、r a m s e y 问题、笼问题、图的支配问题、图的标号问题以及图的着色问 题等等。这些问题均属于n p - 完全问题。 图论中标号问题是图论中一个比较活跃的研究领域。 若下豳的憾1 ) 全标号和( 2 ，l 标号的研究 基本概念 本文中所考虑的图均为无逸环且无重边的简单有限无向图，其中未定义的术语请参 见h a r a r y 的图论( 李慰萱译) 哆徐俊明的图论及其应用1 2 1 , b o n d y 和m u r t y 的 ( ( g r a p ht h e o r yw i t ha p p l i c a t i o n ) ) 【3 l h a y n e s ，h e d e t n i 和s l a t e r 的( ( f u n d a m e n t a l so f d o m i n - a t i o ni ng r a p h s ) ) 豳和( ( d o m i n a t i o ni ng r a p h s ：a d v a n c e dt o p i c s ) ) d i 1 1 图 一个图g 定义为一个二元组( y ( g ) ，露( g ) ) ，简记作g = ( v ，西) 其中v ( g ) 是一个非 空集合，它的元素称作顶点( v e r t e x ) ，届( g ) 是v ( g ) v ( g ) 的一个子集，它的元素称作 j 2 ( e d g e ) ，我们用v ( g ) 和e ( g ) 表示图g 的顶点集和边集。如果矿( g ) 和e ( g ) 都是有限 集，则称图g 是有限图，否则称为无限图。 若每一对顶点对( v ，v ，) 是有序的，我靛称e ( g ) 中的边是有内边，图g 是有商图 ( d i r e c t e dg r a p h ) 。若每一对顶点对( 1 ，) 是无序的，我们称层( g ) 中的边是无向边，图g 是无向图( u n d i r e c t e dg r a p h ) 。 图g = ( 矿，e ) 的顶点个数叫做图的阶( o r d e r ) ，记作q 刊v ( g ) i 图的边数用 p 司露g ) | 来表示。 当p = 0 时的图称为空 ( e m p t yg r a p h ) ，记作 当p = l ，q = 0 时的图称为平凡图( t r i v i a lg r a p h ) 。 所有其它的图称为非平凡图。 ( 1 ) g2 ) s u b g r a p ho fg ( 3 ) s p a n n i n gs u b g r a p ho fg 图1 1 子图与生成子图 f i g 1 1s u b g r a p ha n ds p a n n i n gs u b g r a p h 大连理工大学硕士学位论文 1 2 子图与生成子图 已知图g = ( v ，e ) 和h = ( y ，e ) ，如果y 。( h ) 矿( g ) ，e ( 日) e ( g ) ，并且何中边 的重数不能超过g 中对应边的重数，则称h 是g 的子 ( s u b g r a p h ) ，记作h g 如果日是g 的子图，并且h g ，则称h 是g 的真 ( p r o p e rs u b g r a p h ) ，记作 hcg 已知图h 是g 的子图，并且y ( h ) = v ( g ) ，则称日是g 的生成子图( s p a n n i n g s u b g r a p h ) 如图1 1 所示。 1 3正则图 一条边的端点称作与这条边相关联的( i n c i d e n t ) ，与一条边相关联的两个顶点是邻接 的( a d j a c e n t ) 顶点1 ，的邻域集合是图g 中所有与1 ，相邻的顶点的集合，记作 ( v ) ，n ( v ) = ，iu v e ( g ) ) 与一个顶点v 相关联的边数叫做顶点的度( d e g r e e ) ，记作 a ( v ) 其中顶点度中的最大值称为图g 的最大度，记作a ( g ) 顶点度中的最小值称为图 g 的最小度，记作万( g ) 若d ( 1 ，) = 0 ，则称1 ，为孤立点( i s o l a t e dv e r t e x ) 若a ( v ) = l ，则称1 ，为悬挂点( p e n d a n t v e r t e x ) ，与悬挂点关联的边则称为悬挂边( p e n d a n te d g e ) 若图g 的各顶点的度相同，则称图g 为正则图，若任取v v ( g ) ，a ( v ) = ，则称图 g 为，正则图，称它的正则度为，如图1 2 所示的图为3 正则图。 图1 23 一正则图 f i g 1 2 3 - r e g u l a rg r a p h 1 4 二部图 - - - - 部 ( b i p a r t i t eg r a p h ) ：若图g 的顶点集可分为二个非空集合k ，圪，使得任一条 若干图的以1 ) 全标号和( 2 ，1 ) 标号的研究 边都有一个端点在k 中，另一个端点在砭中，而u 和内部分别均不存在边，则g 称 为二部图，记为g = ( ku ，e ) ，( k ，) 称为g 的一个划分。 完全二部i 蛩( c o m p l e t eb i p a r t i t eg r a p h ) ：在二部图g = ( ku ，e ) ，菪k 中的每个顶 点与k 中的每个顶点有边连接，则g 称为完全二部图。若lk m ，1 ，则记此完 全二部图为k 如图1 3 所示的图为k ：。完全二部图。 我们把m = l 时的完全二部图k 。称为星图。 图1 3 k 2 4 完全二部图 f i g 1 3k 2 4c o m p l e t eb i p a r t i t eg r a p h 图1 4 图g 和其补图g 。 f i g 1 4 t h eg r a p hga n di t sc o m p l e m e n tg r a p hg 。 1 5 完备图和补图 每一对不同顶点均有一条边相连的简单图叫做完备图( c o m p l e t eg r a p h 或完全图) 。疗 个顶点的完全图记作k 。 设简单图g = ( 矿，e ) ，巨= ( 材，v ) i “，“，1 ，v ) ，则称图h = ( y ，e e ) 为g 的补图 ( c o m p l e m e n tg r a p h ) ，记作h = g 。( 或g ) 如图1 4 所示。 大连理工大学硕士学经论文 1 s 图的闷构 设有两个图g 。和g ：，如果它们的顶点间有对应关系，并且在对应的两个顶点 连接的边也一一对应时，就称g l 和g 2 露构( i s o m o r p h i s m ) ，记作g l 袋g 2 。如图1 5 所示。 图1 5 g l 和其同构图g 2 f i g 1 5g r a p hqa n di t si s o m o r p h i s mg r a p hg 2 1 7 图的乘积 两个图g l 和g 2 的积g l g 2 是图g ，v = k 中的任意两个点摊= ( 掰l ，u 2 ) 和v = “，v 2 ) ，当嚣l = v 1 以及钍2 嘲fv 2 或u 2 = 屹以及豁i 神v l 时，u 和v 在g = g ixg 2 中邻接。 见图1 6 ，路径只和只的积。 图1 6 只和只的积 f i g 。1 6c a r t e s i a np r o d u c to f 最a n d 只 若t 图的 1 ) 全标号和( 2 ，1 ) 标号的研究 1 8 路径 图g = ( y ，e ) ，若由顶点v ，出发，经过一些顶点v 川，v p ：，v p ，v 朋，到达顶点 v ，则称顶点序列( ，。，v p l ，p 2 ，v 胛，v ) 为从顶点，到顶点v ji 僦( p a t h ) 项点v ， 分别叫做路径的起点和终点，路径中的边数称作路径的长度。 若一条路中v ，= 1 ，则称这样的路为回路。 若一条路中所有的边均不相同，则称这样的路为迹。 若一条路中顶点均不相同，则称作通路或道路。 除v ，= ，外，其余顶点均不相同的路，称为圈或闭通路。 在无向图中，若从顶点v ，到v ，有路径，则称顶点y ，与顶点v i 是连通的。若图g 中 任意一对顶点均是连通的，则称图g 是连i l 臣 ( c o n n e c t e dg r a p h ) 非连通图的极大连通 子图叫做连通分量。 若图g 中有圈，则g 中最短圈的长度称为g 的围长，记作g ( o ) g 中最长圈的长 度称为g 的周长，记作c ( g ) 对于g 中的两个项点u 与1 ，当存在联结甜与，的道路时，其中最短道路的长度称作 甜与v 之间的距离d ( u ，v ) 如果不存在联结u 与1 ，的道路，则d ( u ，) = 0 0 图g 中任意两点间最长的距离称作图g 的直径( d i a m e t e r ) ，记作d i a m ( g ) 每对不同项点之间均有一条边相连的简单图称为完全l 蛩( c o m p l e t eg r a p h ) 刀个顶点 的完全图记作k 1 9 树 一个连通的且无回路的图称为树。树中的顶点称为结点。 指定树中的一个结点为根结点，树中任一结点到根结点的距离称为该结点的层数。 对于第f 层的一个结点”，与其相邻接的第f + l 层的结点称为是结点u 的子结点，把没有 子结点的结点称为叶结点。 树中的根结点没有父结点，树中的一个父结点可以有多个子结点，而一个结点最多 只能有一个父结点。 连通图至少有一棵生成树。 树是一类简单、特殊的图，探讨图的问题，通常是先从树来进行的。 1 10 常见图和标记 c 。表示由 个顶点组成的圈。例如c ，表示三边形，c 。表示四边形，c ，表示五边形。 大连理工大学硕士学位论文 只表示由，2 个项点组成的道路，即从c 。上删掉任意一条边所得的图。 k 。表示由n 个顶点组成完全图，即由刀个顶点组成的所有顶点都相互邻接的图。 k m ：表示完全二部图，该图有p ，+ p ：个顶点，这些顶点被分到两个集合中，各个 集合分别包含p 。( p 。 o ) 和p ：( p 2 0 ) 个顶点，属于同一个集合中的顶点均不相互邻接， 属于不同集合中的顶点均相互邻接。 k 九附，几表示完全聊( m 1 ) 部图，该图共有a + p 2 + + p 。个顶点，这些顶点被 分到m 个集合中，各个集合分别包含p 。，p ：，p 。( p ， 0 ) 个顶点，属于同一个集合中的 顶点均不相互邻接，属于不同集合中的顶点均相互邻接。 k 正则图表示所有顶点度均为k 的图。 ( 七，g ) 图表示围长为g 的k 一正则图。 ( 七，g ) 笼是指( 七，g ) - 图中顶点数最少的图，它必须满足下面3 个条件： ( 1 ) 为k 正则图。 ( 2 ) 围长为g 。 ( 3 ) 在满足前两个条件的图中，为顶点数最少的图。 若t 图的 1 ) 全标号和( 2 ，1 ) 标号的研究 2 标号问题的研究现状 图的标号问题的作为图论中极为重要的内容，有着较好的应用价值和研究前景，它 的研究始于1 9 6 3 年g r i n g e l 提出的一个猜想【6 】和1 9 6 6 年a r o s a 的一篇论文【7 1 。 1 9 6 3 年g r i n g e l 提出如下猜想：设丁是给定的有甩个顶点，刀1 条边的树，那么由 k ，川可分解成2 门1 个树同构于z 一个图的顶点标号是图的顶点集到整数集的映射，边标号是图的边集到整数集的映 射。根据对映射的不同要求产生了各种类型的标号问题。 常见的标号问题有： ( 1 ) 优美标号。 ( 2 ) 调和标号。 ( 3 ) 超幻和标号。 ( 4 ) k - ( d 1 ，d 2 ) 标号。 2 1( 2 1 ) 标号的起源和发展 f r o b e r t s 提出了在多个地点之间有效分配无线电频道的问题：使用非负的整数代表 频道，相近的地点要分配不同的频道，非常近的地点的频道为了不相互干预必须间隔2 在各基站之间分配一个合适的频率而不相互干扰的问题可以抽象为依据各项点之 间距离的图的标号问题。 d l ，d ：是正整数，图g 的( 面，d ：) 标号是这样的映射f ：v ( g ) 专 0 ，1 ，k ) ，当图g 中的任意两顶点u 和1 ，的距离d ( u ，v ) = i ( i = l ，2 ) 时满足lf ( u ) 一f ( v ) i z 图g 的 ( d 。，d ：) 数九岛( g ) 是满足( d 。，d ：) 标号最小的k y e h 8 1 和g r i g g s 9 1 最先考虑( 2 ，1 ) 标号。随后有很多文章研究了( 4 ，吐) 标号。 从定义和从几篇文献【虬1 2 】里能够得到( d 。，d ：) 标号的基本结论： ( 1 ) 图日是图g 的子图，则九。，如( h ) 以，如( g ) ，d l d 2 ( 2 ) 图g 的最大度a 1 ，则乃1 ( g ) a + d 1 ( 3 ) 对任何图g 和任意的正整数c ，d l ，d ：，则钿，毗( g ) = c 九，d 2 ( g ) ( 4 ) 图g 至少含有一条边，则1 细九十l “，( g ) = 1 定理2 1 ( g r i g g s 和y e h 【9 】 ) ( 1 ) 如果图g 有n 个顶点，则如1 ( g ) a + z ( g ) 一2 大连理工大学硕士学位论文 ( 2 ) 对任何图g ，如1 ( g ) 2 + 2 ( 3 ) 任何直径为2 的图g ，如。( g ) 2 c h a n g 和k u o 将( 2 ) 里的上界改进到2 + a c h a n g 等人将( 2 ) 推广到以。( g ) ? + ( d 一1 ) a g r i g g s 和y e h 9 1 提出了下面猜想：对于任何图g ( ( g ) 2 ) ，五1 ( g ) 2 树丁的的研究： g r i g g s 禾 y e h 9 1 证明了如，l ( 丁) 是+ 1 或者+ 2 c h a n gk u o 给出了求如1 ( 丁) 的 算法。c h a n g 等人证明了a + d 一1 乃1 ( 丁) m i n a + 2 d 一2 ，2 a + d 一2 圈c 。的研究： g r i g g s 和y e h 9 1 给出了如1 ( c 。) = 4 g e o r g e s 和m a u r o 研究了所有d l d 2 1 的 i a , , a , ( c n ) 定理2 2 ( g e o r g e s 和m a u r o0 0 ) ( 1 ) 2 五面，吒( c 。) = 2 d l ， 刀3 ，刀是奇数， d l + 2 d 2 ，甩= 0m o d4 ， 2 a m ， r = 2m o d4r d l d 2 3 ， 吐+ 3 d 2 ，n = 2m o d4 且吐d 2 3 ( 2 ) 2 i2 d l ， 刀= 0m o d3 ， 兄d l ，d ：( c 。) = 4 d 2 ， ，2 = 5 ， 【d l + 2 d 2 ，其它 平面图的研究： b o d l a e n d e r t l 3 1 等人研究了平面图，给出了下面的一些结果： ( 1 ) 如果图g 是外平面图，则如。( g ) a + 8 ( 2 ) 如果图g 是含有三角面的外平面图，则如。( g ) a + 6 ( 3 ) 如果图g 是平面图，贝, t j4 1 ( g ) 3 a + 2 8 ( j o n a s 1 4 1 最先得到上界8 一1 3 ) ( 4 ) 如果图g 是含有三角面的平面图，则如。( g ) 3 a + 2 2 w a n g 和l i h t l 5 1 获得了如下的一些平面图的结果： 若t 图的 1 ) 全标号和( 2 ，1 ) 标号的研究 ( 1 ) 如果g ( g ) 7 ，乃，如( g ) ( 2 d 2 1 ) + 4 d 1 + 4 d 2 4 ( 2 ) 如果g ( o ) 6 ，乃，d ：( g ) ( 2 d 2 - 1 ) a + 6 d 1 + 1 2 d 2 - 9 ( 3 ) 如果g ( g ) 5 ，乃，以( g ) ( 2 d 2 一1 ) + 6 d l + 2 4 d 2 一1 5 乘积图的研究： 设p 是具有p ，个顶点的路径，f _ 1 ，2 ，以，2 2 p = 只b 只表示路径p 的 积，f _ l ，2 ，n ，门2 从 9 ，1 6 】我们有以下的结论： ( 1 ) 如果对每个f ，p ，3 ，且至少有两个不同的f ，p ，4 ，我们有五1 ( p ) = 2 n + 2 ( 2 ) 如果p 。= 2 ，p 胁一1 3 ，且至少有两不同的f ，p ，4 ，我们有如1 ( 尸) = 2 n + 1 ( 3 ) 假设对每个f ，p ，5 ，有：如果4 d 2 2 n ，2 d , ，矾( p ) = d l + ( 4 n - 2 ) d 2 和 如果d l d 2 2 n ，2 d 1 + 2 ( n - 1 ) d 2 2 d , 。西( p ) 2 d 1 + ( 2 n - 1 ) d 2 如果对全部的f 有p j = 2 ，则p = q g r i g g s 和y e h 9 1 已经给出如1 ( q ) 2 n + l ， j o n a s l l 4 1 给出n + 3 如1 ( q 。) 不久w h i t t l e s e y 0 6 1 等人将上界改进到2 刀更确切的，他们 得到的有： ( 1 ) 如，1 ( q 。) 2 一1 ，刀2 一七一l ；如，l ( q 2 t i 一1 ) 2 一1 ( 2 ) 1 q k ，五1 ( q ) 2 + 2 一9 “一2 ，n 2 一g ( 3 ) 刀2 时，如1 ( q ) 2 n ( 4 ) l i m 4 。，( q ) i n = 1 n - - l b a o 除了对路径积的a 进行了研究，对于全部的m ，刀，如，。( 巳只) 和如，( c 。c 。) 已经 被j h a t l 7 1 ，j h a 1 8 l 等人和k u o 和y a n 1 9 1 研究。c h i a n g 2 0 1 i 开究了对于d 2 的圈和路径积的 ( 吐1 ) 标号问题。g e o r g e s 和m a u r o 2 1 】，g e o r g e s1 2 2 1 等人和e r w i n 等人考虑了完全图积 的( 2 ，1 ) 标号问题。s h a o 和y e h 【2 4 1 研究了任意图的积的( 2 ，1 ) 标号问题。 其他一些类型图的积的( 2 ，1 ) 标号问题在文献 2 4 ，2 5 ，2 6 】能够找到。 2 2( d1 ) 全标号的起源和发展 定义2 3 ( z1 ) 全标号 图g 的( z1 ) 全标号是一个映射厂：yue - - 9 , 0 ，1 ，k ) ，满足下面三个条件： ( 1 ) v ( u ，1 ，) v 2 ：u v e = ，厂( “) f ( v ) ( 2 ) v ( u ，v ，w ) v 3 ：u v e ，u w e = ，f ( u v ) f ( u w ) ( 3 ) v ( u ，v ) v 2 ：w ej if ( u ) 一f ( u v ) i d 大连理工大学硕士学位论文 满足以上3 个要求的标号的最小的k 被称为( 吐1 ) 全标号数，用乃( g ) 来表示。 ( 吐1 ) 全标号来源于( z1 ) 标号的推广。最先由h a v e t 和y u 2 7 ，2 8 1 提出来。b a z z a r o 和 m o n t a s s i e r 2 9 1 证明了对于具有大围长的稠密平面图，乃( g ) + 2 d 一2 w a n g 和 c h e n t 3 0 1 给出了：对于外平面图g ，如果5 ，或者图g 是= 3 的2 连通图，或者图g 的a = 4 且不含有相邻三角形，则墨( g ) sa + 2 h a v e t 和y u 3 u 给出了完全图k 。的全标 号数的上界和下界且给出了挖正 d + 5 ，6 d 2 1 0 d + 4 的确定值乃( k 。) m o n t a s s i e r 和 r a s p a u d 3 2 1 证明了一个给定最大平均度的连通图的乃( g ) a + 2 d 一2 定理2 4 ( h a v e t 2 8 1 ) 图g 的最大度是，我们有： ( 1 ) 乃( g ) a + d - 1 ( 2 ) 如果g 是a 正则图，则乃( g ) a + d ( 3 ) 如果d a ，则乃( g ) + d ( 4 ) 乃( g ) z ( g ) + z ( g ) + d 一2 ( 5 ) 乃( g ) 2 a + d - 1 推论2 5 图g 是二部图，对于二部图来说，z ( g ) = a ，我们有： + d 一1 乃( g ) + d j 对于正则的二部图，且d a ，则乃( g ) = a + d 定理2 6 ( b a z z