完全四部图K1,1,m,n和K1,3,3,n的交叉数下界

来源 :辽宁师范大学 | 被引量 : 0次 | 上传用户:daxing_hhx
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数理论是图论中十分重要的一个分支,多年来,国内外很多学者都从事过有关图的交叉数这一问题的研究。事实上,Garey和Johnson证明了确定一个图的交叉数是NP-完全问题,正是由于其难度,国内外在这方面的进展才如此缓慢。到目前为止,能确定交叉数的完全多部图少之又少。本文主要研究几个完全多部图的交叉数。  本文的主要内容:  (1)对于完全四部图,K1,1,m,n首先,构造出K1,1,m,n的一个好画法,证明其交叉数的一个上界;其次,对K1,1,m,n的一个好画法进行适当的调整,构成完全三部图K1,m+1,n+1的一个好画法,证明出K1,1,m,n交叉数的一个下界;最后,假设完全三部图K2,m,n的交叉数是z(m+2,n+2)-mn进而得到K1,1,m,n当m与n均为奇数时的交叉数:cr(K1,1,m,n)=z(m+2,n)+([)m/2(])([)m-1/2(])n+([)m/2(])([)n/2(]),并给出当m,n为其他情形时K1,1,m,n交叉数的猜想。  (2)依据完全四部图K1,2,2,n好画法的局部特征,我们将K1,2,2,n的好画法分为两类,再用和(1)类似但不同于Ho的方法证明了K1,2,2,n的交叉数:cr(K1,2,2,n)=z(5,n)+([)3n/2(]).  (3)对于完全四部图K1,3,3,n,首先,通过构造完全三部图K3,4,n的一个好画法,给出K3,4,n交叉数的猜想:cr(K3,4,n)=z(7,n)+4n+2([)n/2(])+2;其次,构造出K1,3,3,n的一个好画法,证明其交叉数的一个上界。根据K1,3,3,n好画法的局部特征,我们将K1,3,3,n的好画法分为三类,对K1,3,3,n的一个好画法进行适当的调整,构成完全三部图K3,4,n+1的一个好画法,证明出K1,3,3,n交叉数的一个下界;最后,结合K3,4,n交叉数的猜想,进而得到K1,3,3,n交叉数的猜想:cr(K1,3,3,n)=|z(7,n)+5n+3([)n/2(])+3.
其他文献
首先,我敬请大家谅解我的坦诚。像我们这样生在新时期的年轻人,要说对“没有共产党,就没新中国……”的内涵究竟有多深的理解,真是很难说的,是肯定不能与那些经历过新旧两重
近二十年来,人工神经网络的理论和应用研究引起科学工作者的很大兴趣,并成为非线性科学领域的研究热点之一,究其原因,这主要因为人工神经网络有着丰富的动力学行为,如稳定性
投资组合选择是现代金融理论的核心问题之一,它主要解决的问题就是如何把一定数量的资金分配到不同的资产中,使得在小于某给定风险水平下最大化收益或者在收益一定的情况下最小化风险。另一方面,交易费用是实际的市场中比较常见的一种摩擦因素。交易费用对投资组合的影响是显著的,不考虑交易费用可能会导致无效的投资组合,交易费用对投资组合份额的选择也有影响。因此,本文考虑有交易费用的情况下研究基于CVaR(条件风险价
宁夏吴忠黄河公路特大桥主桥为大跨度预应力混凝土连续箱梁,现浇节段法施工工艺,箱梁采用了C55高性能混凝土,为宁夏地区首次应用。以C55高性能混凝土配合比设计为例,阐述了C55高
期刊
本文研究的是两个特殊情况的在线(Over List)并行工件排序,目标是最大完工时间最小。并行工件排序与一般平行机排序问题的工件不同之处在于,一个工件可能需要若干台机器同时对
期刊
在本文中,我们主要关注定义在赋范代数A上的J ordan初等算子  UA,B:X→AX B+B X A,(A,B∈A).  范数问题是初等算子研究的核心问题之一,对 J ordan初等算子而言,寻求不等式
本论文主要研究的是给定亏格曲面上的非同构根地图,即所谓的带根地图计数问题(如不特别申明,文中凡提及地图皆指带根地图).其作为一般地图计数的理论基础,该问题的研究具有重要的
牢记宗旨,树立高尚博大的亲情观。邓小平曾有过精辟的论述:“人民是一切的母亲。”陈毅也说过,“人民是我的亲父母,我是人民的好儿郎。”“心无百姓莫为官”。对领导干部来
本文首先研宄了一个欧拉-拉格朗日泛函方程在模糊空间上的稳定性.然后又考虑了一个二次可加函数在β-Banach空间上的稳定性.  根据内容本文分为以下三章:  第一章概述了一