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

来源：应用数学学报杂志2016年第2期北京时间：

作者：原军, 刘爱霞

单位：1. 太原科技大学应用科学学院, 太原 030024;2. 山西大学数学科学学院, 太原 030006

摘要：本文利用多重插入法,对局部内(外)半完全有向图及其扩张有向图的可迹性作了讨论.首先,证明了对n阶连通的局部内半完全有向图D,若它中任意不相邻的受控点对{x,y}满足d(x)≥n-1, d(y)≥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阶连通的扩张局部外半完全有向图中.

关键词：Hamilton路,Hamilton圈,可迹性,局部内(外)半完全有向图,扩张的局部内(外)半完全有向图

基金资助：国家青年科学基金(61402317);数学天元基金(11126067);山西省自然科学基金(2012021001-2)资助项目.