Note on Faudree-Schelp Theorem in Path Connected Graphs and Ore Theorem in Hamilton Connected Graphs

In this note more short proofs are given for Faudree-Schelp theorem and Ore theorem.

(g,f)-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE (mg,mf)-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.

2-连通[5,3]-图中的Hamilton圈

如果G中任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.证明了若G是顶点数不小于8且δ(G)≥3的2-连通[5,3]-图,则G含有Hamilton圈.

拟阵基图的1 Hamilton 性质(英文)

研究了拟阵基图的１Ｈａｍｉｌｔｏｎ 性质，证明了基图或者是１Ｈａｍｉｌｔｏｎ 连通的，或者是一个超方体，或者与Ｋ２ ×Ｋ３ 和５ 轮Ｗ５ 中之一同构．

具有二分划(A_1,A_2)的二连通偶图的(A_1,A_2)Hamilton连通性

给出了具有二分划（ Ａ１ ，Ａ２）ｎ 阶２ 连通偶图Ｇ（ Ａ１ ，Ａ２） ，当 Ａ１ ＝ Ａ２ 时为（ Ａ１ ，Ａ２）Ｈａｍｉｌｔｏｎ 连通的定义·采用反证法，将图Ｇ（ Ａ１ ，Ａ２） 分为若干情况，利用图Ｇ（ Ａ１ ，Ａ２） 的２ 连通性及 Ａ１ ＝ Ａ２ ，证明了若ｎ≤４δ－ ２ ，则Ｇ（ Ａ１ ，Ａ２） 是（ Ａ１ ，Ａ２）Ｈａｍｉｌｔｏｎ 连通的·

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1 设G是2连通的(k,k+1)图,并且k≥V(G)3+13,如果G是偶数阶的图,则G是Hamilton图.定理2 设G是(k,k+2)图,并且k≥n3+103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.

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

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

一个充分条件和Hamilton连通图

考虑条件:n阶图G的任3个互不相邻的点u、v、w,HN=min{|N(u)∪N(v)|+d(w),|N(v)∪N(w)|+d(u),|N(w)∪N(u)|+d(v)}≥n.显然,这是一个改进和统一Dirac(δ≥n/2)和Ore(Ore≥n)这两个哈密尔顿图经典条件的条件.此外,HN≥n也包含领域并条件NC+δ≥n.文中研究了HN≥n的哈密尔顿图性、哈密尔顿连通图性,得到(I):2连通n阶图G,HN≥n则G是哈密尔顿图;(II):2连通n阶图G,HN≥n则G是哈密尔顿连通图或例外图.

(k+1)-连通无爪图的Hamilton-连通性

一个图若不含与Ｋ１．３同构的导出子图，则称它为无爪图。本文利用Ｔ－插点方法，得到（ｋ＋１）－连通无爪图是Ｈａｍｉｌｔｏｎ－连通的两个充分条件．（１）设Ｇ是（ｋ＋１）－连通无爪图（ｋ２），若对每个Ｘ∈Ｉｋ＋１（Ｇ），有ｓ２（Ｘ）＞１，则Ｇ是Ｈａｍｉｌｔｏｎ－连通图．（２）设Ｇ是（ｋ＋１）－连通无爪图（ｋ２），若对每个Ｘ∈Ｉｋ＋１（Ｇ），有∑ｘ∈Ｘｄ（ｘ）ｎ（Ｘ）－ｋ＋１，则Ｇ是Ｈａｍｉｌｔｏｎ－连通图．

图为Hamilton连通的邻域并或Fan型条件

图为Ｈａｍｉｌｔｏｎ连通的邻域并或Ｆａｎ型条件顾国华，孙学红（东南大学数学力学系南京２１００１８）（南京气象学院南京２１００４４）１定义与基本定理在文［１］中，Ａ，Ｂｅｎｈｏｃｉｎｅ，和Ａ．Ｐ．Ｗｏｊｄａ，证明了ｎ阶３连通图Ｇ，若任意两个距离为２的顶...

γ-klee-图的Hamilton-连通性和着色(英文)

一个r-klee-图递归定义为一个r+1阶完全图或者通过用一个r阶完全图替换已知的r-klee-图G′中的一个顶点所得到的图.本文主要研究了r-klee-图的Hamilton-连通性和着色问题.我们证明了:每一个r-klee-图是Hamilton-连通的和它的色数是r;如果r是奇数,则它的边色数是r;如果r是偶数,则它的边色数是r+1.

Hamilton连通性和邻域并条件

设 G =( V,E)为简单图 ,δ为图 G的最小度 ,1 987年 Faudree等人给出 N C=min{| N( x)∪ N ( y)‖ x,y∈ V( G) ,xy∈ N ( G) },有关文献曾研究 3连通的 H连通图 ,本文进一步得到 :若 G是 n阶 2连通图 ,且 N C≥ n -δ,则 G除几个图外均是H连通图 .从而 ,完成了邻域并条件的

Hamilton群上的Cayley图的Hamilton路

本文考虑Ｌｏｖａｓｚ猜想的特殊情形：Ｈａｍｉｌｔｏｎ群上的Ｃａｙｌｅｙ图。证明了有限Ｈａｍｉｌｔｏｎ群Ｆ上连通的Ｃａｙｌｅｙ图Ｇ（Ｆ，Ｓ）具有以任意顶点为起点的Ｈａｍｉｌｔｏｎ路。

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

半无爪图的概念是Ainouche首先引进的,它是包含无爪图的更大图类．本文得到3-连通半无爪图的下列结果:若G是3-连通的半无爪图,其阶为n,则n当不超过5δ—4,G是Hamil-ton图,它是无爪图有关结果的推广．

树图的1-Hamilton连通性(英文)

一阶数≥3的简单连通图叫做1-Hamilton连通的,若对每一对顶点v_1、v_2及任一边v_2v_3(v_1≠v_3),存在连接v_1和v_2,并且经过v_3v_2的Hamilton路.本文中我们证明:连通图的树图或是1-Hamilton连通的,或为一超立方体,或同构于K_2×K_3和W_5之一.

4限制边连通二部图的充分条件

设G是一个4限制边连通图,主要研究含有(4,4)-距离点集对的4限制边连通二部图的最优性.

满足邻集交和点度和的图的Hamilton性质

结合关于独立数的邻域交条件,给出了图G为Hamilton图的关于最小度的新度和条件,并且证明了在此种条件下3连通图G是Hamilton连通的。

Hamiltonian连通图的一个范－型条件

在一个图Ｇ中，对于两个不相邻点ｕ，ｖ，用α（ｕ，ｖ）表示包含ｕ和ｖ的最大独立集的个数．本文证明了：如果Ｇ是一个包含ｎ个顶点的３－连通图，对于Ｇ中每一对满足１≤｜Ｎ（ｕ）∩Ｎ（ｖ）｜≤α（ｕ，ｖ）－１的不相邻顶点ｕ，ｖ有ｍａｘ｛ｄ（ｕ），ｄ（ｖ）｝≥ｎ＋１２。

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

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

3-连通[5,3]-图的Hamilton性

如果一个图的任意s阶导出子图中至少含有t条边,则称这个图为[s,t]-图.用G3表示任意3阶图,证明了3-连通[5,3]-图是Hamilton图或者同构于-K4∨G3.