| 【中文题名】 | 可满着色图和最优标号问题 |
| 【英文题名】 | Full-colorable Graphs and Optimal Label |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-13 |
| 【中关键词】 | L（2,1）标号,频率分配问题,No-hole,L（2,不连续增长路 |
| 【英关键词】 | L（2, 1）-labeling,Channel assignment problem,No-hole L（2,1）-labeling,Increasing nonconsecutive path,Optimal label, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
图的染色问题是图论中最基本，也是最重要的问题之一。而图的标号问题作为图的染色问题的推广在现实生活中有广泛的应用。
本文主要讨论了图上的两种标号问题：L(2，1)-标号和最优标号。
给定一个无向图G，G的一个L(2，1)-标号是指从其顶点集V(G)到非负整数集的一个映射f，满足：这里d_G(u，v)表示u和v之间的距离。若一个L(2，1)-标号中的所有标号都不超过整数k，则称之为k-L(2，1)-标号。图G的L(2，1)-标号数，记作λ(G)，是使得图G存在L(2，1)-标号的最小正整数k。特别地，若G的某个L(2，1)-标号中的标号是连续出现的，则称之为G的一个No-hole L(2，1)-标号。图G的No-hole L(2，1)-标号数，记作(?)(G)，是使得图G存在No-hole L(2，1)-标号的最小正整数k。很显然(?)(G)≥λ(G)。在第二章中我们将把注意力放在上述不等式取等号的情况，并把一个满足(?)(G)=λ(G)的图G称为可满着色图，否则称G为非可满着色图。本文第二章将给出一些可满着色图，主要结果有：(1)：刻画非可满着色图的基本结构。(2)：G是n个顶点m条边... |
| 【论文题纲】 |
|
论文摘要 |
6-8 |
|
ABSTRACT |
8-11 |
|
第一章 引言 |
11-18 |
|
§1.1 背景和基本概念 |
11-15 |
|
§1.2 主要的相关结果 |
15-18 |
|
第二章 可满着色的L(2,1)-标号图 |
18-29 |
|
§2.1 非可满着色图的基本结构 |
18-21 |
|
§2.2 几类可满着色图 |
21-29 |
|
第三章 L(2,1)-标号的其它一些结果 |
29-34 |
|
§3.1 特殊图的L(2,1)-标号 |
29-31 |
|
§3.2 图与补图的L(2,1)-标号 |
31-34 |
|
第四章 图的最优标号 |
34-40 |
|
§4.1 一个简单的证明 |
34-36 |
|
§4.2 圈和星图的最优标号 |
36-40 |
|
参考文献 |
40-43 |
|
作者申请硕士学位期间完成的工作 |
43-44 |
|
致谢 |
44 |
|
| 【DOI】 | LunWen.ID:2.2008.11830 |
