局部内(外)半完全有向图可迹的充分条件

本文利用多重插入法,对局部内(外)半完全有向图及其扩张有向图的可迹性作了讨论.首先,证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}满足d(x)≥n-1,d(可)≥n-2,或d(x)≥n-2,d(y)≥n-1,则D是可迹的.同时还证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}有min{d~+(x)+d~-(y),d~-(x)+d~+(y)}≥n-1,D是可迹的.其次,证明了n阶连通的扩张局部内半完全有向图D,如果任意不相邻的控制点对{u,v}和任意不相邻的受控点对{x,y}同时满足(1)d(u)≥n-1,d(v)≥n-1;(2)d(x)≥n-1,d(y)≥n-2或d(x)≥n-2,d(y)≥n-1,则D是可迹的.最后,利用逆图的性质把这三个结论推广到n阶连通的局部外半完全有向图与n阶连通的扩张局部外半完全有向图中.