首页 | 本学科首页   官方微博 | 高级检索  
     检索      

有向跳图的生成欧拉子有向图
引用本文:刘娟,杨洪,赖虹建,张新东.有向跳图的生成欧拉子有向图[J].数学研究及应用,2022,42(5):441-454.
作者姓名:刘娟  杨洪  赖虹建  张新东
作者单位:贵州财经大学大数据统计学院, 贵州 贵阳 550025;新疆大学数学与系统科学学院, 新疆 乌鲁木齐 830046;美国西弗吉尼亚大学数学系, 美国 摩根敦 26506;新疆师范大学数学科学学院, 新疆 乌鲁木齐 830017
基金项目:国家自然科学基金(Grant Nos.11761071; 11861068), 贵州省大数据统计分析重点实验室(Grant No.[2019]5103), 新疆维吾尔自治区自然科学基金(Grant No.2022D01E13).
摘    要:一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.

关 键 词:超欧拉有向图    有向线图    有向跳图    弱迹连通    强迹连通
收稿时间:2021/8/19 0:00:00
修稿时间:2022/2/19 0:00:00

Spanning Eulerian Subdigraphs in Jump Digraphs
Juan LIU,Hong YANG,Hongjian LAI,Xindong ZHANG.Spanning Eulerian Subdigraphs in Jump Digraphs[J].Journal of Mathematical Research with Applications,2022,42(5):441-454.
Authors:Juan LIU  Hong YANG  Hongjian LAI  Xindong ZHANG
Institution:College of Big Data Statistics, Guizhou University of Finance and Economics, Guizhou 550025, P. R. China;College of Mathematics and System Sciences, Xinjiang University, Xinjiang 830046, P. R. China;Department of Mathematics, West Virginia University, Morgantown 26506, USA; School of Mathematical Sciences, Xinjiang Normal University, Xinjiang 830017, P. R. China
Abstract:A jump digraph $J(D)$ of a directed multigraph $D$ has as its vertex set being $A(D)$, the set of arcs of $D$; where $(a,b)$ is an arc of $J(D)$ if and only if there are vertices $u_{1}, v_{1}, u_{2},v_{2}$ in $D$ such that $a=(u_{1},v_{1}),b=(u_{2},v_{2})$ and $v_{1}\not=u_{2}$. In this paper, we give a well characterized directed multigraph families $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$, and prove that a jump digraph $J(D)$ of a directed multigraph $D$ is strongly connected if and only if $D\not\in \mathcal{H}_{1}$. Specially, $J(D)$ is weakly connected if and only if $D\not\in \mathcal{H}_{2}$. The following results are obtained: (i) There exists a family $\mathcal{D}$ of well-characterized directed multigraphs such that strongly connected jump digraph $J(D)$ of directed multigraph is strongly trail-connected if and only if $D\not\in \mathcal{D}$. (ii) Every strongly connected jump digraph $J(D)$ of directed multigraph $D$ is weakly trail-connected, and so is supereulerian. (iii) Every weakly connected jump digraph $J(D)$ of directed multigraph $D$ has a spanning trail.
Keywords:supereulerian digraph  line digraph  jump digraph  weakly trail-connected  strongly  trail-connected
点击此处可从《数学研究及应用》浏览原始摘要信息
点击此处可从《数学研究及应用》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号