哈密尔顿连通的有向线图  

Hamiltonian-connected Line Digraphs

作　　者：刘娟 杨洪 赖虹建[3] 张新东[4] LIU Juan;YANG Hong;LAI Hongjian;ZHANG Xindong(College of Big Data Statistics,Guizhou University of Finance and Economics,Gruiyang,Guizhou,550025,P.R.China;College of Mathematics and System Sciences,Xinjiang University,Urumqi,Xinjiang,830046,P.R.China;Department of Mathematics,West Virginia University,Morgantown,WV 26506,USA;School of Mathematical Sciences,Xinjiang Normal University,Urumqi,Xinjiang,830017,P.R.China)

机构地区：[1]贵州财经大学大数据统计学院,贵州贵阳550025 [2]新疆大学数学与系统科学学院,新疆乌鲁木齐830046 [3]西弗吉尼亚大学数学系,美国西弗吉尼亚摩根敦26506 [4]新疆师范大学数学科学学院,新疆乌鲁木齐830017

出　　处：《数学进展》2023年第2期224-234,共11页Advances in Mathematics（China）

基　　金：Supported by NSFC(No.12261016);Natural Science Foundation of Xinjiang Uygur Autonomous Region(No.2022D01E13)。

摘　　要：设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′.

关 键 词：有向伪图 有向线图 弱哈密尔顿连通 强哈密尔顿连通 

分 类 号：O157.5[理学—数学]