s—Hamilton—连通图的一个充分条件

证明了下面的结论 :设G是n阶 (k+2 +s) 连通图 ,G 为G的部分平方图 ,k≥ 2 ,而 (a1,a2 ,… ,ak+ 1)是k LTW序列 .若对于每个X ∈Ik+ 1(G ) ,在G中有 k+ 1i=1aisi(X) >n +s,则G是s Hamilton 连通图     

竞赛图中Hamilton路数的矩阵求法

任一对不同顶点都相邻且无2-圈的有向图称为竞赛图.每个竞赛图都有Hamilton路,利用矩阵方法可求得计算竞赛图中的Hamilton路及Hamilton路数的方法,既为计算竞赛图的Hamilton路及Hamilton路数增加了一种新的计算途径,还可用来计算任意有向图的所有长为k有向路.     

关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。     

Hamilton图的一个注记

本文的主要结果是：设G是D－圈图,若存在某个t≤δ,使得对任何t＋1个点的独立集,X＝｛x0,x1,…,xz）,有,则G是Hamilton图。     

几乎Hamilton连通图和部分平方图

G为图,G6*是G的部分平方图,运用（k 2)连通图（k≥2）上的插点技术,借助LTW序列对G6*中独立集的邻域交加权,证明了图G是几乎Hamilton连通的一些充分条件。     

Hamilton图的矩阵变换判别法

利用图的邻接矩阵与一种特殊矩阵置换相似的关系判别图中Hamilton圈(路)的存在情况。首先对于不完全图的无向图和有向图进行分析,给出不完全图和完全图存在Hamilton圈(路)的充分必要条件,然后得出了竞赛图寻找Hamilton圈(路)的简单方法。     

部分平方图的独立集和1-几乎Hamilton性

借助于部分平方图独立集讨论了图的1-几乎Hamilton性，得到G是1-几乎Hamilton图的一个充分条件．     

一类Hamilton图

若P[u,v]是2连通无爪图G的最长路,设dp(xβ,xα)=︱P[xβ,xα]︱-1(xβ相似文献   

爪心独立图中有Hamilton—路的一个充分条件

证明了下面的结论：设Ｇ是（ｋ－１）－连通爪心独立图，若对于每个Ｚ∈Ｉｋ＋１（Ｇ），在Ｇ中有∑／ｘ∈ｚｄ（ｚ）≥（Ｚ）＋ｋ，则Ｇ中含Ｈａｍｉｌｔｏｎ－路。     

图的控制数与其补图覆盖数的关系

本文研究了图的控制数、边控制数与其补图覆盖数间的关系．获得了某些重要不等式，且均为界可达。     

k-连通无爪图中的生成圈和控制圈

用张存铨在文[2]中的方法!本文通过疏远边的度和给出k-连通无瓜图中存在汉密尔顿圈和控制圈的充分条件,作为文中定理的推论,证明了若对任意■∈E(G) d(k)+d(v)≥3n/k-6,则G有汉密尔顿圈;若对任意■∈E(G) d(k)+d(v)≥3n/(k+1)-3,则G有控制圈,这里G是k-连通无爪图。     

完全图的Hamilton圈分解

在文[3]中,Hoffman等证明了完全图Kn中最多边不交的Hamilton圈个数为「n-1/2」.然而根据文[3]中的证明方法,要具体表示出这「n-1/2」个边不相交Hamilton圈是非常困难的.文章给出了完全图的Harailton圈分解的一种简便方法.     

控制迹与线图的泛圈性

设u与v是圈G中的两个任意给定的顶点,本文给出图中存在连接u和v的控制迹的一个充分条件.若图G的阶n≥5,又对一切xy∈B(G)都有d(x) d(y)≥n,本文证明线图L(G)是点泛圈的,且可使得与任一点关连的各个图几乎一个套一个,即几乎是可扩充的.     

循环图及单圈图的有效控制集与完美控制集

图的完美控制集和有效控制集是两类特殊的控制集．通常要判断一个图是否存在有效控制集是困难的．该文证明了无向循环图一定存在有效控制集．此外，给出了单圈图的完美控制数与其阶数的关系．     

含有两个分离三角形的极大平图有一个Hamilton路

一个图若包含Hamilton圈，则这个图是Hamilton图．Whitney已经证明了没有分离三角形的极大平图是Hamilton图．一个三角形若删去其顶点后使图不连通，则这个三角形称为分离三角形。Chuiyuan Chen证明了仅含有一个分离三角形的极大平图仍然是Hamilton图，我们将证明含有两个分离三角形的极大平图有一个Hamilton路。     

有向线图存在Hamilton圈和Hamilton路的一个充要条件

有向图D的有向线图是以A（D）为顶点集，弧集为{（xy，yz），xy∈A（D），yz∈A（D）}的有向图，用L（D）表示D的有向线图。文章证明了连通有向线图存在Hamilton圈当且仅当它有圈因子；连通有向线图存在Hamilton路当且仅当它有1-路圈因子。     

Hamilton图的充要条件及圈的矩阵算法

利用矩阵方法得到了一个简单无向图为H am ilton图的充要条件等一些结论以及圈的矩阵算法.一个n阶简单无向图是H am ilton图的充要条件是其n阶长路矩阵是一个对角线元素全不为0的对角阵,且对角线上每一个元素均为H am ilton圈之和.     

最小最大路划分的一个启发式算法

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.