Hamiltonian二部竞赛图

设 T(n,n)表示 n×n 二部竞赛图。本文证明了:如果 uv 是 T(n,n)的一条弧,蕴含d^-(u)+d^+(v)≥n-2≥4,则 T(n,n)是 Hamilton 图,除非 T(n,n)属于两类已被刻划的特殊图类。

关于竞赛图的弧k-反回路性质

设T=(,A)提一个竞赛图。=p称T具有p_k(p＇_k)性质,若xy∈A,T中存在一条长度为k-1的y-x路(X-Y路),其中2≤k<p.称T具有强路连通性,若对x,y∈,T中存在长度为k的x-y路(k=d,d+1,…,p-1其中d=d_r(x,y)是x到y距离)。在文献[1][2]中提出如下猜想:p个顶点的竞赛图T=(,A)具有强路连通性的充要条件是T具有p＇_2与p＇_(p-1)性质。本文证明了:若T具有p＇_2与p＇_(p-1)的性质,则T具有p＇_(p-2)性质。