| 【中文题名】 | 具有完美匹配的三正则图的L（2，1）-标号和毛毛虫的最优标号问题 |
| 【英文题名】 | L(2, 1)-labeling of 3-regular Graphs with Perfect Matching and the Optimal Labeling of Caterpillar |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-13 |
| 【中关键词】 | L（2,1）-标号,频率分配问题,三正则图,广义Petersen图,不连续增长路 |
| 【英关键词】 | L（2,1）-labeling,Channel assignment problem,3-regular graph,Generalized Petersen graph,Increasing nonconsecutive path,Optimal labeling, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
图的标号问题是图的染色问题的推广，它在现实生活中有着广泛的应用。
本文讨论了图的两种标号问题：L(2，1)-标号和最优标号。给定一个无向图G，G的一个L(2，1)一标号是指从其顶点集V(G)到非负整数集{0，1，2，…}的一个映射f，满足：
这里d_G(u，v)表示u和v之间的距离，即u和v之间最短路的长度。若一个L(2，1)-标号中的所有标号都不超过整数k，则称之为k-L(2，1)-标号。图G的L(2，1)-标号数，记作λ(G)，是使得图G存在L(2，1)-标号的最小正整数k。Griggs和Yeh最早研究了L(2，1)-标号问题，他们考虑了λ(G)与X(G)，△(G)，|V(G)|之间的关系。他们得出结论：λ(G)≤△~2(G)+2△(G)。并猜想：当图G的最大度△(G)≥2时，都有λ(G)≤△~2(G)。本文中，我们定义了图的匹配和的概念，得到λ(G)的一个上界。把这个结果应用于一类特殊的三正则图G，我们得到λ(G)至多是9，这于Griggs和Yeh的猜想相符合。在这里，我们将证明这类特殊的三正则图除了Petersen图的λ(G)=9之外，其余图的λ(G)≤8。并猜想：除了Pet... |
| 【论文题纲】 |
|
论文摘要 |
6-8 |
|
ABSTRACT |
8-11 |
|
第一章 引言 |
11-17 |
|
§1.1 背景和基本概念 |
11-15 |
|
§1.2 主要的相关结果 |
15-17 |
|
第二章 一类具有完美匹配的三正则图的L(2,1)-标号 |
17-27 |
|
§2.1 引言 |
17-19 |
|
§2.2 主要结论 |
19-27 |
|
第三章 毛毛虫的最优标号 |
27-33 |
|
§3.1 引言 |
27-28 |
|
§3.2 主要结论 |
28-33 |
|
第四章 关于图的L(2,1)-标号数的一点注记 |
33-36 |
|
§4.1 引言 |
33 |
|
§4.2 主要定理的证明 |
33-36 |
|
参考文献 |
36-39 |
|
作者申请硕士学位期间所做的工作 |
39-40 |
|
致谢 |
40 |
|
| 【DOI】 | LunWen.ID:2.2008.11794 |
