若干H-局部连通图的路和圈问题

摘要

路和圈是图的两种基本结构，是分析和刻画图的有力工具，有大量的实际问题可以归结为图的路和圈问题．所以图的路和圈问题是图论中一个十分重要而且活跃的研究课题．图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题．国内外许多学者对此问题作了大量的研究工作．这方面的研究成果和进展可参见文献[38][42]经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体．路的方面包括图的Hamilton路(可迹性)，齐次可迹性，最长路，Hamilton连通，泛连通，路可扩等等；圈的方面包括图的Hamilton圈，最长圈，(点)泛圈，完全圈可扩，点不交的圈，圈覆盖等等．
　　由于直接研究一般图的Hamilton问题往往比较困难，于是人们转而研究不含有某些禁用子图的图类．继Beineke1970年发表的关于线图性质的文章[17]之后，人们开始关注包含着线图的无爪图．70年代末80年代初，是研究无爪图的一个非常活跃的时期．关于无爪图方面的部分优秀成果可参考[2]-[4]，[19]-[31]．另外，无爪图的概念也被从不同角度推广到了更大的图类，半无爪图，几乎无爪图，(K1,4，2)-图等．2005年，刘春房在[8]中定义了一种新的图类[s，t]图，即任意s个点之间至少含有t条边．程建民在[s，t]图的基础上提出了强-[s，t]图[53]的概念，即任意s个点之间至少含有t条独立边．[s，t]图的特点是其边的分布比较均匀，因而在交通网络，通信系统，计算机的网络配置等方面有着很典型的应用．关于[s，t]图的研究成果可参见文献[8][10]．连通和局部连通是研究图的路圈性质的常用条件，在局部连通的概念提出之后，张存全在1989年提出了半局部连通的定义，并研究了无爪图在半局部连通条件下的一些性质．之后人们又相继提出了许多不同的相关定义，如：几乎局部连通，三角连通，2-阶邻域连通等．2008年刘明颖提出了H-局部连通图的概念，并初步讨论了K2-局部连通条件下无爪图的一些性质．本文在此基础上进一步研究若干种图类，如无爪图、(K1,4；2)-图、[5，3]图在H一局部连通条件之下的路圈性质．
　　在第一章中，我们主要介绍文章中所涉及的一些概念和术语符号，以及本文的研究背景和已有的一些结果．

目录

封面

声明

目录

中文摘要

英文摘要

第一章 预备知识

1.1 研究背景

1.2 符号概念介绍

1.3 已有结果

第二章 H-局部通条件下的（K1,4;2)-图

2.1 K3-局部连通（K1,4;2)-图的极短路

2.2 K2-局部连通（K1,4;2）-图的hamilton性

第三章 连通，P3-局部连通无爪图的1-2可扩性

第四章 连通、P3-局部连通[5,3]-图的圈可扩性

4.1 连通、P3-局部连通[5,3]-图的1-2可扩性

4.2 连通、P3-局部连通[5,3]-图的泛圈性

参考文献

致谢