（运筹学与控制论专业论文）图的距离二边标号问题.pdf

图的距离二边标号问题 博士生姓名：吴建专指导教师：潘平奇教授 ( 东南大学数学系，南京，2 1 0 0 9 6 ) 摘要 在图的经典的顶点着色( 或边着色) 中，我们只要求任意两个相邻顶点( 或相邻边) 所着颜色不相同如果还要求距离为二的顶点( 或距离为二的边) 所着颜色也不相同， 我们就得到图的距离二着色( 或强边着色) 图的距离二着色实际上就是原图的平方图的 顶点着色平方图的顶点着色很早就有研究，而直到上个世纪九十年代初才出现一些图 的强边着色的研究结果经典的顶点着色和边着色已经有非常丰富的理论结果，其应用 的领域也很广泛最近二十年来，关于图的距离二着色问题和强边着色问题的研究结果 也不断涌现作为经典着色问题的推广，距离二着色问题和强边着色问题研究进一步拓 广了着色理论的实际应用范围比如，g e b r e m e d h i n 、m a n n e 和p o t t h e n 在文【2 9 】中 综述了距离二着色问题和一种强边着色问题在导数计算中的应用。 设歹和k 是两个非负整数，通常假定歹k 图的l ( j ，七) 标号是距离二着色的一 个直接推广，它最早是在1 9 9 2 年由g r i g g s 和y e h 【3 8 】为了解决一种特殊的频道分配问 题而提出的它作为经典着色的一个重要推广，得到了广泛深入的研究在图的l ( j ，七) 一 标号中，我们用非负整数对图的顶点进行标号使得相邻顶点的标号之间的差至少为j 而 距离为二的顶点的标号之间的差至少为k 一个图的所有l ( j ，惫) 一标号中最大标号的最 小值称为该图的l ( j ，) 一标号数图的圆l ( j ，后) 一标号是l ( j ，忌) 一标号的一个变形，它用 一个周长为整数的圆上的整点对图的顶点进行标号，要求相邻顶点的标号在圆上的距离 至少为j 而距离为二的顶点的标号在圆上的距离至少为毙使得图有圆一l ( j ，惫) 一标号的 最小圆的周长称为图的圆一l ( j ，忌) 一标号数。我们可以类似地定义图的l ( j ，尼) 一边标号数 和圆一l ( j ，尼) 一边标号数本论文重点研究图的强边着色( 即图的l ( 1 ，1 ) 一边标号) 、图的 l ( 2 ，1 ) 一边标号和图的圆l ( 2 ，1 ) 一边标号 论文首先研究图的强边着色，证明除了一个仅六个顶点的特殊图外，对任意图g ， 如果对图g 的任一条边z 剪都有d ( x ) + d ( y ) 5 ，那么它的强边色数不超过6 因为完 全二部图鲍。3 满足上述条件且其强边色数为6 ，所以上界6 是最好可能的。这个结果回 答了f a u d r e e 等人 2 2 】提出的第四个问题，事实上我们不要求g 是二部图，所以这个结 论比问题要求的更强该结果推进了强边色数上界的研究，有重要的理论意义我们还 设计了一个算法，它可以在线性时间内对满足上述定理条件的图给出它的一个6 一强边着 色该算法具有潜在的应用价值 g e o r g e s 和m a u r o 在文 3 3 】中完全确定了无穷一正则树的l ( 2 ，1 ) 一边标号数。接着 对任意正整数，我们确定了无穷一正则树的圆l ( 2 ，1 ) 一边标号数设佗2 是一正 整数，q n 表示n 一维立方体g e o r g e s 和m a u r o 在文【3 3 】中研究了当扎较小时q n 的 l ( 2 ，1 ) 一边标号数我们充分利用q 死的结构特征和圆标号的循环性质确定了q 2 、q 3 、 q 4 和q 5 的圆一l ( 2 ，1 ) 。边标号数以及q 5 的l ( 2 ，1 ) 一边标号数我们在利用圆一l ( 2 ，1 ) 边标号数确定l ( 2 ，1 ) 边标号数这方面作了有益的尝试，有望使用这一手段确定更多的 图的l ( 2 ，1 ) 标号数 网格图的研究是一项很有意义的工作本论文最后集中研究三种无穷网格图的l ( 2 ，1 ) 一 边标号、圆l ( 2 ，1 ) 边标号和强边着色分别用r 6 、r 4 和r 3 表示无穷六边形、四边形 和三角形网格图我们证明了r 6 的强边色数为6 ，l ( 2 ，1 ) 一边标号数为7 ，圆- l ( 2 ，1 ) - 边标号数为8 用r 。口尸n 表示两条路r ；和r 的笛卡尔乘积图我们又得到了一些情 况下p 竹；口r 的l ( 2 ，1 ) 一边标号数和圆一l ( 2 ，1 ) 一边标号数，同时还证明了n 的l ( 2 ，1 ) 一 边标号等于9 或者等于1 0 ，而它的圆一l ( 2 ，1 ) 一边标号数等于1 1 或者等于1 2 最后我 们确定了r 3 和两条无穷路的强乘积图的强边色数，证明了r 3 的l ( 2 ，1 ) 一边标号数等于 1 5 或者等于1 6 ，而它的圆一l ( 2 ，1 ) 一边标号数介于1 6 和1 8 之间，同时也得到了两条无 穷路的强乘积图l ( 2 ，1 ) 一边标号数和圆一l ( 2 ，1 ) 一边标号数的上下界。 关键词：点色数、边色数、强边色数、l ( j ，后) 一标号数、l ( j ，忌) 一边标号数、圆一l ( j ，是) 一 标号数、圆一l ( j ，忌) 边标号数、线图、平方图、无穷正则树、伽维立方体、三角形网格 图、四边形网格图、六边形网格图、笛卡尔乘积图、强乘积图 di s ta n c et w oe d g el a b e l i n go fg r a p h s a b s t r a c t t h ec l a s s i c a lv e r t e xc o l o r i n g ( e d g ec o l o r i n g ) o fag r a p hi sa na s s i g n m e n to fc o l o r s t oi t sv e r t i c e ss u c ht h a ta d j a c e n tv e r t i c e s ( a d j a c e n te d g e s ) r e c e i v ed i f f e r e n tc o l o r s 。i f ，i n a d d i t i o n ，o n ed e m a n d st h a tv e r t i c e s ( e d g e s ) a td i s t a n c et w om u s ta l s or e c e i v ed i f f e r e n t c o l o r s ，t h e no n eg e tt h ed i s t a n c et w oc o l o r i n g ( t h es t r o n ge d g ec o l o r i n g ) o fg r a p h s a d i s t a n c et w oc o l o r i n go fag r a p hi sa c t u a l l yav e r t e xc o l o r i n go ft h es q u a r eo ft h eg r a p h c o l o r i n gt h es q u a r eo fg r a p h si sa no l dt o p i ci ng r a p hc o l o r i n gp r o b l e m s ，w h i l et h es t r o n g e d g ec o l o r i n go fag r a p hw a sf i r s ti n v e s t i g a t e di n1 9 9 0 t h e r ea r eal a r g ea m o u n to fr e s u l t s c o n c e r n i n gt h ec l a s s i c a lv e r t e xa n de d g ec o l o r i n g so fg r a p h s ，a n dt h eg r a p hc o l o r i n gt h e o r y h a v em a n ya p p l i c a t i o n si np r a c t i c ea n di no t h e rs u b j e c t s i nr e c e n t2 0y e a r s ，m a n yp a p e r s i n v e s t i g a t i n gt h ed i s t a n c et w oc o l o r i n ga n ds t r o n ge d g ec o l o r i n ga n dt h e i rg e n e r a l i z a t i o n s h a v eb e e np u b l i s h e d t h e s eg e n e r a l i z a t i o n sa l s oh a v em a n ya p p l i c a t i o n si np r a c t i c a l p r o b l e m s f o re x a m p l e ，g e b r e m e d h i n ，m a n n ea n dp o t t h e ni n2 0 0 5p u b l i s h e das u r v e y 【2 9 】o nt h ea p p l i c a t i o n so fd i s t a n c et w oc o l o r i n g si nc o m p u t i n gd e r i v a t i v e s 。 l e tja n dkb et w on o n n e g a t i v ei n t e g e r sw i t hj k t h el ( j ，后) 一l a b e l i n go fag r a p h i sak i n do fg e n e r a l i z e dd i s t a n c et w oc o l o r i n g ，w h i c hw a sp r o p o s e db yg r i g g sa n dy e h 3 8 】 i n1 9 9 2i no r d e rt om o d e las p e c i a lk i n do fc h a n n e la s s i g n m e n tp r o b l e m a sa ni m p o r t a n t g e n e r a l i z a t i o no fc l a s s i c a lg r a p hc o l o r i n g ，i th a sa t t r a c t e dal o to fa t t e n t i o n sf r o mm a n y r e s e a r c h e s i na nl ( j ，惫) 一l a b e l i n go fag r a p h ，v e r t i c e sa r ea s s i g n e dn o n n e g a t i v ei n t e g e r s ， c a l l e dl a b e l s ，a n da d j a c e n tv e r t i c e sm u s tr e c e i v el a b e l st h a ta r ea tl e a s t 歹a p a r t ，a n d d i s t a n c et w ov e r t i c e sm u s tr e c e i v el a b e l st h a ta r ea tl e a s tka p a r t t h ec i r c u l a r - l ( j ，纠一 l a b e l i n gi sav a r i a t i o no fl ( j ，七) 一l a b e l i n gi nw h i c hl a b e l so fv e r t i c e sa r ei n t e g e rp o i n t s o nac i r c l eo fi n t e g r a lc i r c u m f e r e n c e ，a d ja c e n tv e r t i c e sa r ea s s i g n e dp o i n t st h a ta r ea t d i s t a n c ea tl e a s tjo nt h ec i r c l ea n dd i s t a n c et w ov e r t i c e sa r ea s s i g n e dl a b e l st h a ta r ea t d i s t a n c ea tl e a s tko nt h ec i r c l e t h ec i r c u m f e r e n c eo ft h em i n i m u mc i r c l es u c ht h a tt h e g r a p hh a sac i r c u l a r - l ( j ，后) 一l a b e l i n gi sd e f i n e da st h ec i r c u l a r l ( j ，尼) 一l a b e l i n gn u m b e ro f t h eg r a p h s i m i l a r l y , o n ec a nd e f i n et h el ( j ，惫) 一e d g e l a b e l i n gn u m b e r ，t h ec i r c u l a r l ( j ，尼) 一 e d g e l a b e l i n gn u m b e ro fg r a p h s t h i st h e s i sm a i n l yf o c u so nt h es t r o n ge d g ec o l o r i n g ( i e t h el ( 1 ，1 ) 一e d g e l a b e l i n g ，t h el ( 2 ，1 ) 一e d g e l a b e l i n g ，t h ec i r c u l a r l ( 2 ，1 ) 一l a b e l i n go fg r a p h s 1 1 1 f i r s t l y ，w ei n v e s t i g a t et h es t r o n ge d g ec o l o r i n g so fg r a p h s i ti sp r o v e dt h a tf o ra n y g r a p h ，e x c e p to n es p e c i a lg r a p hw i t hs i xv e r t i c e s ，i fd ( x ) + d ( y ) 5f o ra n ye d g ex y ， t h e nt h es t r o n ge d g ec h r o m a t i cn u m b e ro ft h eg r a p hi sl e s st h a no re q u a lt o6 s i n c ek 2 ，3 s a t i s f i e st h ea b o v ec o n d i t i o na n dh a ss t r o n ge d g ec h r o m a t i cn u m b e r6 ，t h eu p p e rb o u n d 6i st h eb e s tp o s s i b l e t h i sr e s u l ta n s w e r st h ef o u r t hq u e s t i o np r o p o s e db yf a u d r e ee t a 1 i n 【2 2 a c t u a l l yo u rr e s u l ti ss t r o n g e rt h a nt h eo n ea s k e db yt h eq u e s t i o ns i n c ew e d r o pt h er e q u i r e m e n tt h a tt h eg r a p hi sb i p a r t i t e t h i sr e s u l ti st h e o r e t i c a l l ys i g n i f i c a n t ， w h i c hp r o m o t e st h er e s e a r c ho ft h eu p p e rb o u n d sf o rs t r o n gc h r o m a t i ci n d e xo fg r a p h s a na l g o r i t h mi sa l s og i v e nt oc o n s t r u c ta6 - s t r o n ge d g ec o l o r i n go fag i v e ng r a p hs a t i s f y i n g t h ea b o v ec o n d i t i o n t h i sa l g o r i t h mh a sp o t e n t i a la p p l i c a t i o n si np r a c t i c e w et h e nt u r nt ot h ec i r c u l a r - l ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ro fg r a p h s l e ta ( 2 ) b ea n yp o s i t i v ei n t e g e r g e o r g e sa n dm a u r o 【3 3 】c o m p l e t e l yd e t e r m i n e dt h el ( 2 ，1 ) - e d g e 一 ， l a b e l i n gn u m b e r so ft h ea r e g u l a rt r e e s w ed e t e r m i n et h ec i r c u l a r l ( 2 ，1 ) 一e d g e - l a b e l i n g n u m b e r so ft h ea r e g u l a rt r e e si nt h ep a p e r l e t 佗( 2 ) b ea ni n t e g e r d e n o t eb yq ，。t h e n - d i m e n s i o n a lc u b e g e o r g e sa n dm a u r o 3 3 】s t u d i e dt h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ro f q 凡f o rs m a l ln b ys u f f i c i e n t l ym a k i n gt h eu s eo fi n f o r m a t i o no ft h es t r u c t u r eo fq na n d t h ec y c l i cp r o p e r t i e so ft h ec i r c u l a r - l ( 2 ，1 ) 一e d g e l a b e l i n g ，t h ec i r c u l a r - l ( 2 ，1 ) 一e d g e l a b e l i n g n u m b e r so fq nf o r 佗= 2 ，3 ，4 ，5a n da sac o n s e q u e n c et h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r so f q 5a r ed e t e r m i n e d t h i sg i v e sa ne x a m p l et od e t e r m i n et h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r o fag r a p ht h r o u g hi t sc i r c u l a r l ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r t h i sm e t h o dc a nb eu s e dt o d e t e r m i n et h el ( 2 ，1 ) 一e d g e - l a b e l i n gn u m b e r so fs o m eo t h e rg r a p h s f i n a l l y ，w ef o c u so nl a t t i c e s l a t t i c e sa r ei m p o r t a n ts t r u c t u r e si np r a t i c e d e n o t eb y r 6 ，f 4a n df 3t h eh e x a g o n a l ，t h es q u a r e ，a n dt h et r i a n g u l a rl a t t i c e s w ep r o v et h a tt h e s t r o n ge d g ec h r o m a t i cn u m b e ro ff 6i s6 ， t h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ro fr 6i s7a n d t h ec i r c u l a r l ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r so ff 6i s8 l e t 焉口rd e n o t et h ec a r t e s i a n p r o d u c to ft w op a t hp ma n dr w eo b t a i n ss o m ep a r t i a lr e s u l t so nt h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r sa n dc i r c u l a r l ( 2 ，1 ) 一e d g e - l a b e l i n gn u m b e r so f 口ra n dp r o v e st h a t t h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ro ff 4i se q u a lt o9o r1 0a n dt h ec i r c u l a r l ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e r so ff 4i s1 1o r12 w ea l s oo b t a i nt h es t r o n ge d g ec h r o m a t i cn u m b e r so f f 3a n dt h es t r o n gp r o d u c to ft w oi n f i n i t ep a t h sa sw e l la st h eu p p e ra n dl o w e rb o u n d sf o r t h el ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ra n dt h ec i r c u l a r l ( 2 ，1 ) 一e d g e l a b e l i n gn u m b e ro ff 3a n d l v t h es t r o n gp r o d u c to ft w oi n f i n i t ep a t h s k e y w o r d s ：c h r o m a t i cn u m b e r ，e d g ec h r o m a t i cn u m b e r ，s t r o n ge d g ec h r o m a t i c n u m b e r ，l ( j ，) 一l a b e l i n gn u m b e r ，c i r c u l a r - l ( j ，惫) 一l a b e l i n gn u m b e r ，l ( j ，惫) 。e d g e - l a b e l i n g n u m b e r ，c i r c u l a r - l ( j ，尼) 一e d g e l a b e l i n gn u m b e r ，l i n eg r a p h ，s q u a r eo fag r a p h ，a r e g u l a r t r e e ，n - d i m e n s i o n a lc u b e ，t r i a n g u l a rl a t t i c e ，s q u a r el a t t i c e ，h e x a g o n a ll a t t i c e ，c a r t e s i a n p r o d u c t ，s t r o n gp r o d u c t v 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 研究生签名：城专日期： 潮、二，弓d 东南大学学位论文使用授权声明 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印，缩印或其他复制手段保存论文本人电子文档的内 容和纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究 生院办理。 研究生签名：灏专导师签名： 第一章综述 1 1引言 优化问题分为连续优化和离散优化两大类随着科学技术的不断发展，尤其是计算 机科学的迅猛发展，在生产实践和理论研究过程中出现了大量的离散结构，使离散优化 问题的研究变得越来越重要离散优化是应用数学和理论计算科学的一个重要分支 图的着色问题是离散优化问题的一个重要的研究领域现实世界中的很多问题可以 归结为图上的不同类型的着色问题这也是着色问题成为图论的一个核心问题的重要原 因然而很遗憾的是图的着色问题通常都是很困难的问题比如判断一个图是否是3 一可 着色的问题是一个n p 完全问题f 7 5 】要想通过求解着色问题得到实际问题的最优解， 通常只有对那些很小规模的问题才是可能的由于没有有效的算法，对于规模稍大的问 题，我们都要付出巨大的计算代价或者牺牲解的最优性这也意味着图的着色问题通常 没有多项式时间算法。 由于实际应用的需要，我们不可避免地遇到大量的着色问题如何寻求着色问题的 最优解是一个摆在我们面前的非常现实的问题一个特定的应用问题通常都归结为定义 在某个特殊图类上的特定的着色问题尽管那些着色问题对一般的图而言是困难的，然 而对某些特殊的图类，我们还是有希望找到多项式时间算法，或者好的近似算法，甚至 可以确定它们的最优解或者最优解的好的上下界 本论文研究一些特殊图类上的特殊的边着色问题。我们将确定它们的色数，或者给 出色数的上下界，或者给出一个有一定保证的设计巧妙的着色方法( 或算法) 这将是非 常有理论及实际意义的工作 1 2着色和距离二标号的背景、基本概念和结论 图的着色问题最初源于四色问题，是图论中的一个十分重要的研究方向这里我们 首先给出点着色的定义 。 定义1 2 1 给定图g = ( ve ) 和一个正整数k ，设是从g 的顶点集v ( c ) 到颜色集 1 ，2 ，毙) 的映射，即：v ( g ) - 1 ，2 ，南) 若对图g 的任意两个相邻顶点v l 和 口2 ，都有( 钉1 ) ( u 2 ) 则称是图g 的一个正常的k 一着色图g 的点色数x ( g ) ， 1 2东南大学博士学位论文 定义为图g 的所有正常k 一着色中最小的k 即 x ( v ) = m i n k ：g 有正常的k 一着色) 从点着色的定义可以看出，图g 的一个正常k 一着色实际上是将图g 的顶点集划分 成k 个子集合，每个子集合中的顶点着相同的颜色，我们称之为一个颜色族着相同颜 色的顶点构成独立集点着色中有一些重要的定理 定理1 2 1 ( b r o o k s ，1 9 4 1 ) i s 对任意连通图g ，有x ( a ) ( g ) + 1 等号成立的 充要条件是g 是奇圈或者完全图这里的a ( a ) 是图g 的最大度 同样地，我们给出边着色的定义 定义1 2 2 给定图g = ( ve ) ，k 是一给定的正整数，设是从g 的边集合e ( c ) 到 颜色集 l ，2 ，七) 的映射，即：e ( g ) _ 1 ，2 ，后) 若对图g 的任意两条相邻的 边e 1 和e 2 ，都有( e 1 ) ( e 2 ) 则称是图g 的一个正常的k 边着色图g 的边色 数x 7 ( g ) ，定义为图g 的正常k 一边着色中最小的k 即 x 7 ( g ) = m i n k ：g 有正常的k 一边着色) 从边着色的定义可以看出，图g 的一个正常的k 一边着色是将图g 的边集合划分成 k 个边子集合每个边子集合中的边着相同的颜色，我们称之为一个颜色族着相同颜 色的边构成一个匹配v i z i n g 定理是边着色中的一个重要定理 定理1 2 2 ( v i z i n g ，1 9 6 4 ) 刀对于任意简单图g ，有( g ) ) ( 7 ( g ) ( g ) + 1 这里的( g ) 是图g 的最大度 ， 。 对于简单图g ，如果x 7 ( g ) = ( g ) ，则称g 是第一类的；如果x ( g ) = ( g ) + 1 ， 则称g 是第二类的 一 自从点着色和边着色的概念提出来以后，随着科学技术的进一步发展，产生了各种 各样的着色问题例如l ( j ，后) 一标号问题就是其中的一种 假定某地区有若干电台，每个电台都要使用某个频道发射信号为了避免干扰，当 两电台之间的距离小于给定的数值时，它们必须使用不同的频道为了节省资源，我们 尽量少使用频道这一问题可转化为图的点着色问题将每个电台看作图的顶点，当两 电台之间的距离小于给定的数值时，两个顶点之间连一条边，这样就形成一个图g ，而 图g 的点色数x ( a ) 就是我们所要求的最少的频道数 第一章综述 3 在实际应用过程中，上述的模型往往过于简化，通常我们需要同时考虑距离以及频 道之间的差异当两电台之间的距离银近时，我们希望频道之间的差值较大当两 电台之间的距离较近”时，我们也希望使用不同的频道这就是通常所说的频道分配 问题针对频道分配问题，自然就提出了距离二标号问题， g r i g g s 和y e h 3 s 】于1 9 9 2 年首次提出z ( 2 ，1 ) 一标号问题三( 2 ，1 ) 一标号问题可以很 好地模拟频道分配问题频道分配问题的研究参见 2 8 ，4 1 ，4 9 】同样我们将每个电台看 作图的顶点，当两电台之间的距离小于一给定的数值时，两个顶点之间连一条边，这样 就形成一个图g 如果两电台所对应的两个顶点之间距离为一，我们认为两电台之间的 距离银近”此时希望这两电台所使用的频道之差的绝对值至少为二如果两电台所 对应的两个顶点之间距离为二，我们认为两电台之间的距离“较近 ，此时希望这两电 台所使用的频道不同图g 的l ( 2 ，1 ) 标号数，就是我们所需要的最小的频道跨度一 般地我们有下面的定义 定义1 2 3 给定图g = ( ke ) 和两个正整数j ，k ，这里歹免设是从g 的顶点集 v ( v ) 到非负整数标号集的映射对于图g 的任意两顶点t ，1 和沈，如果d ( v 1 ，u 2 ) 4 - - 1 ， 那么就有i ( 口1 ) 一( 2 ) i j ；如果d ( v l ，v 2 ) = 2 ，那么就有i ( 钞) 一( 2 ) i 后，则 称是图g 的一个l ( j ，忌) 一标号图g 的一个l ( j ，忌) 一标号的跨度s p a n ( l ) 是指这 个l ( j ，惫) 标号中最大的标号值图g 的l ( j ，惫) 一标号数( _ 也称其为图g - 的，七一数) ， 沁，k ( g ) ，定义为图g 的所有l ( j ，七) 一标号中最小的跨度，即 a 歹，七( g ) = m i n s p a n ( l ) ：l 是g 的l ( j ，忌) 一标号， l ( 2 ，1 ) 一标号是l ( j ，忌) 一标号的一个特殊情形。目前有很多学者关注和研究l ( j ，忌) 一标 号问题有关l ( j ，后) 一标号问题的结果请参见 9 ，1 1 ，3 0 ，3 2 ，3 5 ，4 6 ，7 2 ，8 2 ，8 3 】关于l ( 2 ，1 ) 一 标号问题，已经有很多的结果g r i g g s 和y e h 在文 3 8 】中确定了所有路和圈的a 2 ，1 一数， 对任意最大度为的树t 他们证明了+ 1 a 2 , 1 ( t ) s + 2 。设n 是一个正整数， 我们用q n 表示伽维立方体，他们证明了a 2 ，1 ( q 1 ) = 2 ，a 2 ，1 ( q 2 ) = 4 ，a 2 ，1 ( q 3 ) = 6 ， a 2 ，1 ( q 4 ) = 7 ，a 2 ，1 ( q 5 ) = 8 ，仃+ 3 a 2 ，i ( q n ) 2 n + 1 ( 仃5 ) g r i g g s 和y e h 【3 8 】给出了下面的猜想； 猜想1 ：对任意最大度为a 的图g ，a 2 ，1 ( 6 ) a 2 g r i g g s 和y e h 证明了对任意最大度为a 的图g ，入2 。1 ( 6 ) a 2 + 2 a 他们证明 4东南大学博士学位论文 了猜想对直径为2 的图是成立的，同时还给出了两类图它们的a 2 1 一数等于2 一因 为圈的a 2 , 1 一数等于a 2 = 4 ，p e t e r s e n 图的a 2 1 - 数等于a 2 = 9 ，所以这个猜想如果成 立，那么这个上界是最好可能的( 至少当a = 2 ，3 时是如此) 关于l ( z ，1 ) 一标号问题的复杂性，g r i g g s 和y e h 【3 8 】证明了对一个直径为2 的图判 断它的a 2 1 - 数是否小于等于它的顶点数的问题是一个n p 完全问题他们还猜想对任 意一颗树t ，判断它的入2 ，1 - 数是否小于等于( t ) + 1 的问题也是一个n p 一完全问题 g r i g g s 和y e h 的这篇种子文章首先提出了l ( 2 ，1 ) 一标号问题，从几个不同的侧面对 该问题进行了深入的研究，提出了一个很重要的猜想，并指出了进一步研究的方向这 个问题引起了许多学者的注意，此后的十多年里，相关的研究结果不断呈现_ 后继的结 果中的很大一部分都可以在g r i g g s 和y e h 的这篇种子文章中找到它们的起点 一 w h i t t l e s e y 等人在文【8 0 】中研究n 一维立方体的a 2 1 - 数，得到了改进的上界，根据 该文的结果我们有a 2 ，1 ( q 6 ) 1 0 ，根据g r i g g s 和y e h 的下界我们有a 2 ，l ( q 6 ) 9 。从而 9 曼入2 ，l ( q 6 ) 1 0 尽管q 6 并不是一个很大的图，然而要确定入2 ，l ( q 6 ) 是否等于9 却是 一件非常困难的事情，至今未见到有文献给出该问题的定论注意到犯一维立方体实际上 是佗条路恳的笛卡尔乘积，w h i t t l e s e y 等人同时还研究了礼条不同长度的路的笛卡尔 乘积的a 2 ，l 一数此后有不少作者开始研究乘积图的a 2 ，l 一数、入d ，1 一数、，七一数，这些乘 积图包括笛卡尔乘积、直积、复合图等，请参见文献【1 9 ，3 4 ，4 4 ，4 5 ，4 7 ，5 0 - 5 2 ，5 4 - 5 7 ，8 0 1 w h i t t l e s e y 等人在文【8 0 1 中还对一个图g 的剖分图g s ( 即将图g 的每一条边用一 条长度为2 的路替换后得到的图) 的a 2 1 - 数进行研究，这一研究成为点边l ( j ，七) 一全标 号问题研究的起点，关于点边l ( j ，忌) 全标号问题研究请参见文献( 7 ，1 7 ，6 3 】 距离二标号问题的一个研究重点是设法证明猜想1 g r i g g s 和y e h 证明了对任意最 大度为的图g ，a 2 ，i ( 6 ) a 2 + 2 a 这个上界被c h a n g 和k u o 【1 2 】改进为a 2 ，l ( g ) s 2 + a k r d l 和s k r e k o v s k i 【5 3 】研究列表频道分配问题得到一个b r o o k s - 型定理，作为 这个定理的一个简单推论c h a n g 和k u o 的上界被改进了1 ，即a 2 ，l ( g ) 2 + a 一1 该上界随后又被g o n a l v e s 【2 6 】改进为a 2 , 1 ( g ) a 2 + a 一2 迄今为止还没有关于这 个上界更加实质性的改进即使是要证明猜想1 在a = 3 时成立也相当困难一些作者 开始证明对某些特殊的图类猜想1 是成立的，比如c h e n 和l i n 【1 4 】证明了猜想1 对所 有线图是成立的 一 关于距离二标号问题的复杂性，g r i g g s 和y e h 3 8 】猜想判断一颗树的a 2 ，1 一数是否 等于+ 1 的问题是一个n p 一完全问题，但c h a n g 和k u o 在文【1 2 】中证明了它是一个 p 一问题，并给出了解决该问题的一个多形式时间算法，从而否定了g r i g g s 和y e h 的猜 第一章综述 想设s 是一个正整数，f i a l a ，k l o k s 和k r a t o c h v l ( 【2 4 】) 证明了判断一个图的a 2 1 - 数是否不超过8 。当8 4 时是n p 一完全问题，当8 3 时是p 一问题求解一个直径 为2 的图的a 2 l - 数( 【3 8 ，8 1 】) 、求解一个平面图的a 2 ，1 一数( 【5 ，2 5 】) 、求解一个二部图 和弦图的入2 ，1 - 数( f 5 】) 等都是n p 一困难的问题 c h a n g 和k u o ( 【1 2 】) 证明了存在计算c o g r a p h 的a 2 ，1 一数的线性时间算法w a n g 等( 【7 9 】) 证明了二部图的单射入2 ，1 一数( 即所有单射l ( 2 ，1 ) 一标号的最小跨度) 可多项 式时间计算设k 2 为j 幻在其某个顶点上增加一个环而得到的图肛( g ) 表示图g 的 m y c i e l s k i 图，g 口鲍表示g 和鲍的笛卡尔乘积图l i n 和l a m ( 【5 5 】) 证明了对任 意图g ，p ( g ) 和g o k 2 的a 2 ，l - 数和单射a 2 1 - 数都是多形式时间可计算的；一一 1 3 圆- l ( j ，尼) 一标号问题 1 9 9 8 年，h e u v e l 等人在文 4 0 】中提出圆l ( j ，尼) 一标号的概念设m - ，j 和k 都是非负 整数且歹k 图g 的一个m 一圆一l ( j ，忌) 一标号是指从图g 的顶点集到 o ，1 ，m 一1 】 的一映射，对任意两个顶点让和口，如果让移e ( g ) ，那么i f ( u ) 一y ( v ) l m j ； 如果如( u ，口) - - - - 2 ，那么i 厂( u ) 一，( u ) l m k 这里i 口i m = m i n a ，m 一口) 图g 的圆 一l ( j ，尼) 一标号数定义为g 的所有m - 圆一l ( j ，尼) 一标号中最小的m ，记为a t ，七( g ) 我们 有时称图g 的圆一l ( j ，老) 一标号数为图g 的f ，k 一数 图g 的，。圹数和a ，七一数之间的关系是： ，七( g ) + 1 乃，七( g ) ，k ( a ) + 歹 在知道a 七( g ) 的情况下要得到乃，k ( a ) 的值一般并不是一件容易的事情。反之，当吧，k ( a ) 的值已经知道时我们也不能轻易地得到a k ( a ) 的值当j = 2 ，k = l 时，a 2 ，l ( g ) + 1 0 2 ，l ( a ) a 2 ，1 ( g ) + 2 ，即0 2 ，1 ( g ) 等于久2 ，l ( a ) + l 或者a 2 ，l ( a ) + 2 ，但要确定0 2 ；1 ( g ) 的值一般并不容易 知道0 5 ，七( g ) 的值在理论和应用上都有它的意义比如我们可以利用图g 的圆 l ( j ，恕) 一标号轻易地给出图g 的一个阶