α_(2-)独立数为2的有向图中的迹,路和圈

设α_(2-)(D)=max{|X|:X■V(D)且D[X]不含有向2-圈}是有向图D的α_(2-)(D)-独立数.在文献[Proc.London Math.Soc.,42(1981)231-251]中,Thomassen构造了满足κ(D)=α(D)的非哈密尔顿有向图D,以此证明Chvátal-Erdös定理在有向图情形下不能得到自然推广.Bang-Jensen和Thomassé提出如下猜想:每一个满足弧强连通度大于等于其独立数的有向图一定包含生成闭迹.对于满足弧强连通度大于等于其α_(2-)(D)-独立数的有向图是否包含生成迹这一问题,目前仍未解决.如果对于D中的任意两个顶点x和y,D包含生成(x,y)-迹,或者生成(y,x)-迹,则称有向图D是弱迹连通的.如果对于D中的任意两个顶点x和y,D既包含生成(x,y)-迹又包含生成(y,x)-迹,则称D是强迹连通的.本文在确定两个强连通有向图类M和H的基础上,研究了在满足α_(2-)(D)=2条件下,有向图D的相关结果,并得到以下结论:(ⅰ)D是哈密尔顿的当且仅当D■M.(ⅱ)D是弱迹连通的.(ⅲ)D是强迹连通的当且仅当D?H.特别地,每一个满足α_(2-)(D)=2的强连通有向图D包含哈密尔顿路,并且每一个满足α_(2-)(D)=2的2-强连通有向图D是强迹连通的.

关于无爪图的哈密尔顿性的一个充分条件

设 G是阶为 n,连通度为 k(k≥ 2 )的无 K1 ,k+2 图。本文证明了 :对于任意 2 -独立集 ,S={ u,v,w} ,或者 d(u) +d(v) +d(w)≥n+k,或者 S中存在 x和 y(x≠ y) ,使得 λxy≥min{ α2xy,t2xy+1 } ,则 G是哈密尔顿的。