学位论文 > 优秀研究生学位论文题录展示

图的f-染色和均匀边染色

作　者: 张霞
导　师: 刘桂真
学　校: 山东大学
专　业: 运筹学与控制论
关键词: 边染色 f-染色 均匀边染色 分数f-染色 色数 分类问题
分类号: O157.5
类　型: 博士论文
年　份: 2007年
下　载: 284次
引　用: 0次
阅　读: 论文下载
 

内容摘要


图的染色理论在图论中占据着重要的位置。图的染色理论有很多分支，如边染色、点染色、面染色和全染色等。其中研究最多，结果也较完善的就是图的边染色。本文旨在讨论图的边染色的几个问题，即f-染色，均匀边染色和分数f-染色。本文所考虑的图都是有限无向图，它们允许有重边，但没有环。图G的一个边染色就是把G的边集划分为一些边不交的子集。为便于叙述，我们常常称这些子集为颜色类，并给每个颜色类分配一个不同的颜色。设g，f是与图G的每个顶点相关联的两个整值函数，并且对每一个v∈V（G）满足0≤g（v）≤f（v）。G的一个（g，f）-因子F是G的一个支撑子图，并且对所有的v∈V（G）满足g（v）≤dF（v）≤f（v）。如果图G的一个边染色满足每个同色边导出子图都是图G的一个（g，f）-因子，则称该边染色是图G的一个（g，f）-染色。特别地，（0，1）-染色，（0，f）-染色，（1，d）-染色和（g，d）-染色（对G的每个顶点v，d=d（v））一般分别被称为正常的边染色，f-染色，边覆盖染色和g-边覆盖染色。1986年，Hakimi和Kariv[33]将正常的边染色推广到f-染色并且得到了很多有意义的结果。使G有一个f-染色所需的最少的颜色数被称为图G的f-色数，记作x′f（G）。显然，当对所有的v∈V（G）都有f（v）=1时，f-染色问题，即要确定任意图G的x′f（G），就简化为正常的边染色问题。Holyer[42]证明正常的边染色问题是NP-完全的，即使限制到立方图也是如此。因此涵盖正常的边染色问题为其子问题的f-染色问题也是NP-完全的。对一个图G，我们记△（G）=（?）{（d（v）}，△f（G）=（?）{「d（v）/f（v）（?）}，其中「d（v）/f（v）（?）为不小于d（v）/f（v）的最小整数。在正常的边染色中，Vizing[79]的一个著名结果表明：任何简单图G有x′（G）=△（G）或△（G）+1。根据这个结果，所有的简单图可以被划分成两类。若x′（G）=△（G），我们称简单图G是第一类的，否则是第二类的。确定一个简单图是第一类还是第二类的问题被称为关于正常边染色的分类问题。关于正常边染色的分类问题已经有了大量的研究。特别重要的是，作为Hakimi和Kariv[33]一个结果的推论，简单图的f-染色有一个类似的结果，即对任意的简单图G有△f（G）≤x′f（G）≤△f（G）+1成立。我们自然也可以考虑关于f-染色的分类问题。若x′f（G）=△f（G），我们称图G是f-第一类的，否则是f-第二类的。当所有的v∈V（G）均有f（v）=1时，关于f-染色的分类问题就简化为关于正常边染色的分类问题。本文讨论的另外一个问题是图的均匀边染色。设k≥2为一个整数，并且C={c1，c2，…，ck）为一个颜色集。给定了图G的用C中k种颜色的一个边染色，对每个v∈V（G），用ci（v）记与v邻接的染颜色ci（1≤i≤k）的那些边的集合。如果图G的用C中k种颜色的一个边染色对所有的1≤i＜j≤k和所有的v∈V（G）都满足‖ci（v）|～|cj（v）‖≤1，则称该边染色是均匀的。均匀边染色问题就是对任意的整数k≥2确定一个给定的图是否有k色的均匀边染色。我们定义Vt（G）={v∈V（G）∶t|d（v）)，其中t是一个正整数。我们称由Vt（G）导出的G的那个子图为G的t-核。Hilton和de Werra[39]研究了简单图的均匀边染色问题，并给出了基于一个简单图的k-核的几个有意义的结果。徐常青[91]考虑了图的均匀边染色并给出了一个图有k色的均匀边染色的一个充分条件。对所有的v∈V（G）令f（v）=「（d（v））/k（?），我们可以看出图G有一个k色的均匀边染色当且仅当G有一个k色的（f-1，f）-染色。因此图的均匀边染色与图的f-染色或者g-边覆盖染色有密切的关系。在本文中，我们借助f-染色的一些方法获得了一个简单图有k色均匀边染色的一个新的充分条件，该条件严格的覆盖了Hilton在[37]中所提出的一个猜想。进一步将这个新结果应用到简单图的边覆盖染色中，我们推广了王纪辉，张霞和刘桂真在[83]中的一个结果。分数图论是研究各种图论问题的一个重要工具。我们也将它应用到图的f-染色的研究中。于是要讨论的第三个问题就是图的分数f-染色。设G是一个图，f是给每个顶点v∈V（G）分配一个正整数f（v）的一个函数。G的一个（0，f）-因子IF是G的一个支撑子图，使得对每个v∈V（G）有0≤dIF（v）≤f（v）。G的一个（0，f）-因子IF的边集被称为G中的一个f-匹配，记作F。一个分数f-染色就是给G的每个f-匹配F分配一个非负权wF，使得对每一条边e∈E（G）我们有∑F（?）ewF≥1。G的分数f-色数x′ff（G）=（?）∑FwF（其中，“和”是取遍所有的f-匹配F，“最小”是取遍所有的分数f-染色c）。许多在（整值）图论中未解决的问题或猜想能够在分数图论中被解决。关于分数f-染色的研究为f-染色问题的解决提供了一个新的思路。有时候，一个分数f-染色可能恰好就是我们想要的一个f-染色。本文分为四章。在第一章中，我们回顾一下边染色的历史和一些进展。在第二章中，我们研究关于f-染色的分类问题和f-临界图的性质。首先，我们基于简单图G的f-核给出G是f-第一类图的一系列充分条件和关于函数f的两个充分条件。其次，我们确定完全图的f-色数，并讨论简单正则图关于f-染色的分类问题。最后，我们给出f-临界图的一个性质。在第三章中，我们给出简单图均匀边染色的一个新的充分条件。这个结果证实Hilton[37]在2005年提出的一个猜想，并且实质性地将其推广到一个更一般的图类。另外，我们把简单图均匀边染色的这个新结果应用到简单图的边覆盖染色中，推广了王纪辉，张霞和刘桂真的一个结果[83]。在第四章中，我们给出一个图的分数f-色数的确切值。作为其一个推论，我们证明了Nakano等人在[62]中提出的一个猜想的分数形式。下面，我们将列出本文的主要结果。我们定义V0*（G）={v∈V（G）∶（d（v））/（f（v））=△f（G）}。图G的f-核是由V0*（G）导出的G的子图，记作G△f。（当对所有的v∈V（G）有f（v）=1时，图G的f-核就是G的核。）首先在第二章中，基于简单图G的f-核，我们给出G是f-第一类图的一系列充分条件。结论1设G是一个简单图。若V0*（G）=（?），则G是f-第一类的。结论2设G是一个简单图。若G△f是一个森林，则G是f-第一类的。如果一个图H的所有边可以被排序为e1，e2，…，eε（H），使得对每一个j（1≤j≤ε（H）），边ej都有一个端点vj满足在每个顶点u∈NH（vj）处都有一条边ei（i≥j），我们则称H是边有序的。结论3设G是一个简单图。若G△f是边有序的，则G是f-第一类的。可以证实森林是边有序的。因此结论3覆盖了结论2。给定X（?）V（G）\V0*（G），令HX表示由V（HX）=V0*（G）∪X和E（HX）=E(G△f)∪E（X，V0*（G））定义的G的子图，其中E（X，V0*（G））表示连接X中顶点和V0*（G）中顶点的所有边的集合。按类似的方式，可以证明一个稍微更一般的结果。结论4设G是一个简单图。若存在X（?）V（G）\V0*（G）使得HX是边有序的，则G是f-第一类的。我们称d（v）/f（v）为G中顶点v的f-率，记作df（v）。如果一个图G的所有顶点可相继用下述剥离法则剥离掉，则称G是△f（G）-可剥离的：如果顶点v最多还剩下一个f-率为△f（G）的邻点，那么剥离v。于是我们有下述结果。结论5设G是一个简单图。若G是△f（G）-可剥离的，则G是f-第一类的。下述结果证明结论5覆盖了结论4。结论6设G是一个简单图。若存在X（?）V（G）\V0*（G）使得HX是边有序的，则G是△f（G）-可剥离的。进一步地，通过实例展示结论6的逆不成立，我们证明结论5严格强于结论4。另一方面，我们有下述的结论6的部分的逆。结论7设简单图G是△f（G）-可剥离的，并且V0*（G）中的所有顶点可以先被剥离。则G△f是边有序的。特别地，当对所有的v∈V（G）都有f（v）=1时，我们可以推导出Fournier[28]，Hoffman等[41]和Hakimi等[34]基于G的核的那些结果。其次，在第二章中，我们基于函数f给出了一个简单图是f-第一类图的两个充分条件。给定图G的一个部分的边染色，H是G的一个连通子图，若ε（H）是奇数并且对每个v∈V（H）都有dH（v）=2f（v），则称H是一个障碍（对一个部分的f-染色而言）。结论8设G是一个图。若G中没有障碍，则x′f（G）=△f（G）。显然，如果G是一个简单图，则G是f-第一类的。由结论8，我们可以很容易地推导出Hakimi和Kariv[33]的两个结果。此外，我们有下述结果，它推广了Hakimi和Kariv[33]一个结果的简单图形式。结论9设G是一个简单图。假定V0*（G）≠（?）。若对所有的v∈V0*（G）∪NG（V0*（G）），f（v）均为正偶数，则G是f-第一类的。我们还证明了该条件在一定意义下是最好的。进而，在第二章中，我们对两类特殊的简单图讨论了关于f-染色的分类问题。我们完全解决了完全图关于f-染色的分类问题。结论10设G是一个完全图Kn若k和n是奇数，并且对所有的v∈V（G）均有f（v）=k和k|d（v），则G是f-第二类的。否则，G是f-第一类的。令f*=minv∈V（G）{f（v）}。对简单正则图，我们有下列结果。结论11设G是一个度d（G）=△的简单正则图。若f*（?）△或者f*是偶数，则G是f-第一类的。结论12设n≥1。设G是一个顶点数为2n+1且度d（G）=△的简单正则图。若对所有的v∈V（G）均有f（v）=f*是奇数并且f*|△，则G是f-第二类的。结论13设G是一个顶点数为n且度d（G）=△的简单正则图，并设G≠Kn。假定w∈V（G）是满足f（w）＞f*的唯一顶点。则G是f-第一类的当且仅当G—w是f-第一类的。结论14设n≥1。设G是一个顶点数为2n且度d（G）=△的简单正则图，这里G≠K2n。假定对所有的v∈V（G）均有f（v）=f*。则G是f-第一类的当且仅当G—w是f-第一类的，其中w∈V（G）。显然，当对所有的v∈V（G）都有f（u）=1时，我们可以从结论10，12，14推导出完全图和简单正则图关于正常边染色的分类问题中的那些结果（见[11，13]）。最后，在第二章中，我们考虑f-临界图的性质．若简单图G是f-第二类的，并且对每条边e∈E（G）都有x′f（G—e）＜x′f（G），则称G是f-临界的。我们得到了下述结果，当对所有的v∈V（G）都有f（v）=1时可以得到Vizing邻接引理[80]。结论15设G是一个f-临界图并且u，w是G中的相邻顶点。则w至少与f（w）（f（u）△f（G）—d（u）+1）个f-率为△f（G）且不同于u的顶点邻接。于是，我们得到下述结果。结论16设G是一个f-临界图。则G·的每个非孤立顶点都有至少两个f-率为△f（G）的邻点，并且G包含至少三个f-率为△f（G）的顶点。由结论16，我们也给出了结论5的另外一个证明。在第三章中，我们考虑简单图的均匀边染色。令M（v）记顶点v处至多出现了f（v）—1次的那些颜色的集合。我们证明了简单图有均匀边染色的一个新的充分条件。结论17设G是一个简单图并设k≥2。假定对每个v∈V（G）有f（v）=「（d（v））/k（?）。设C={c1，c2，…，ck}。如果可以用C中的k种颜色按顺序e1，e2，…eε（G）对G的边进行f-染色，并满足对每个j（1≤j≤ε（G）），当f-染色第j条边ej=wjvj时，对所有的v∈NG（wj）或者所有的v∈NG（vj）有M（v）≠（?）成立，则G有一个k色的均匀边染色。我们找到了一个简单图具有结论17所述性质的更简单的一个充分条件。如果一个图G的所有顶点可用下述t-剥离法则相继被剥离掉，我们称G是t-可剥离的：如果顶点v至多还剩下一个这样的邻点v′满足v′∈Vt（G）并且v′的度仍然是dG（v′），那么剥离顶点v。于是我们有下述结果。结论18设G是一个简单图并设k≥2。若G是k-可剥离的，则G有一个k色的均匀边染色。结论18推广了Hilton和de Werra在[39]中的结果，并且证实了下述猜想。猜想A （Hilton[37]）设G是一个简单图并设k≥2。若G的k-核是一个森林，则G有一个k色的均匀边染色。另外，我们用一个例子证明结论18严格强于猜想A。图G有一个边覆盖染色所需的最多的颜色数被称为G的边覆盖色数，记作x′c（G）。关于一个图的边覆盖色数，Gupta[31]的一个著名的结果表明：任意的简单图G均有x′c（G）=δ（G）或者δ（G）。—1。将结论18应用到简单图的边覆盖染色中，我们立即得到了一个简单的结果。结论19设G是一个简单图且δ（G）＞0。若G是δ（G）-可剥离的，则x′c（G）=δ（G）。我们考虑一类特殊的简单图。如果一个图G的所有顶点可以用下述弱-δ（G）-剥离法则相继被剥离掉，那么我们称G是弱-δ（G）-可剥离的：如果顶点v至多还剩下一个这样的邻点v′满足v′∈V（Gδ）并且v′的度仍然是δ（G），那么剥离顶点v。对弱-δ（G）-可剥离简单图，我们得到如下漂亮的结果。结论20设G是一个简单图且δ（G）＞0。若G是弱-δ（G）-可剥离的，则x′c（G）=δ（G）。这个结果严格覆盖了结论19，也是王纪辉，张霞和刘桂真在[83]中一个结果的推广。在第四章中，我们讨论图的分数f-染色。Nakano等提出了下列猜想。猜想B（Nalcano等[62]）若G是一个图，则x′f（G）≤max{△f（G）+1，「∧f（G）（?）}，这里∧f（G）=（?）{（ε（H））/（sum from v∈V（H） to（f（v））/2）)}其中v（H）≥2。我们给出了图的分数f-色数的确切值。结论21对任意的图G，x′ff（G）=max{（?）df（v），∧f（G）}。作为以上结果的一个推论，我们证明了猜想B的分数形式。我们也可以从结论21推导出很多有意义的结果。另外，我们分别在第二、三、四章中给出了一些未解决的问题。

全文目录


中文部分  1-115
  中文摘要  6-14
  英文摘要  14-24
  符号说明  24-27
  第一章 绪论  27-35
    1.1 基本定义和符号  27-29
    1.2 边染色的历史及其进展  29-35
      1.2.1 图的f-染色  31-33
      1.2.2 图的均匀边染色  33
      1.2.3 图的分数f-染色  33-35
  第二章 简单图的f-染色  35-60
    2.1 预备知识  35-38
    2.2 基于图的f-核的f-第一类简单图的几个充分条件  38-45
    2.3 基于函数f的f-第一类简单图的两个充分条件  45-49
    2.4 完全图的f-染色  49-52
    2.5 简单正则图的f-染色  52-55
    2.6 f-临界图的性质  55-58
    2.7 关于f-染色的几个问题  58-60
  第三章 简单图的均匀边染色  60-89
    3.1 介绍  60-61
    3.2 一个有用的引理  61-66
    3.3 定理3.1.4的证明  66-80
    3.4 进一步的讨论  80-82
    3.5 在简单图的边覆盖染色中的应用  82-87
    3.6 可进一步研究的问题  87-89
  第四章 图的分数f-染色  89-103
    4.1 预备知识  89-93
    4.2 主要结果  93-102
    4.3 可进一步研究的问题  102-103
  参考文献  103-111
  致谢  111-112
  作者简介  112-114
  学位论文评阅及答辩情况表  114-115
英文部分  115-233
  Chinese Abstract  121-129
  English Abstract  129-138
  Symbols  138-141
  Chapter 1 Introduction  141-151
    1.1 Basic Definitions and Notations  141-143
    1.2 The History and Some Progress of Edge-Coloring  143-151
      1.2.1 f-Colorings of graphs  146-148
      1.2.2 Equitable edge-colorings of graphs  148-149
      1.2.3 Fractional f-colorings of graphs  149-151
  Chapter 2 f-Colorings of Simple Graphs  151-177
    2.1 Preliminaries  151-155
    2.2 Some Sufficient Conditions for a Simple Graph of f-Class 1 Based on the f-Core of the Graph  155-162
    2.3 Two Sufficient Conditions for a Simple Graph of f-Class 1 Based on Function f  162-167
    2.4 f-Colorings of Complete Graphs  167-169
    2.5 f-Colorings of Simple Regular Graphs  169-173
    2.6 A Property of f-Critical Graphs  173-176
    2.7 Related Problems on f-Colorings  176-177
  Chapter 3 Equitable Edge-Colorings of Simple Graphs  177-207
    3.1 Introduction  177-179
    3.2 A Useful Lemma  179-183
    3.3 The Proof of Theorem 3.1.4  183-198
    3.4 Further Discussion  198-201
    3.5 Application to Edge Covering Colorings of Simple graphs  201-205
    3.6 A Problem for Further Research  205-207
  Chapter 4 Fractional f-Colorings of Graphs  207-223
    4.1 Preliminaries  207-211
    4.2 Main Results  211-222
    4.3 A Problem for Further Research  222-223
  References  223-229
  Acknowledgement  229-230
  Curriculum Vitae  230-233
  学位论文评阅及答辩情况表  233

相似论文

  1. 海水珍珠染色机理及染色工艺优化研究,TS933.23
  2. 棉花纤维初始发育的磷酸蛋白质组学研究,S562
  3. 百萨偃麦草染色体1J和5J变异体的诱致与鉴定,S512.1
  4. 普通小麦—加州野大麦双二倍体辐射回交后代的分子细胞遗传学分析,S512.1
  5. 草莓小孢子培养与离体诱导染色体加倍研究,S668.4
  6. 南瓜染色体加倍和体细胞胚发生的细胞学及生理生化变化研究,S642.1
  7. 固始鸡胚期消化管发育的研究,S831
  8. 新疆维吾尔族与哈萨克族人群17个Y-STR基因座遗传多态性研究,R394
  9. Wilson病ATP7B基因重组腺病毒载体对Wilson病人离体肝细胞作用的初步研究,R742.4
  10. 组蛋白特定甲基化位点突变对完整及第二结构域缺失的ELP3转录功能的影响,Q75
  11. RECK蛋白在脑胶质瘤中的表达特点及意义,R739.4
  12. Caveolin-1蛋白在脑胶质瘤中的表达特点及意义,R739.4
  13. EpCAMhigh/CD44+标记的大肠癌干细胞与β-catenin在大肠癌中的表达及临床意义,R735.34
  14. RUNX3蛋白在结直肠癌中的表达特点及意义,R735.3
  15. 大连眼科门诊眼干涩患者调查,R777
  16. 不同水稻品种对灰飞虱抗性机理的初步研究,S511
  17. 866例次白血病患者染色体核型分析,R733.7
  18. 海人酸致痫大鼠神经元树突棘的可塑性变化,R742.1
  19. S100A4蛋白在结直肠癌中的表达特点及其临床意义,R735.3
  20. 国产异氟醚全凭吸入麻醉影响成年大鼠学习记忆的相关研究,R965
  21. 中国淡水涡虫分类及核型研究（Ⅺ）,X174

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com