哈密尔顿连通的有向线图

Hamiltonian-connected Line Digraphs

设D是一个有向伪图,如果对于任意两个点u和v,D有一条生成(u,v)-路或一条生成(v,u)-路,则D是弱哈密尔顿连通的;若既存在一条生成(u,v)-路又存在一条生成(v,u)-路,则D是强哈密尔顿连通的.一个有向伪图D的线图L(D)是D的弧集作为其点集,对于任意两个点a,b∈A(D),(a,b)是L(D)的弧当且仅当存在D中的点u,v,w满足a=(u,v)并且b=(v,w).本文刻画了两类有向伪图T及T’,使得L(D)是弱哈密尔顿连通的当且仅当D∈T,并且L(D)是强哈密尔顿连通的当且仅当D∈T’.

Let D be a directed pseudograph,if for any two vertices u and,D admits a spanning(u,v)-path or a spanning(v,u)-path,then D is weakly Hamiltonian-connected;and if there are both a spanning(u,v)-path and a spanning(u,u)-path,then D is strongly Hamiltonian-connected.The line digraph L(D)of a directed pseudograph D has as its vertex set the family of arcs of D,where for any a,b e A(D),(a,b)is an arc of L(D)if and only if there are vertices u,v,w in D with a=(u,v)and b=(u,w).In this paper,we determine families T and T′ of well-characterized directed pseudographs such that L(D)is weakly Hamiltonianconnected if and only if D∈T,and L(D)is strongly Hamiltonian-connected if and only if D∈T′.