论文部分内容阅读
图论作为现代数学的一个重要分支，在电气网络，信息传输，城市规划等方面的应用越来越广泛，因为自然界和人类社会中有大量事物以及事物之间的关系，可以用图来描述．而路和圈作为图的两种基本结构，是分析和刻画图的有力工具，有许多的实际问题可以归结为图的路和圈问题，所以这方面一直是图论中的热点研究领域，其研究成果和进展可参见文献[1]-[4]．事实上，图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题．经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体．路的方面包括图的Hamilton-路(可迹性)，最长路，Hamilton连通，泛连通，路可扩等等；圈的方面包括图的Hamilton圈，最长圈，(点)泛圈，完全国可扩，点不交的圈，圈覆盖等等． 由于Hamilton问题是一个NPC问题，直接研究往往比较困难，于是人们转而研究不含有某些禁用子图的图类．继Beinekel968，1970年发表的关于线图性质的两篇文章[5]-[6]之后，人们开始关注包含着线图的无爪图．70年代末80年代初，是研究无爪图的一个非常活跃的时期．关于无爪图方面的部分优秀成果可参考[7]-[32]．另外，无爪图的概念也被从不同角度推广到了更大的图类，如半无爪图，几乎无爪图，(K1，4；2)-图，DCT图等．这方面的研究成果可参考[33]-[46]．2005年，刘春房在[47]中定义了一种新的图类-[s，t]-图，即任意s个点之间至少含有t条边，这类图的特点是其边的分布比较均匀，因而在交通网络，通信系统，计算机的网络配置等方面有着典型应用．目前，关于[s，t]-图路圈性质的研究也取得了不少成果，可参考文献[47]-[50]． 连通和局部连通是研究图的路圈性质的常用条件，在局部连通的概念提出之后，张存全在1989年提出了半局部连通的定义，并研究了无爪图在半局部连通条件下的一些性质．而后人们又相继提出了许多不同的相关定义，如：几乎局部连通，三角连通，2-阶邻域连通等．2008年刘明颖[51]提出了H-局部连通的概念，并初步讨论了K2-局部连通条件下无爪图和半无爪图的一些性质．本文正是以[s，t]-图中一类具有典型意义的图-[s，t]-图作为主要研究对象，探讨其在H-局部连通条件下的路圈性质．