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 NameAffiliation
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: 185
Download times: 239
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  Download reader