关于赋权图中重圈的一个范型定理

论文摘要

设G=（V,E;ω）为赋权图,定义G中点v的权度dGω（v）为G中与v相关联的所有边的权和,图G中圈的权值定义为圈中所有边的权和。范更华[7]中证明了下述众所周知的结论:设G是n阶2-连通图,c是满足3≤c≤n的一个整数。如果对任意的u,v∈V（G）, d（u,v）=2（?）max{d（u）,d（v）}≥c/2, 那么G中存在哈密尔顿圈或者存在一个长度至少为c的圈。Bedrossian等人[1]和Zhang等人[12]中分别将上述范定理进行了推广。本文将范定理更进一步推广为: 假设G是满足下述条件的2-连通赋权图, （1） 对G中每一个与K1,3同构的导出子图T,T中所有边的权都相等; （2） 对G中每一个与K1,3+e同构的导出子图T,T中所有边的权都相等; （3） 对G中每一个与K1,3或者与K1,3+e同构的导出子图T, min{max{dGω（x）,dGω（y）}:d（x,y）=2,x,y∈V（T）}≥c/2。 那么,G中存在哈密尔顿圈或者存在一个权值至少为c的圈。 此外,我们还证明了该定理中的条件（1）和（2）是不能被减弱为条件（1）或条件（2）的。

论文目录

• 摘要
• Abstract
• 第一节 引言
• 1.1 研究背景和现状
• 1.2 定义
• 1.3 已知结论
• 1.4 主要结论
• 第二节 结构引理
• 2.1 引理1
• 2.2 引理2
• 第三节 主要结论的证明
• 3.1 引理3
• 3.2 定理4的证明
• 第四节 主要结论的最好可能性
• 第五节 后记
• 参考文献
• 致谢