P3-支配图哈密尔顿性的两个充分条件

在文献[4]中作者引进P3-支配图,并研究了这类图的一些性质.设G是2-连通的P3-支配图,证明了G是哈密尔顿的两个充分条件fan型条件和禁止子图型条件.     

2-连通T3-受限图的Hamilton性

部分K1,3的一条边所得到的图记为T3,其中的3度顶点称为T3的中心.如果图G的任意一个同构于T3的导出子图,除中心以外的4个顶点之间的边数≥3,则称G为T3-受限图.本文主要证明:如果GF′,2-连通T3-受限图G含有Hamilton图.     

3—连通正则无爪图的Hamilton圈

证明了每一个3－连通k-正则无爪图G，当G的点数n≤5k-5时，G包含一个Hamilton圈。     

P3——支配图哈密尔顿性的一个充分条件

在文献[4]中作为半无爪图的一个超类,作者引进P3-支配图,并研究了这类图一些性质。设G是2-连通的P3-支配图,我们证明了G是哈密尔顿的一个充分条件局部连通型条件。     

一类无爪图的Hamilton圈

设ｖ是图Ｇ＝（Ｖ，Ｅ）的顶点，若存在顶点ｕ∈Ｖ－｛ｖ｝，使子图Ｇ［Ｎ（ｖ）∪｛ｕ｝中任意一对顶点的距离不超过３，则称ｖ是Ｇ的弱局部连通顶，点。设Ｇ是非平凡的连通无爪图，且它的任一顶点割均钫含一个弱局部连通顶点，则Ｇ包含Ｈａｍｉｌｔｏｎ圈。     

2-连通无爪Hamilton图的一个充分条件

本文证明了:设G是n阶2-连通无爪图,△(G)≥n-4,则G是Hamilton图。     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

2-连通[4,1]-图的Hamilton圈

如果G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了以下结果:2-连通[4,1]-图是Hamilton图的充要条件是它不同构于三类特殊的图.     

4－连通无爪图中的Hamilton圈

Ｍａｔｔｈｅｗｓ等猜想：每一个４－连通无爪图是Ｈ－图．本文证实当Ｇ不含局部连通点及３团时该猜想成立．     

2-连通无三角形图中的长圈

研究了2-连通无三角形图中长圈的存在性．     

2-连通［4,1］-图的Hamilton圈

如果G的任意s个点的导出子图中至少含有t条边,则称图G为［s, t］-图。本文证明了以下结果：2-连通［4,1］-图是Hamilton图的充要条件是它不同构于三类特殊的图。     

完全图K11及K12的边不相交的H圈的个数

给出了边矩阵及n-圈着色的定义。阐明了完全图K11的1因子分解及2因子分解的思路。证明了完全图Kv的2因子分解的定理。介绍了K11及K12的2因子分解的全过程。     

完全图K_(11)及K_(12)的边不相交的H圈的个数

给出了边矩阵及n-圈着色的定义。阐明了完全图K11的1因子分解及2因子分解的思路。证明了完全图Kv的2因子分解的定理。介绍了K11及K12的2因子分解的全过程。     

拟阵基图的Hamilton圈性质

设G是拟阵的基图,对于拟阵基图的哈密顿性质,证明了在简单拟阵的基图中,如果|V(G)|≥5并且拟阵的子拟阵基图不同构于W5,那么对于任意的两条边e与e’,存在包含e且不包含e’的Hamilton圈。     

关于Hamilton图充分性的一个注记

在两个关于Hamilton路和Hamilton圈的定理的基础上,推广得到一个Hamilton图的新的充分条件.熟知的Ore定理可直接从本文结论推出.     

Hamilton图中的H圈数

设Гk={G||E(G)|—|V(G)|=k且G是至少有3个顶点的H图}，Гn,k={G|G是阶为n≥3的图且|E(G)|—|V(G)|=k}，用，(G)表示图G的H圈数，令h(k)=max{f(G)|G∈Гk}和h(n，k)=max{f(G)|G∈Гn,k}，作者得到h(是)的上界和下界，并且当n为大于等于k的奇数以及k≤号 l时，确定了h(n，k)。     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

唯一2或3-列表染色图

文中对限制颜色总数的图作了进一步的研究.运用唯一列表染色的定义找出了非唯一2-列表可染图K5和K3,3,并运用独立集的定义给出了唯一3-列表可染图的一个充要条件:设G是2-连通的图,则G是唯一3-列表可染的当且仅当存在G的一独立集W,使得G\W既不是完全图,也不是完全二分图,也不是圈.