论文部分内容阅读
图的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图。