连通无爪图的最长圈及其Hamilton性

来源 :山东大学 | 被引量 : 0次 | 上传用户:fendynx
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的Hamilton性是图的最基本的性质之一。图的Hamilton性与网络模型联系密切,使它拥有很强的应用背景,是图论中重要的研究课题之一。包含有限简单图G的每个顶点的圈称为Hamilton圈(Hamiltonian Cycle)。若图G的每两个顶点都由Hamilton路连接着,则图G称为Hamilton-连通图(Hamiltonian Connected Graph)。一个图若有Hamilton圈,则称这个图是Hamilton图。无爪图(Claw-free Graph)是不含有同构于K1.3的导出子图的图,无爪图是一个重要的图类。 图的最长圈是探讨图的Hamilton性的重要工具之一,对它们的研究具有重要的理论价值和应用价值。本文选择连通无爪图的最长圈作为研究对象,就是希望能够对进一步了解连通无爪图结构的研究工作有所帮助。本文主要研究3-连通无爪图的Hamilton性、4-连通无爪图的最长圈的性质以及Hamilton性。下面简单介绍一下本文的主要结果。 我们先介绍连通无爪图的周长及幅度的概念。 定义1图G的最长圈的长度,我们称为图G的周长,记为c(G)。 定义2图G为阶数为p的k连通无爪图,F={C|圈C是图G的最长圈},对任一C∈F,定义并记θ(G)=max{f(C)|C∈F},称θ(G)是图G的幅度。 我利用幅度的概念,得出了关于3-连通无爪图的Hamilton性和4-连通无爪图的最长圈及其Hamilton性的新结论。 结论1图G是阶数为n的3-连通无爪图,θ(G)为图G的幅度,当θ(G)≥1/3(n—δ+1)时,图G为Hamilton图。 结论34—连通非Hamilton无爪图G的周长:c(G)≥min{4θ(G)+δ,8δ}。 结论4设图G是阶数为n的4—连通无爪图,θ(G)为图G的幅度,圈C为图G的最长圈,若θ(G)<δ*且θ(G)≥1/4(n—2δ+5)时,图G为Hamilton图。 结论5设图G是阶数为n的4—连通无爪图,θ(G)为图G的幅度,圈C为图G的最长圈,R*=G—V(G)是图G的G—V(G)导出子图,R()R*是R*的一个连通分支,且|Nc(R)|=ι=4,当θ(G)≥1/4(n—2δ+4)时,图G为Hamilton图。
其他文献
现代科学技术的发展在很大程度上依赖于物理学、化学、和生物学等各科的成就和发展,而这些学科自身的精确化必须通过建立相应的数学模型来实现,而这些数学模型中有大量问题与偏
图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)任给
学位
图的连通性是图最基本的性质之一,是图论中重要的研究课题。连通图与网络模型和组合优化联系密切,使它具备很强的应用背景.随着计算机与网络的迅速发展,这一联系日益密切,使连通图
设X与Y是两个阶数为n与m的有限集,映射f:X→Y称为Hash函数,这样的N个Hash函数的集合称为(N;n,m)Hash函数族,记为F.如果对于X的任何一个w元子集W,Hash函数族F中至少存在一个函数
本文主要对离散生物动力系统和连续空间传染病模型进行了研究。具体内容安排如下: 第二章,研究了一类具有Beddington-DeAndelis功能性反应和捕食者互相残杀项的非自治离散捕
本文首先研究了完备的Douglas空间(M,F),证明了如果其Cartan张量是有界的,且满足H=0和Ejk·l|m=0,则F为Berwald度量,其中E为F的平均Berwald曲率,H为刻划E沿测地线的变化率的几何量
Sturmian序列在符号动力系统中起着很重要的作用,以及在组合学、遍历理论中,甚至在计算机科学理论、生物学和物理学等领域中也是如此。   由定义知:Sturmian序列是复杂度函数
随着经济建设和现代工业的迅速发展,城市大气环境污染日趋严重,城市大气环境质量直接影响人们的生存环境和社会经济的发展,因此越来越得到人们的重视。为了有效地治理城市大气环
图论是组合数学中的一个重要分支。在许多领域,诸如物理学、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理都有广泛的应用。矩阵A可以与它所对