【摘 要】
：
图G的一个平衡k-划分是V(G)的一个划分V1∪V2…∪Vk,使得∣∣Vi∣-∣Vj∣|≤1,I,j ∈｛1,2,…,k｝.
Bollob(a)as与Scott猜想: 任一图G都存在平衡划分V(G)=V1∪V2使得:（1)任给
论文部分内容阅读
图G的一个平衡k-划分是V(G)的一个划分V1∪V2…∪Vk,使得∣∣Vi∣-∣Vj∣|≤1,I,j ∈｛1,2,…,k｝.
Bollob(a)as与Scott猜想: 任一图G都存在平衡划分V(G)=V1∪V2使得:（1)任给v ∈V1,满足dG[V1](v)-dG[V2∪{v}(v)≤1;(2)任给v∈V2,满足dG[V2](v)-dG[V1∪{v}](v)≤1.
我们把满足上述猜想的划分称为大平衡划分. 类似地，我们引入了小平衡划分的定义: 一个图G的平衡划分V(G)=V1∪V2，如果满足下列条件:（1)任给v∈V1，满足dG[V2∪{v}](v)-dG[V1](v)≤1;(2)任给v∈V2，满足dG[V1∪{v}](v)-dG[V2](v)≤1. 则称V(G)=V1∪V2为G的一个小平衡划分.
在本文中，我们得到了大平衡划分与小平衡划分的一个关系: 一个图存在小平衡划分，则它的补图存在大平衡划分. 并且给出了不存在小平衡划分的反例. 通过利用上述关系和图本身的结构性质证明了k-正则图、树、树的补图、度不大于3的图及两类特殊的二部图的补图存在大平衡划分，其中k∈｛3,n-1,n-2,n-3,n-4g.对于k=3或n-4的一个特殊情形，还给出了寻找k-正则图平衡划分的算法.
其他文献
现实中，捕食者与被捕食者的关系不一定永远是猎杀关系，在一定的条件下他们可以合作共存的。在种内竞争的Lotka—Volterra捕食系统基础上，我们建立了一类具合作关系捕食系统的模
随着人类社会的不断进步，科学技术的不断发展，生产和生活的控制和管理问题得到了广大学者的普遍关注。本文主要研究控制理论中的一致性问题。一致性问题（consensus problem）的研
竞争性选址问题是选址问题中具有重要意义和引起广泛关注的一类实际问题.近年来,随着经济的快速增长和人民生活水平的逐步提高,物流配送产业飞速发展.物流配送中心作为物流网
本文对6维近凯勒流形中典型子流形的刚性及分类问题进行了研究。6维近凯勒流形是一类重要的几何对象,对其各种典型子流形的研究是十分自然而重要的课题。本文研究6维近凯勒流
Sturmian序列是定义在二元字母表上的具有最小复杂度的非最终周期序列。
这类序列有许多等价的定义和性质，他们在许多领域内有重要的应用，例如：组合论、数论、动力系统论等
在本文中，我们研究了一类带非光滑核的多线性奇异积分算子的极大算子的有界性，加权模不等式。同时，在齐型乘积空间以及C2n的区域边界上研究了乘积型的Hardy空间和BMO空间理论以
数论是一门研究整数性质的学科，在数学中占有非常重要的地位，而数论问题中，关于一些特殊序列及函数的均值性质的研究一直备受数论工作者和学者的关注，数论中的很多猜想和难题都与
自上世纪九十年代以来,建立在结构风险最小化基础上的支持向量机(Support Vector Machine, SVM)已经成功地应用于各种实际问题中,如粒子识别、文本分类、生物信息学和金融应
现代科学技术的发展在很大程度上依赖于物理学、化学、和生物学等各科的成就和发展，而这些学科自身的精确化必须通过建立相应的数学模型来实现，而这些数学模型中有大量问题与偏