| 【中文题名】 | 图的L（d，1）-标号的边跨度 |
| 【英文题名】 | The Edge Span of L(d,1)-labeling on Some Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-6-11 |
| 【中关键词】 | 频道分配问题,L（2,1）-标号,标号着色数,边跨度,弦图 |
| 【英关键词】 | channel assignment problem,L（2,1）—labeling,L（2,1）—labelling number,the edge span,choral graph,the unit interval graph,r-path,the triangular lattice,the square lattice,the hexagon lattice,the wheel W_n, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 图G的标号着色L(2，1)-labeling是一个从顶点集V(G)到非负整数集的函数f，满足条件：(1)|f(u)-f(v)|≥2，若uv∈E(G)；(2)|f(u)-f(v)|≥1，若d(u，v)=2．将所有正常L(2，1)-标号的集合记作￡(2，1)，图G的标号着色数定义为：λ(G)=min max{f(v)∶v∈V(G)}，即使图G所有正常的L(2，1)-标号的最大标号达到最小值。我们可以将这个概念推广到一般的情形L(d，1)-标号和L(s，t)-标号，相应的标号着色数分别记为λ_d(G)和λ_((s，t))(G)。图的标号着色问题来自所谓的频道分配模型：不同的电台要使用无线频道发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资源。
本文主要研究该标号的另外一个参数，即边跨度，记做β(G)=min max{|f(u)-f(v)||uv∈v(G)}，其中f∈￡(2，1)，即在所有的正常L(2，1)-标号中，使得相邻顶点的标号之差最大值达到最小值。同样我们可以求出L(d，... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-8 |
|
第一章 引言 |
8-12 |
|
1.1 标号着色的背景及定义 |
8-9 |
|
1.2 图的L(d，1)-labeling |
9-10 |
|
1.3 图标号着色的跨度和边跨度 |
10 |
|
1.4 图论的基本符号与概念 |
10-12 |
|
第二章 关于边跨度的基本结论 |
12-18 |
|
2.1 关于圈的边跨度 |
12-14 |
|
2.2 关于树和k部完全图的边跨度 |
14-18 |
|
第三章 正则网格图的边跨度 |
18-24 |
|
3.1 正则网格的定义及基本结论 |
18 |
|
3.2 正三角形网格的边跨度 |
18-20 |
|
3.3 正四边形网格的边跨度 |
20-21 |
|
3.4 正六边形网格的边跨度 |
21-24 |
|
第四章 轮W_n的边跨度 |
24-32 |
|
4.1 轮的定义以及基本结论 |
24 |
|
4.2 关于轮L(2，1)-标号的边跨度 |
24-29 |
|
4.3 关于轮L(d，1)-标号的边跨度 |
29-32 |
|
第五章 路的强积图与弦图的边跨度 |
32-40 |
|
5.1 关于路的强积图L(2，1)-标号的边跨度 |
32-36 |
|
5.2 弦图的L(d，1)-标号以及相应的边跨度 |
36-40 |
|
致谢 |
40-41 |
|
参考文献 |
41-42 |
|
| 【DOI】 | LunWen.ID:2.2008.11802 |
