| 【中文题名】 | 图的L（p，q）-标号问题研究 |
| 【英文题名】 | Study on the Problem of L(p, q)-Labeling of Graphs |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-10-17 |
| 【中关键词】 | 图的L（p,q）-标号,L（p,q）-边-标号,边-L（p,q）-数 |
| 【英关键词】 | L（p,q）-labeling,edge-L（p,q）-labeling,edge-L（p,q）-number,strong edge-coloring,strong edge- chromatic number,list-strong edge-coloring,strong edge-choice number, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 图的L(p，q)-标号来源于Hale所介绍的频率分配问题作为研究背景。给定图G和两个正整数p≥q，G的一个m-L(p，q)-标号是映射f：V(G)→{0，1，2，…，m}使得对任意x，y∈V(G)，若d_G(x，y)=1则|f(x)-f(y)|≥p；若d_G(x，y)=2则|f(x)-f(y)|≥q，并称λ_(p，q)(G)=min{m|存在G的一个m-L(p，q)—标号}为图G的L(p，q)-数。
本学位论文，首先总结近些年图的L(p，q)-标号的主要结果和进展，然后我们兴趣在于最大度△(G)≤4的图G的线图L(G)的L(1，1)-标号和L(2，1)-标号。通常用λ′_(p，q)(G)记线图L(G)的L(p，q)-数。最后，研究某些特殊图类的L(P，q)—标号问题。
线图L(G)的L(1，1)-标号是类似于图G的强边-染色，记S_(X′)(G)(S_(X′_l)(G))为G的强边-色数(列表-强边-色数)，那么S_(X′)(G)=λ′_(1，1)(G)+1。在1985年，Erdos和Nesetril提出猜想，令G为简单图，那么当△(G)为偶数时，S_(X′)(G)≤5△~2(... |
| 【论文题纲】 |
|
中文摘要 |
2-3 |
|
英文摘要 |
3-5 |
|
第一章 绪论 |
5-10 |
|
(一)、应用背景 |
5-7 |
|
(二)、研究现状 |
7-8 |
|
(三)、基本概念和符号 |
8-10 |
|
第二章 图的强边-染色 |
10-33 |
|
(一)、强边-染色猜想 |
10-11 |
|
(二)、△(G)=4时图的列表-强边-染色 |
11-23 |
|
(三)、△(G)=3时图的列表-强边-染色 |
23-28 |
|
(四)、△(G)=4时图的强边-染色 |
28-33 |
|
第三章 图的L(2,1)-边-标号 |
33-40 |
|
(一)、△(G)=4时图的L(2,1)-边-标号 |
33-37 |
|
(二)、△(G)=3时图的L(2,1)-边-标号 |
37-40 |
|
第四章 某些图类的L(p,q)-标号 |
40-46 |
|
(一)、定义、引理及符号 |
40-41 |
|
(二)、k-退化图,联图G_1∨G_2及M-matched图G_1M~+G_2 |
41-43 |
|
(三)、仙人掌图,唯一圈图 |
43-46 |
|
参考文献 |
46-49 |
|
致谢 |
49-50 |
|
攻读硕士学位期间发表论文 |
50-51 |
|
学位论文独创性声明 |
51 |
|
学位论文使用授权声明 |
51 |
|
| 【DOI】 | LunWen.ID:2.2008.11732 |
