α2-独立数为2的有向图中的迹,路和圈 |
| |
引用本文: | 张新东,杨洪,赖虹建,刘娟.α2-独立数为2的有向图中的迹,路和圈[J].数学学报,2024(1):137-150. |
| |
作者姓名: | 张新东 杨洪 赖虹建 刘娟 |
| |
作者单位: | 1. 贵州财经大学大数据统计学院;2. 新疆大学数学与系统科学学院;3. 西弗吉尼亚大学数学系 |
| |
基金项目: | 国家自然科学基金资助项目(12261016,11761071);;新疆维吾尔自治区自然科学基金:杰出青年基金项目(2022D01E13); |
| |
摘 要: | 设α2(D)=max{|X|:X?V(D)且DX]不含有向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是弱迹连通的.(...
|
关 键 词: | α2 (D)-独立集 哈密尔顿圈 弱迹连通 强迹连通 |
|
|