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

Trails,Paths and Cycles of Digraphs with α_(2)-stable Number 2

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

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

出　　处：《数学学报（中文版）》2024年第1期137-150,共14页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(12261016,11761071);新疆维吾尔自治区自然科学基金:杰出青年基金项目(2022D01E13)。

摘　　要：设α_(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是强迹连通的.Letα_(2-)(D)=max{|X|:X■V(D)and D[X]has no 2-cycle}be theα_(2-)(D)-stable number of a digraph D.In[Proc.London Math.Soc.,42(1981)231-251],Thomassen constructed non-hamiltonian digraphs D withκ(D)=α(D)to show that the well-known Chvatal-Erdos theorem does not have obvious extension to digraphs.Bang-Jensen and Thomasse conjectured that every digraph with arc strongconnectivity at least its stable number must have a spanning closed trail.The problem also remains unanswered whether a digraph with its arc strong-connectivity at least itsα_(2-)(D)-stable number has spanning trails or not.A digraph D is weakly trail-connected if for any two vertices x and y of D,D admits a spanning(x,y)-trail or a spanning(y,x)-trail,and is strongly trail-connected if for any two vertices x and y of D,D contains both a spanning(x,y)-trail and a spanning(y,x)-trail.We determine two well-characterized families of strong digraphs M and H,and prove each of the following for any strong digraph D withα_(2-)(D)=2:(ⅰ)D is hamiltonian if and only if D?M.(ⅱ)D is weakly trail-connected.(ⅲ)D is strongly trail-connected if and only if D?H.In particular,every strong digraph D withα_(2-)(D)=2 has a hamiltonian path and every 2-strong digraph D withα_(2-)(D)=2 is strongly trail-connected.

关 键 词：α_(2)(D)-独立集 哈密尔顿圈 弱迹连通 强迹连通 

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