一致星因子图与笼的连通性

来源 :南开大学 | 被引量 : 0次 | 上传用户:xiaosheng2099
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1940年,Turan首先将极图理论作为一个学科来研究,Paul Erdos进而推动了这一理论的发展。自此,极图理论成为图论的一个重要分支。在极图理论里,我们所感兴趣的是图的各种不变量之间的关系,这些不变量包括顶点数、边数、连通度、最小度、直径等。此外,多大的这些不变量才能保证图具有某些性质,这也是我们所感兴趣的地方。通常对一类图H,给定性质p和一个不变量μ,我们希望确定出最小的值m,使得H中每个满足μ(G)>m的图G都具有性质p。我们称H中的那些不具有性质p且μ(G)=m的图G为此问题下的极图。举个例子,每个顶点数为n,边数至少为n的图一定包含圈,那么在这个问题下的极图就是所有顶点数为n的树。说到这里,我们需要强调下,本文中所说的极图理论是指广义的,它可以包括各种结构性结果。   在本文中,我们主要讨论了两类极图。一类是关于一致星因子图的刻画,另一类则是关于笼的连通性。在第一章中,我们将会介绍一些基本的定义和相关问题的历史背景。   我们称同构于K1,n的树为星,这里n≥1。如果图G的某个生成子图的所有分支都是星,则称这个生成子图足图G的一个星因子。图G的边赋权函数是指ω:E(G)→N+,这里N+表示正整数集合。设H是图G的一个子图,在G的边赋权函数ω下,图H上所有边的权和称为H的权,也就是说,ω(H)=∑e∈E(H)ω(e)。如果图G存在一个边赋权函数ω,使得G的每个星因子的权都相等,那么我们则称图G是一致星因子图。一致星因子图的概念是由Hartnell和Rall在文[24]中提出的。在第二章里,我们首先用Gallai-Edmonds匹配结构定理给出在常函数边赋权条件下,所有一致星因子图的完整刻画;然后给出在一般边赋权函数条件下,所有围长至少为5的一致星因子图的一个清晰刻画。   如果一个k-正则图G的围长为g,则称它为(k,g)-图。对给定的k和g,含有最少顶点数的(k,g)-图则称之为笼。笼问题是图论中最古老的问题之一。笼是由Tutte[52]在1947提出的,此后得到广泛地研究,然而这个课题太难了。一般来说,当k≥3,g≥5时,即使是估计笼的顶点数的界都是很困难的。因此,最近很多学者把精力放在对笼的结构性质研究上了,比如笼的连通性。在文章[Fu,Huang and Rodger,Connectivity of cages,J.Graph Theory,24(1997),187-191]中,他们猜想在k≥3时,所有(k,g)-笼都是k连通的。在第三章里,我们将在前人研究的基础上,继续研究笼的连通性。
其他文献
本文主要目的是利用”点一集”邻属关系的方法研究模糊子格和直觉模糊子格。   首先,应用模糊点与模糊子集的邻属关系,给出了(β,α)-模糊子格的定义.得到了三种有意义的模糊
本文研究了一类半线性双曲型方程的Cauchy问题:的解的存在唯一性。 主要利用Lp空间、Sobolev空间的相关性质,从一个相应的齐次线性波动方程的解的估计入手,以此为基础,通过构
本文建立了两个具有阶段结构的三种群食物链捕食者-被捕食者模型,利用时滞微分方程与动力系统理论与研究方法对模型的动力学性质进行了研究.全文内容共分为三章.  第一章是
1990年,联合国计划署(以下简称UNDP)提出了一个用于衡量人类发展水平的指标,并为世界人民制定了一套用于测量它的体系。根据该体系,UNDP定期计算并公布世界各国的人类发展指
学位
令JM表示一个有限集合M上的全变换半群,A是M的一个非空子集,FM={f∈JM|f(A)()A或者|f(M)|=1}.显然FM是JM的一个子半群。并且当A=M时,FM=JM。本文主要研究FM上的一些等价关系,并且确定
函数空间上的算子理论是线性算子理论中十分活跃并引起广泛关注的分支之一,这是因为算子理论中许多深层次的问题都可以模型化为具体的函数空间上的、由具有某些特殊性质的函数
Water-preservation mining is one of the most important parts of the ‘Green Mining’ technology system,which can realize the effective regulation of groundwater
在数学里面,傅立叶分析和傅立叶变换已经发展了很长一段时间。傅立叶分析有很多的科学应用,例如在物理学,偏微分方程,数论,密码学,数值分析,光学,几何以及其他的领域。稳定态逼近是渐
压缩感知是近年来所研究的一种关于信号传输的新的理论,信号的稀疏表示、编码测量和重构算法等构成了压缩感知理论主要的三个方面.信号的稀疏表示为压缩感知的先决条件,即满足