Spanning Eulerian Subdigraphs in Jump Digraphs |
Received:August 19, 2021 Revised:February 19, 2022 |
Key Words:
supereulerian digraph line digraph jump digraph weakly trail-connected strongly trail-connected
|
Fund Project:Supported by the National Natural Science Foundation of China (Grant Nos.11761071; 11861068), Guizhou Key Laboratory of Big Data Statistical Analysis, China (Grant No.[2019]5103) and the Natural Science Foundation of Xinjiang Uygur Autonomous Region (Grant No.2022D01E13). |
Author Name | Affiliation | Juan LIU | College of Big Data Statistics, Guizhou University of Finance and Economics, Guizhou 550025, P. R. China | Hong YANG | College of Mathematics and System Sciences, Xinjiang University, Xinjiang 830046, P. R. China | Hongjian LAI | Department of Mathematics, West Virginia University, Morgantown 26506, USA | Xindong ZHANG | School of Mathematical Sciences, Xinjiang Normal University, Xinjiang 830017, P. R. China |
|
Hits: 432 |
Download times: 410 |
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. |
Citation: |
DOI:10.3770/j.issn:2095-2651.2022.05.001 |
View Full Text View/Add Comment |
|
|
|