| 【中文题名】 | 图的（d,1）-全标号问题 |
| 【英文题名】 | The Problem of (d,1)-Total Labeling in Graphs |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-3-28 |
| 【中关键词】 | 全标号,（d,1）-全标号,L（d,1）-标号,L（p |
| 【英关键词】 | total labeling,（d,1）-total labeling,L（d,1）-labeling,L（p,q）-labeling, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 本学位论文研究的(d，1)-全标号问题源于以无线电频道分配为背景的距离2标号问题。图G的一个k-(d，1)-全标号是一个从集合V(G)∪E(G)到{0，1，…，k}的映射使得相邻点有不同值、相邻边有不同值、相关联的点和边的值差至少是d．G的(d，1)-全标号数λ_d~T(G)是使得G有k-(d，1)-全标号的最小的k值。
2002年，Havet和Yu最先引进了(d，1)-全标号这一概念，并猜想：λ_d~T(G)≤Δ(G)+2d—1。
本学位论文主要围绕这个猜想展开研究。在第一章，我们给出了一些基本概念以及图的(d，1)-全标号问题的研究背景和现状，并且介绍了本学位论文的主要结果。
在第二章，我们给出了最大度为3的树的(2，1)-全标号数的一个完全刻画。在第三章，对于外平面图的(2，1)-全标号，我们证明了以下结果：
(1)若Δ(G)≤2，则λ_2~T(G)≤4；
(2)若Δ(G)=3且G是2-连通的，则λ_2~T(G)≤5；
(3)若Δ(G)=4，G是2-连通的且不含有n-开齿(n≥4)，则λ_2~T(G)≤6；
... |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
ABSTRACT |
3-5 |
|
目录 |
5-6 |
|
一、绪论 |
6-12 |
|
(一)、基本概念 |
6-7 |
|
(二)、(d,1)-全标号问题的研究背景及现状 |
7-10 |
|
(三)、本文的主要结果 |
10-12 |
|
二、树的(2,1)-全标号 |
12-22 |
|
(一)、预备引理 |
12-17 |
|
(二)、最大度为3的树的(2,1)-全标号的刻画 |
17-22 |
|
三、外平面图的(2,1)-全标号 |
22-38 |
|
(一)、Δ(G)≤3的情况 |
22-23 |
|
(二)、Δ=4的情况 |
23-35 |
|
(三)、Δ≥5的情况 |
35-38 |
|
四、积图的(2,1)-全标号 |
38-43 |
|
(一)、C_m×C_n的(2,1)-全标号数 |
38-40 |
|
(二)、P_m×P_n的(2、1)-全标号数 |
40-43 |
|
五、若干图的(d,1)-全标号 |
43-49 |
|
参考文献 |
49-52 |
|
附录1 |
52-58 |
|
致谢 |
58-59 |
|
攻读期间的研究成果及发表的论文 |
59-61 |
|
| 【DOI】 | LunWen.ID:2.2008.11758 |
