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

关于K-完美超图的一些性质

作　者: 孙林
导　师: 王迪吉；杜智华
学　校: 新疆师范大学
专　业: 基础数学
关键词: 弱k-完美强k-完美 k-团强色数平衡超图单模超图树超图线图强独立集
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 29次
引　用: 1次
阅　读: 论文下载

内容摘要

此文章的思想主要来自于拉瓦兹和贝尔热在完美图方面所做出的文章，这些文章详细的说明了完美图的性质和一些相关重要定理。图G是完美的，如果G和它的所有诱导子图都满足色数等于其相应的最大团的基数。完美图的思想最早是由贝尔热于1961提出的，这个思想是图论的一大成果，与此同时，关于完美图还有两个非常重要的猜想，即弱完美图猜想和强完美图猜想，不过，现在已经被证明为定理。我们都知道，超图要比图更加广泛，因为图是超图的一种特殊情况。所以，根据图的完美性，我想进一步讨论超图的完美性，然而图的完美性不能平行地转移到超图上来。所以，一方面，我把图的完美性作为这篇文章的基础；另一方面，在超图的完美性方面，我做了一些新的定义。超图H是指超边的集合，其中超边是基数至少是2的顶点子集。在这篇文章中，我只讨论有限超图。以下是我的主要工作： 1．定理1．2．1 超图H是弱k-完美的当且仅当H的任何一个有k-团的诱导子超图H_A都存在一个强独立集B使得w_k（H_A-B）＜w_k（H_A）。 2．定理1．3．1 超图H是2—完美的当且仅当[H]₂是完美的。 3．定理1．4．1 如果超图H是弱k-完美的，则w_k（H）=max「|A|/α（H_A）」，A≠φ，A（?）X（H）。 4．定理1．4．2 超图H是在X={x₁，x₂，…，x_n)上的一个弱k—完

全文目录

中文摘要  3-5
英文摘要  5-7
文献综述  7-10
1.关于k-完美超图的一些性质  10-18
2.树超图、平衡超图和单模超图的完美性  18-20
3.关于k-完美超图的一些充分必要条件  20-25
附录  25-26
致谢  26

关于K-完美超图的一些性质

内容摘要

全文目录

相似论文