关于某些图的L(2,1)标号毕业论文

1、本 科 毕 业 论 文题目关于某些图的l(2,1)-标号 作 者： xx 专 业： 信息与计算科学 指导教师： xxx 完成日期： 2011年5月20日 原 创 性 声 明本人声明：所呈交的论文是本人在导师指导下进行的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名： 日 期： 本论文使用授权说明本人完全了解xx大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。（保密的论文在解密后应遵

2、守此规定）学生签名： 指导教师签名： 日期： xx大学毕业论文立题卡课题名称关于某些图的l(2,1)-标号出题人xxx课题表述（简述课题的背景、目的、意义、主要内容、完成课题的条件、成果形式等） 图着色是图论研究的主题之一。在无线电通信波段分配的促动下，有了图的距离2着色这一迷人的推广概念l(h,k)-标号。对l(h,k)-标号,已有大量的图类弦图、直径2的图、乘积图等等，均被研究过,或确定h,k-数或确定h,k-数的界，当然也有许多待解决的问题。图的距离2着色问题是无线电通信波段分配问题的图论模式，有着很大的探讨空间，它的研究成果对波段分配问题起着推进作用。本课题主要研究一类特殊构成图如类似

3、手镯的图的l(2,1)-标号。完成课题的条件是学习图着色，查阅相关资料特别是英文资料。 成果形式：论文课题来源其他课题类别毕业论文该课题对学生的要求 有一定的图论基础和英文阅读能力教研室意见 教研室主任签名：_ _年_月_日学院意见同意立题（）不同意立题（） 教学院长签名：_ _年_月_日注：1、此表一式三份，学院、教研室、学生档案各一份。 2、课题来源是指：1.科研，2.社会生产实际，3. 其他。3、课题类别是指：1.毕业论文，2.毕业设计。4、教研室意见：在组织专业指导委员会审核后，就该课题的工作量大小，难易程度及是否符合专业培养目标和要求等内容提出具体的意见和建议。5、学院可根据专业特点

4、，可对该表格进行适当的修改。xx 大 学毕业论文任务书题目 关于某些图的l(2,1)-标号 学生姓名 xx 学 院 理学院 专 业 信息与计算科学 班 级 信计071 学 号 xxxxxxx 起讫日期 2010年12月16日至5月31日 指导教师 xxx 职称 讲师 发任务书日期 2010 年 12 月 16 日课题的内容和要求（研究内容、研究目标和解决的关键问题）研究内容：（1）考察已有的图的距离2标号的结果和方法；（2）整理已读文献结果，寻求方法,解决问题；（3）给出方法并确定选定图如类似手镯的图的l(2,1)标号数。目标和要求： 问题的探求可通过分析选定图的结构特点,给出最好标号的方法,

5、确定选定图的l(2,1)标号数。课题的研究方法和技术路线(1)查阅二十世纪七十年代以来国际有关图的距离2标号的文献和资料; (2)分析已有的标号方法；(3)提出好的标号方法；(4)通过给出标号确定上界，再结合图结构特点，试图确定下界，以达到最后确定选定图的l(2,1)标号数。基础条件要有一定的图论基础，并具有一定分析能力和文献检索能力，可以通过互联网查阅到相关的资料以及一些最新的成果，学校图书馆有比较丰富的图书资料。参考文献1 g.j. chang and d. kuo, the l(2,1)-labelling problem on graphsj, siam j. discrete mat

6、h. 9(1996), 309-316.2 j.p. georges and d.w. mauro, generalized vertex labelings with a condition at distance twoj, congr. numer. 109(1995), 141-159.3 j.p. georges and d.w. mauro, some results on j,k-numbers of the products of complete graphsj, congr. numer. 140 (1999), 141-160.4 j.p. georges and d.w

7、. mauro, labeling trees with a condition at distance twoj, discrete math. 269 (2003), 127-148.5 j.p. georges, d.w. mauro, and m.i. stein, labeling products of complete graphs with a condition at distance twoj, siam j. discrete math. 14 (2000), 28-35.6 j.p. georges, d.w. mauro, and m. a. whittlesey,

8、relating path coverings to vertex labellings with a condition at distance twoj, discrete math. 135 (1994), 103-111.7 j.r. griggs and r.k. yeh, labelling graphs with a condition at distance 2j, siam j. discrete math. 5 (1992), 586-595.8 j. heuvwl, r. a. leese, and m.a. shepherd, graph labeling and ra

9、dio channel assignmentj, j. graph theory 29 (1998), 263-283.9 p.k. jha, a. narayanan, p. sood, k. sundaram and v. sunder, on l(2,1)-labelling of the cartesian product of a cycle and a pathj, ars combinatoria 55 (2000), 81-89.10 s. klavvzar and a. vesel, computing invariants on rotagraphs using dynam

10、ic algorithm approach: the case of (2,1)-colorings and independence numbersj, discrete appl. math. 129 (2003), 449-460.11 d. kuo and j. yan, on l(2,1)-labelings of cartesian products of paths and cyclesj, discrete math. 283(2004), 137-144.12 d. sakai, labelling chordal graphs: distance two condition

11、, siam j. discrete math. 7 (1994), 133-140.13 c. schwarzand and d. sakai troxell, l(2,1)-labelings of products of two cyclesj, dimacs technical report 2003-33 (2003).14 m.a. whittlesey, j.p. georges and d.w. mauro, on the-number of qn and related graphsj, siam j. discrete math. 8 (1995), 499-506.本课题

12、必须完成的任务：(1) 分析已有的标号;(2) 给出方法并试着确定选定图的l(2,1)标号数。成果形式本课题的成果是论文进度计划起讫日期工作内容备 注10.11.18-10.3.9选题、查阅文献资料11.3.10-11.3.18开题报告11.3.19-11.3.25根据开题报告情况继续查阅文献资料11.3.26-11.4.1写出论文第一稿11.4.2-11.4.29指导老师批阅论文第一稿11.4.30-11.5.15修改论文，并定稿11.5.16-11.5.21指导教师评定成绩，评阅老师评阅论文，写出评阅意见。11.5.22-11.5.31答辩教研室审核意 见 该任务书的内容符合xx大学毕业设

13、计（论文）要求和本专业的培养目标，同意下发。 教研室主任签名： 年 月 日学院意见 教学院长签名： 年 月 日xx大学本科生毕业论文开题报告学生姓名xx学 号xxxxxxx专业信息与计算科学课题名称关于某些图的l(2,1)-标号阅读文献情 况国内文献 8篇开题日期2011年3月18日国外文献 8篇 篇开题地点xx7号楼119室一 文献综述与调研报告：（阐述课题研究的现状及发展趋势，本课题研究的意义和价值、参考文献） 研究价值： 图着色是图论研究的主题之一。在无线电通信波段分配的促动下，有了图的距离2着色这一迷人的推广概念。古典的点着色问题中，仅对相邻点限制条件，即相邻点着色不同；图的距离2着色

14、则要求更强的条件- 给定图中相邻点着色及距离2的两点着色都限制条件。因为无线电通信波段分配问题中，要求使每个发射台分配的波段相互无干扰且波段有效利用。对l(h,k)-标号,已有大量的图类弦图、直径2的图、乘积图、mobius带等等，均被研究过,或确定h,k-数或确定h,k-数的界，当然也有许多待解决的问题。本课题主要研究手镯型图的l(2,1)-标号。总之，图的距离2着色问题是无线电通信波段分配问题的图论模式，有着很大的探讨空间，它的研究成果对波段分配问题起着推进作用。参考文献:1 g.j. chang and d. kuo, the l(2,1)-labelling problem on gr

15、aphsj, siam j. discrete math. 9(1996), 309-316.2 j.p. georges and d.w. mauro, generalized vertex labelings with a condition at distance twoj, congr. numer. 109(1995), 141-159.3 j.p. georges and d.w. mauro, some results on j,k-numbers of the products of complete graphsj, congr. numer. 140 (1999), 141

16、-160.4 j.p. georges and d.w. mauro, labeling trees with a condition at distance twoj, discrete math. 269 (2003), 127-148.5 j.p. georges, d.w. mauro, and m.i. stein, labeling products of complete graphs with a condition at distance twoj, siam j. discrete math. 14 (2000), 28-35.6 j.p. georges, d.w. ma

17、uro, and m. a. whittlesey, relating path coverings to vertex labellings with a condition at distance twoj, discrete math. 135 (1994), 103-111.7 j.r. griggs and r.k. yeh, labelling graphs with a condition at distance 2j, siam j. discrete math. 5 (1992), 586-595.8 p.k. jha, a. narayanan, p. sood, k. s

18、undaram and v. sunder, on l(2,1)-labelling of the cartesian product of a cycle and a pathj, ars combinatoria 55 (2000), 81-89.二 本课题的基本内容，预计解决的难题研究内容：（1）考察已有的图的距离2标号的结果和方法；（2）整理已读文献结果，寻求方法,解决问题；（3）给出方法并确定选定图如类似手镯的图的l(2,1)标号数。目标和要求： 问题的探求可通过分析选定图的结构特点,给出最好标号的方法,试着确定选定图的l(2,1)标号数。三 课题的研究方法、技术路线(1)查阅二十世

19、纪七十年代以来国际有关图的距离2标号的文献和资料; (2)分析已有的标号方法；(3)提出好的标号方法；(4) 通过给出标号确定上界，再结合图结构特点，试图确定下界，以确定选定图的l(2,1)标号数。四 研究工作条件和基础内在因素：在大学四年里，有了一定的图论基础，并具有一定分析能力和文献检索能力，可以通过互联网查阅到相关的资料以及一些最新的成果。外在因素：现代网络便利的搜索系统为我们提供了重要的信息资源,充分利用学校图书馆大量文献资料。同时老师的精心指导也是完成此教学设计的重要保证.五、进度计划起讫日期工作内容11.3.18-11.3.25分析整理已读文献结果11.3.26-11.4.1寻求方

20、法,解决问题，完成外文翻译11.4.2-11.4.29整理研究结果,定论文初稿11.4.30-11.5.15修改论文,解决残留问题,完善论文11.5.16-11.5.21定稿,打印论文11.5.22-11.5.31答辩论文阶段完成日期文献调研完成日期论文实验完成日期撰写论文完成日期评议答辩完成日期指导教师评语该生已经查阅相关文献，同意开题。 导师签名： 年 月 日教研室意见 教研室主任签名： 年 月 日学院意见通过开题（）开题不通过（） 教学院长签名： 年 月 日注：1、学院可根据专业特点，可对该表格进行适当的修改。xx 大 学毕 业 论 文题目： 关于某些图的l(2,1)-标号 姓 名：xx

21、指导教师：xxx专 业： 信息与计算科学xx大学理学院2011年5月摘 要图的一个-标号就是从顶点集到非负整数集的一个函数，使得时,有；当时，有，其中,是图的顶点。不妨设最小标号为。那么，图的-标号数是是的所有-标号下的跨度的最小数。本文给出了两个定义拟梯子和手镯图，并完全确定了拟梯子和手镯图的-标号数。关键词： -标号，-标号数，拟梯子，手镯图abstractan -labeling of a graph is a function f from the vertex set to the set of all nonnegative integers such that if ， and

22、if . without loss of generality, we let the least label be 0. the-labeling number ofis the smallest number over the spans of all -labelings of .in this paper, we define the similarity- ladder and the bracelet graph ,and completely determine their-labeling number.key words: -labeling, -labeling numbe

23、r, similarity-ladder, bracelet graph目 录摘 要iabstractii第一章 引 言11.1标号的定义与背景11.2拟梯子和手镯图的定义21.3本文的主要工作3第二章 拟梯子的l(2,1)-标号42.1 t=3,4的拟梯子的l(2,1)-标号数42.2 4t17的拟梯子的l(2,1)-标号数10第三章 手镯图的l(2,1)-标号113.1 t=3,4的手镯图的l(2,1)-标号数113.2 4t17的手镯图的l(2,1)-标号数16参考文献17致 谢19第一章 引 言1.1标号的定义与背景 图着色是图论研究的主题之一。在无线电通信波段分配的促动下，有了图的距

24、离2着色这一迷人的推广概念。古典的点着色问题中，仅对相邻点限制条件，即相邻点着色不同；图的距离2着色则要求更强的条件 给定图中的相邻点着色及距离2的两点着色都限制条件。因为无线电通信波段分配问题中，要求使每个发射台分配的波段相互无干扰且波段有效利用。griggs和robert 4在这个现实问题的基础上提出了图的-标号这个概念。l(2,1)-标号问题就是将各个频率（非负整数）分配到各个电台，使得“接近”的电台必须接收不同的频率，而“十分接近” 的电台则必须接收至少相差2的频率。在图论中具体表述这个问题，简单图的一个-标号就是从顶点集到非负整数集的一个函数，使得时,有；当时，有，其中,是图的顶点。

25、不防设最小标号为。那么，图的-标号数是是的所有-标号下的跨度的最小数。-标号问题就是要找出图的-标号数。在过去的十多年里，-标号问题一直被广泛研究，很多图形的-标号结果已经得到(见13，57)，特别是关于路和圈的cartesian积图的-标号数已基本全部得到确定(见1，2)。后来，在许多论文中标号的推广概念标号得到了进一步探讨，(见810)。对-标号,已有大量的图类弦图、直径2的图、cartesian积图、mbius梯子等等8,19-21，均被研究过,或确定-数或确定-数的界，当然也有许多待解决的问题。在文献10-18对图的边-路替换图的-标号数研究。梯子即两条路和的cartesian积图，本

26、文首先首先研究由梯子推广得到的拟梯子的-标号问题，进而研究拟梯子基础上得到的一条路和一个圈的cartesian积图的推广图手镯图的-标号问题。1.2拟梯子和手镯图的定义定义1.1：圈设为无向标定图，中顶点与边的交替序列cn=vi0ej1vi1ej2ejnv in称为到的通路，其中vir-1,vir为的端点，（r=1,2,n）,vi0 , vin分别称为cn的始点和终点，cn中边的条数称为它的长度。若cn的所有顶点各异，所有边也各异，但是vi0=vin，则称cn为圈。长度为奇数的圈称为奇圈。长度为偶数的圈称为偶圈。接下来我们由n个相同的t圈构造图。 首先我们设t圈或 , 为了表述方便，我们将圈c

27、ti的顶点分成顶点个数相同或相差一个顶点的上下两行(如图1)，即：当时，第一行顶点从左向右依次为：，第二行顶点从左向右依次为：.当时，第一行顶点从左向右依次为：，第二行顶点从左向右依次为：。 图1 圈cti定义1.2 ：将个相同的圈如下依次相接：当时，对，把点和重合，把点和重合，边和边重合；当时，对，把点和重合，把点和重合，边和边重合，所得的图称为拟梯子，用表示如图2所示： 图2 定义1.3 : 在拟梯子的基础上把拟梯子的两端如下重合：当时，将和重合，和重合，边和边重合；当时，将和重合，和重合，边和边重合，所得的图称为手镯图，我们用来表示。如图3所示：图3 1.3本文的主要工作 和的carte

28、sian积图及一条路和一个圈的cartesian积图的-标号问题在文献 8,20已有研究。本文主要研究这两个图的推广图拟梯子和手镯图的-标号问题。本文通过给出恰当的标号获得上界，通过反证法或图与子图的关系，获得下界，进而完全确定了拟梯子和手镯图的-标号数。本课题的主要难点在于获得下界，以最终获得标号数的确切值。因为拟梯子是手镯图的子图，故第二章是关于拟梯子的-标号数的研究，本章内容是我和陈亚娟共同研究完成，为了第三章证明的需要，部分定理证明不同。第三章是关于手镯图的-标号数的研究，这一部分由本人独立完成。第二章 拟梯子的l(2,1)-标号本章我们首先研究拟梯子的-标号。首先我们给出本章需要的引

29、理。引理2.17 设是最大度为的图，。引理2.27 设是最大度为的图，若包含三个度为的顶点，且其中的一个顶点与另外两个相邻，则。接下来我们对任意的t值给出拟梯子的l(2,1)-标号数的确切值。的拟梯子即最大度为的扇子图；的拟梯子即两条路的cartesian积图，其标号数结论已有20；对及4t17的拟梯子的l(2,1)-标号数，我们将通过循环标号法一起给出。2.1 t=3,4的拟梯子的l(2,1)-标号数定理2.1 ；当时，。证明：的拟梯子即最大度为的扇子图。由于包含两个度为的顶点，若, 则和只能标0或4,那么和只能标2,与定义矛盾。所以。又易见可以给出一个的跨度为5的-标号： 中心点标，扇弧上

30、的点依次标号为，所以。又引理2.1，。又对，可以给出一个跨度为5的-标号： 中心点标，扇弧上的点依次标号为4,2,5,3。对，可以给出一个跨度为5的-标号： 中心点标，扇弧上的点按照先偶后奇的顺序依次标号为2,4,6，3,5，。从而当时，。的拟梯子即两条路的cartesian积图，其标号数结论已有，即如下定理。定理2.2 20 。在下文中，为表达方便，当点的标号为时，我们用表示。2.2 4t4；当时，由引理2.1有，若最大标号为4，因为的点只能标 0或 4，因此，或者，。（1） 当，时，取2或者取3。当取2时，则无法取值；当取3时，=1，又，则无法取值；（2） 当，时，取1或者取2。当取1时，

31、又，则无法取值；当取2时，则无法取值。故，所以。其次，我们可以给出的跨度为5的-标号（如下，其中加下划线的标号表示度为3的点的标号，下同），所以。综上可知：。的拟梯子的跨度为5的-标号定理2.4 。证明：首先，若标号数为4，因为=3的点只能标 0或 4，因此坐标为和的点只能标2，与定义矛盾，所以。当时，由引理2.1有，若最大标号为4，因为=3的点只能标 0或 4,因此=0，=4或者=4，=0。（1） 当，时，或者，。当，时，又，则无法取值；当，时，又，则无法取值；（2） 当，时，由于此图上下对称，则同理可得无法取值。故。其次，我们可以给出的跨度为5的-标号（如下）。综上可知：。 的跨度为5的-

32、标号的拟梯子的跨度为5的-标号定理2.5 当时，；当时，。证明：首先,当类似于的证明，若标号数为4，则坐标和只能标2，与定义矛盾，同样可得。当时，由引理2.1，有又我们可以给出的跨度为4的-标号（如下），所以。 其次，我们可以给出)的跨度为5的-标号（如下），所以。综上可知：，。 的跨度为4的-标号 的拟梯子的跨度为5的-标号定理2.6 当，时，；当时，。证明：首先，当时，由引理2.1，有当时，4, 又我们可以给出的跨度为4的-标号（如下），所以。当时，有三个度为的顶点,且其中的一个顶点与另外两个相邻，故由引理2.2，当时，4。其次，我们可以给出跨度为5的的拟梯子的-标号（如下），所以。综上可

33、知： 当，时，；当，时，。的跨度为4的标号的跨度为4的-标号的跨度为4的-标号的跨度为4的标号的拟梯子的跨度为5的-标号的拟梯子的跨度为5的-标号的拟梯子的跨度为5的-标号的拟梯子的跨度为5的-标号定理2.7 。证明：首先，由引理2.2，可知。其次，我们可以给出跨度为4的的拟梯子的的-标号（如下），所以，。综上可知：。跨度为4的的拟梯子的的-标号定理2.8 当时，当时，。证明：首先 ，当时， 有三个度为的顶点，且其中的一个顶点与另外两个相邻，故由引理2.2有，；当时，由引理2.1有，又我们可以给出的跨度为4的-标号（如下），则，那么。其次，当n2时，我们可以给出跨度为5的的拟梯子的的-标号（如

34、下），所以。综上可知：当时，当时，。 的跨度为4的-标号的拟梯子的跨度为5的-标号定理2.9 当时，。证明：首先, 由引理2.1，当时，。其次，我们可以给出跨度为4的的拟梯子的-标号（如下），所以当时，。综上可知： 当时，。 的跨度为4的-标号 的跨度为4的-标号 的跨度为4的-标号的跨度为4的-标号2.3 t17的拟梯子的l(2,1)-标号数定理2.10 当时，。证明：首先,由引理2.1可知，。其次我们可以给出跨度为4的 的拟梯子的的-标号（如下）。又，则；而每个圈的上下行里都有一个由024组成的兼容组；则每个圈都能循环扩张下去，所以对，我们可以给出跨度为4的拟梯子的的-标号，所以。综上可知

35、：当时，。的跨度为4的-标号的跨度为4的-标号的跨度为4的-标号的跨度为4的-标号的跨度为4的-标号的跨度为4的-标号第三章 手镯图的l(2,1)-标号 本章我们将进一步研究在拟梯子基础上形成的手镯图的-标号。首先我们给出本章需要的一个引理。引理3.11 。若, 则有。由于,从而由引理3.1得到的一个下界，即 。接下来我们对任意的t值给出的确切值。t=3,4的手镯图的l(2,1)-标号数的结果已有；类似于拟梯子的处理，对4t17的手镯图的l(2,1)-标号数，我们将通过循环标号法一起给出。3.1 t=3,4的手镯图的l(2,1)-标号数。的手镯图即轮 ，其标号数结论已有，即如下定理。定理3.1

36、 9 ；当时，。的手镯图即路和圈的cartesian积图，其标号数结论已有，即如下定理。定理3.219 。3.2 4t18的手镯图的l(2,1)-标号数定理3.3 当，3k+2且5时，；当或时，。证明：首先，因为，由引理3.1可知，。当时，不难发现，上一章中t=5拟梯子跨度为5的标号-同样可作为手镯图的-标号。所以，当时，。当且5时，我们可以给出跨度为5的的手镯图-标号（如下），综上可知：当，3k+2且5时，。当时，我们可以给出跨度为6的的手镯图的-标号（如下），所以。又假设标号数为5，则对任一标号数=0,1,2,3,4,5，至多可标3个顶点。用表示标的顶点个数，则3，且其中至多三个为3，要么

37、=3，要么=3，若如此的话，则无法给出其余点的标号。若中至多两个为3，则+3+3+2+2+2+2=14，这与图的顶点数15矛盾，从而且=5的手镯图标号数至少为6。当时，我们可以给出跨度为6的的手镯图-标号（如下），所以。假设标号数为5，则的手镯图中圈cn=1-02-03-0(n+1)-01-0的任一子图的标号可能为如下情形及他们的对称情形（这里的对称指的是a与5-a对称）或如下情形拼接，即0,1,2,3,4,5所有可能的路的-标号：02402，02403，02405，02413，02415，02502，02503，02504，02513，02514，025302，025304，025305，0

38、25314，025315；0314，0315，03502，03503，03504，03513，03514，035203，035204，035205，0352402，0352403，0352405，0352413，0352415；0413，0415，04203，04204，04205，042502，042503，042504，042513，042514，0425302，0425304，0425305，0425314，0425315；0513，0514，05203，05204，05205，052402，052403，052405，052413，052415，05302，05304，05305，05

39、314，05315；1302，1304，1305，13502，13503，13504，13513，13514，135203，135204，135205，1352402，1352403，1352405，1352413，1352415；1402，1403，1405，14203，14204，14205，142502，142503，142504，142513，142514，1425302，1425304，1425305，1425314，1425315；1502，1503，1504，15203，15204，15205，152402，152403，152405，152413，152415，15302，15

40、304，15305，15314，15315；2402，2403，2405，2413，2415；2502，2503，2504，2513，2514，25302，25304，25305，25314，25315；3502，3503，3504，3513，3514，35203，35204，35205，352402，352403，352405，352413，352415。以以上标号段为中心，对的手镯图进一步标号，其中只有如下的18个可作为圈cn=1-02-03-0(n+1)-01-0的子图的标号：02402，02503；03513，03514；0413， 04204；05204，05305，05315；13

41、513，13514；14204；15314，15315；2402；25314，25315，3513。其余的情形都在某点处无法取得标号不难发现，每段标号末尾两个数是另一段的开始两个数。而这些可作为cn=1-02-03-0(n+1)-01-0的子图的标号段，除了0413，2402，3513这三个长为4，其余长均5。，又因为2402后只和02402衔接，3513后只和13513衔接，如此循环下去，可得的循环标号分别为240240240和351351351，易见 cn=1-02-03-0(n+1)-01-0含2402和3513的标号段的标号，对应于圈长为的圈标号；且cn=1-02-03-0(n+1)-

42、01-0含0413的标号必为04135142 042042042，易见对应于圈长为的圈标号。而长全5的标号段可构成的标号只能对应于圈长为的圈标号。从而当时，用0,1,2,3,4,5给不出的手镯图的标号，从而该图的标号数至少为6。综上可知：当或时，。且5 的手镯图跨度为5的-标号n=5 的手镯图跨度为6的-标号定理3.4 当时，；当时，。证明：首先，因为，由引理3.1可知，。其次，我们可以给出跨度为5的且5的手镯图-标号（如下），所以。综上可知：当5时，。对且=5的手镯图，若标号数为5，则对任一标号数=0,1,2,3,4,5，至多可标4个顶点，用表示标的顶点个数，且设从大到小排为，则至多如下情形

43、之一：（1） =c=d=4，且e2，f2；（2） =c =4，且d4，e3，f3；（3）= 4，且c4，d4，e4，f3；（4）= 4，且4，c4，d4，e4，f4；（4）4，4，c4，d4，e4，f4。易见，+c+d+e+ f17的手镯图的l(2,1)-标号数定理3.10 当时，。证明：首先，当时，由引理3.1可知，；其次不难发现，上一章中的跨度为4的拟梯子标号同样可作为t17的手镯图的-标号。综上可知：当时，。本文主要研究了拟梯子和手镯图的-标号数。还可以进一步研究拟梯子和手镯图的-标号数，同样还可以研究圈和圈之间仅共一点形成的图的-标号数，这些将作为本课题的后续工作。参考文献1 g.j.

44、 chang and d. kuo, the l(2,1)-labelling problem on graphsj, stan j. dtscrete nath. 9(1996), 309-316.2 j.p. georges and d.w. nauro, generaltzed vertex labeltngs with a condition at distance twoj, congr. nuner. 109(1995), 141-159.3 j.p. georges and d.w. nauro, some results on j,k-nunbers of the produc

45、ts of complete graphsj, congr. nuner. 140 (1999), 141-160.4 f.s. robert,p rivate communication through j.griggs(1988)5 j.p. georges, d.w. nauro, and n.t. stein, labeling products of complete graphs with a condition at distance twoj, stan j. dtscrete nath. 14 (2000), 28-35.6 j.p. georges, d.w. nauro,

46、 and n. a. whtttlesey, relating path coverings to vertex labellings wtth a condition at distance twoj, discrete math. 135 (1994), 103-111.7 j.r. griggs and r.k. yeh, labelling graphs with a condition at distance 2j, stan j. discrete math. 5 (1992), 586-595.8 p.k. jha, a. narayanan, p. sood, k. sundaran and v. sunder, on l(2,1)-labelling of the cartestian product of a cycle and a pathj, ars conbtnatorta 55 (2000), 81-89.9 r.k. yeh. labeling graphs with a condition at distance t