| 【中文题名】 | 图的平方着色、L（2，1）-标号以及列表L（2，1）-标号 |
| 【英文题名】 | The Square Coloring, L(2,1)-Labelling and List L(2,1)-Labelling of Graphs |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-8-30 |
| 【中关键词】 | 图,平方着色,L（2,1）-标号,L（2,列表L（2 |
| 【英关键词】 | graph,square coloring,L（2,1）-labelling,L'（2,1）-labelling,list L（2,1）-labelling, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 以频率分配问题作为应用背景,该文研究了图的平方着色、L(2,1)-标号以及列表L(2,1)-标号问题.设χ(G~2),λ(G),λ_l(G)分别表示图G的平方色数,L(2,1)-标号数,列表L(2,1)-标号数.关于χ(G~2)和λ(G),有以下两个著名的猜想:
猜想1[8] 若图G是平面图,则有
猜想2[7] 若图G的最大度Δ(G)≥2,则有λ(G)≤Δ~2(G)。
但是,目前国内外对图的列表L(2,1)-标号问题的研究不多。
在第二章中我们考虑了Halin图的平方着色问题。证明了对所有Halin图有Δ(G)+1≤χ(G~2)≤Δ(G)+3;对于最大度至少为5的Halin图G有χ(G~2)=Δ(G)+1。
在第三章中我们研究了图的L(2,1)-标号问题。首先研究了Halin图、Mycielski图和Kneser图的L(2,1)-标号问题,得到了
(1) 对所有Halin图有χ(G)≤Δ(G)+7;对于最大度至少为9的Halin图G有λ(G)≤Δ(G)+2。
(2) 对所有图有λ(μ(G))≤3Δ(μ(G))-1;|G... |
| 【论文题纲】 |
|
摘要 |
2-4 |
|
Abstract |
4-7 |
|
一、绪论 |
7-12 |
|
(一)、基本概念 |
7-9 |
|
(二)、L(p，q)-标号问题的概念、应用背景与研究概况 |
9-11 |
|
(三)、本文的主要创新点 |
11-12 |
|
二、Halin图的平方着色 |
12-20 |
|
三、图的L(2，1)-标号 |
20-36 |
|
(一)、Halin图的L(2，1)-标号 |
20-25 |
|
(二)、Mycielski图的L(2，1)-标号 |
25-29 |
|
(三)、Kneser图的L(2，1)-标号 |
29-31 |
|
(四)、一般图的L(2，1)-标号数的算法 |
31-36 |
|
四、图的列表L(2，1)-标号 |
36-53 |
|
(一)、一般图的列表L(2，1)-标号 |
36 |
|
(二)、Halin图的列表L(2，1)-标号 |
36-45 |
|
(三)、笛卡儿乘积图G×H的列表L(2，1)-标号 |
45-47 |
|
(四)、复合图G[H]的列表L(2，1)-标号 |
47-48 |
|
(五)、全图T(G)的列表L(2，1)-标号 |
48-50 |
|
(六)、块图S(G)的列表L(2，1)-标号 |
50-51 |
|
(七)、无爪图的列表L(2，1)-标号 |
51-53 |
|
参考文献 |
53-56 |
|
致谢 |
56-57 |
|
攻读学位期间发表的学术论文 |
57 |
|
| 【DOI】 | LunWen.ID:2.2008.11551 |
