检索结果-南通市图书馆

作者：李凌云山东大学

学位级别：硕士

图的Hamilton性是图的最基本的性质之一。图的Hamilton性与网络模型联系密切,使它拥有很强的应用背景,是图论中重要的研究课题之一。包含有限简单图G的每个顶点的圈称为Hamilton圈(Hamiltonian Cycle)。若图G的每两个顶点都由Hamilton... 详细信息

图的Hamilton性是图的最基本的性质之一。图的Hamilton性与网络模型联系密切,使它拥有很强的应用背景,是图论中重要的研究课题之一。包含有限简单图G的每个顶点的圈称为Hamilton圈(Hamiltonian Cycle)。若图G的每两个顶点都由Hamilton路连接着,则图G称为Hamilton-连通图(HamiltonianConnected Graph)。一个图若有Hamilton圈,则称这个图是Hamilton图。无爪图(Claw-free Graph)是不含有同构于K的导出子图的图,无爪图是一个重要的图类。图的最长圈是探讨图的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图。结论2设图G为4-连通非Hamilton无爪图,圈C为图G的最长圈,R=G-V(G)是图G的导出子图,R(?)R是R的一个连通分支。u∈R,且N(u)≠(?),设a∈N(u),N(a)∩(a,a)={x,x,x,…x},N(a)∩(a,a)={y,y,…y},N(a)∩(a,a)={z,z,…z},N(a)∩(a,a)={r,r,…r},若下列条件之一成立:(1)x＞y;(2)x＞z;(3)x＞z;(4)yμ)＞z;(5)yμ)＞r;(6)zν)＞r,则|(a,a)|≥(?)|N(a)∩(a,a)|+l+1,其中下标取值:当i+j＞4时,值为i+j-4,i,j=1,2,3,4;l=min{|P(u,u)||i=1,2,3,4}。设N(a)∩(a,a)={ξ,ξ,ξ,…ξ},N(a)∩(a,a)={η,η,…η},N(a)∩(a,a)={ζ,ζ,…ζ},N(a)∩(a,a)={ρ,ρ,…ρ},以上结果对a,其中i=1,2,3,4,亦成立。结论3 4-连通非Hamilton无爪图G的周长:c(G)≥min(4θ(G)+δ,8δ)。结论4设图G是阶数为n的4-连通无爪图,θ(G)为图G的幅度,圈C为图G的最长圈,若θ(G)图G为Hamilton图。结论5设图G是阶数为n的4-连通无爪图,θ(G)为图G的幅度,圈C为图G的最长圈,R=G-V(G)是图G的G-V(G)导出子图,R(?)R是R的一个连通分支,且|N(R)|=l=4,当θ(G)≥1/4(n-2δ+4)时,图G为Hamilton图。

关键词：连通无爪图最长圈 Hamilton性幅度

来源：