3--连通且基本9--连通线图是哈密尔顿连通图

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

图的哈密尔顿性是结构图论的重要研究课题.该课题与著名的四色猜想密切相关.从计算复杂性角度看，判定一个图是否为哈密尔顿图是NP-困难的，所以对哈密尔顿问题的研究主要集中在给出判定图的哈密尔顿性的充分性条件.本文从图的结构上考虑，给出禁用子图条件.设H是图G的一个子图，如果G不含同构于H的导出子图，则称H为G的一个禁用子图，也称图G是H-free图.K1,3是最常用到的禁用子图之一，K1,3-free图亦称为无爪图.1984年Matthews和Sumner提出了下述著名猜想:任意4-连通无爪图都是哈密尔顿图.该猜想被连续研究了二十多年（参见文献[12]，[4][15]等），但是至今尚未得到证明.于是，Laietal.开始研究3-连通线图的哈密尔顿性，他在2006年证明了:任意3-连通，且基本11-连通线图是哈密尔顿图.Lietal.在2012年证明了:任意3-连通，且基本10-连通线图是哈密尔顿连通图.Lietal.之后提出存在最小的正整数k，满足:任意3-连通且基本k-连通线图是哈密尔顿图.本文证明了:任意3-连通，且基本9-连通线图是哈密尔顿连通图.该结果改进了Laietal.和Lietal.的相关工作.

著录项

作者
程胜利;
展开▼
作者单位

华中师范大学;

展开▼
授予单位华中师范大学;
学科运筹学与控制论
授予学位硕士
导师姓名李相文;
年度 2014
页码
总页数
原文格式 PDF
正文语种中文
中图分类制盐工业;远动技术;
关键词
连通; 线图;

相似文献

中文文献
外文文献
专利

1. 用基本集讨论k-连通图的Hamilton连通性 [J] . 徐新萍 ,周兴和 . 南京师大学报（自然科学版） . 1996,第001期
2. 哈密尔顿-连通图的拉普拉斯谱充分条件 [J] . 刘琦 ,叶淼林 . 安庆师范学院学报（自然科学版） . 2019,第003期
3. 哈密尔顿-连通图的拉普拉斯谱充分条件 [J] . 刘琦1 ,叶淼林1 . 安庆师范大学学报：自然科学版 . 2019,第003期
4. 2P-哈密尔顿二部连通图的能量条件 [J] . 徐弈 ,王礼想 ,舒阿秀 . 安庆师范大学学报：自然科学版 . 2019,第004期
5. 2P-哈密尔顿二部连通图的能量条件 [J] . 徐弈 ,王礼想 ,舒阿秀 . 安庆师范学院学报（自然科学版） . 2019,第004期
6. 带正权的无向连通图中最短路问题研究 [C] . . 中国运筹学会第九届学术交流会 . 2008
7. 局部哈密尔顿和局部哈密尔顿连通图的圈性质 [A] . 汤龙 . 2018

3--连通且基本9--连通线图是哈密尔顿连通图

目录

摘要

著录项

相似文献

相关主题

期刊订阅