Spanning Eulerian Subdigraph in Line Digraphs

doi:10.1007/s42967-025-00505-2

Communications on Applied Mathematics and Computation ›› 2026, Vol. 8 ›› Issue (4): 1393-1419.doi: 10.1007/s42967-025-00505-2

Spanning Eulerian Subdigraph in Line Digraphs

Juan Liu¹, Hong Yang², Xindong Zhang¹, Hong-Jian Lai^3,4

1. College of Big Data Statistics, Guizhou University of Finance and Economics, Guiyang, 550025, Guizhou, China;
2. School of Mathematical Sciences, Guizhou Normal University, Guiyang, 550025, Guizhou, China;
3. School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou, 510665, Guangdong, China;
4. Department of Mathematics, West Virginia University, Morgantown, 26506, WV, USA

收稿日期:2025-01-23 修回日期:2025-05-09 接受日期:2025-05-21 出版日期:2026-08-20 发布日期:2026-09-17
通讯作者: Juan Liu, Email: liujuan1999@126.com E-mail:liujuan1999@126.com
基金资助:
The first author was supported by the Guizhou University of Finance and Economics Innovation Exploration and Academic Emerging Project, China (No. 2024XSXMA05) and the first and third authors were supported by the NSFC (No. 12261016).

Spanning Eulerian Subdigraph in Line Digraphs

Juan Liu¹, Hong Yang², Xindong Zhang¹, Hong-Jian Lai^3,4

1. College of Big Data Statistics, Guizhou University of Finance and Economics, Guiyang, 550025, Guizhou, China;
2. School of Mathematical Sciences, Guizhou Normal University, Guiyang, 550025, Guizhou, China;
3. School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou, 510665, Guangdong, China;
4. Department of Mathematics, West Virginia University, Morgantown, 26506, WV, USA

Received:2025-01-23 Revised:2025-05-09 Accepted:2025-05-21 Online:2026-08-20 Published:2026-09-17
Supported by:
The first author was supported by the Guizhou University of Finance and Economics Innovation Exploration and Academic Emerging Project, China (No. 2024XSXMA05) and the first and third authors were supported by the NSFC (No. 12261016).

摘要/Abstract

摘要： A line digraph L(D) of a directed multigraph D=(V(D),A(D)) has as its vertex-set being A(D), the set of arcs of D, where (a, b) is an arc of L(D) if and only if there are vertices u, v, and w in D such that a=(u,v) and b=(v,w) are in A(D). In this paper, we obtain sufficient and necessary conditions for a line digraph L(D) to be supereulerian and to have a spanning trail, respectively, in terms of certain types of path-cycle covers of D. These results will be applied to show each of the following for a digraph D. (i)If |A(D)| ≥ (|V(D)|-1)²+1, then L(D) is supereulerian. The lower bound on |A(D)| is best possible in the sense that there exists an infinite family of digraphs each of which satisfies |A(D)| = (|V(D)|-1)² without a supereulerian line digraph. (ii) There exists a well-characterized digraph family M such that if D is strong with |A(D)| ≤ |V(D)|+2, then L(D) is supereulerian if and only if D ∉ M.

关键词: Supereulerian digraph, Line digraph, t-q-path-cycle cover, Dense digraph, Sparse digraph

Abstract: A line digraph L(D) of a directed multigraph D=(V(D),A(D)) has as its vertex-set being A(D), the set of arcs of D, where (a, b) is an arc of L(D) if and only if there are vertices u, v, and w in D such that a=(u,v) and b=(v,w) are in A(D). In this paper, we obtain sufficient and necessary conditions for a line digraph L(D) to be supereulerian and to have a spanning trail, respectively, in terms of certain types of path-cycle covers of D. These results will be applied to show each of the following for a digraph D. (i)If |A(D)| ≥ (|V(D)|-1)²+1, then L(D) is supereulerian. The lower bound on |A(D)| is best possible in the sense that there exists an infinite family of digraphs each of which satisfies |A(D)| = (|V(D)|-1)² without a supereulerian line digraph. (ii) There exists a well-characterized digraph family M such that if D is strong with |A(D)| ≤ |V(D)|+2, then L(D) is supereulerian if and only if D ∉ M.

Key words: Supereulerian digraph, Line digraph, t-q-path-cycle cover, Dense digraph, Sparse digraph

Juan Liu, Hong Yang, Xindong Zhang, Hong-Jian Lai. Spanning Eulerian Subdigraph in Line Digraphs[J]. Communications on Applied Mathematics and Computation, 2026, 8(4): 1393-1419.

[1] Aigner, M.: On the line graph of a directed graph. Math. Z. 102(1), 56-61 (1967)
[2] Algefari, M.J., Alsatami, K.A., Lai, H.-J., Liu, J.: Supereulerian digraphs with given local structures. Inf. Process. Lett. 116(5), 321-326 (2016)
[3] Algefari, M.J., Lai, H.-J.: Supereulerian digraphs with large arc-strong connectivity. J. Graph Theory 81(4), 393-402 (2016)
[4] Algefari, M.J., Lai, H.-J., Xu, J.Q.: Locally dense supereulerian digraphs. Discrete Appl. Math. 238, 24-31 (2018)
[5] Alsatami, K.A., Zhang, X.D., Liu, J., Lai, H.-J.: On a class of supereulerian digraphs. Appl. Math. 7(3), 320-326 (2016)
[6] Bang-Jensen, J., Déprés, H., Yeo, A.: Spanning eulerian subdigraphs avoiding k prescribed arcs in tournaments. Discrete Math. 343(12), 112129 (2020)
[7] Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer-Verlag, London (2009)
[8] Bang-Jensen, J., Maddaloni, A.: Sufficient conditions for a digraph to be supereulerian. J. Graph Theory 79(1), 8-20 (2015)
[9] Boesch, F.T., Suffel, C., Tindell, R.: The spanning subgraphs of eulerian graphs. J. Graph Theory 1(1), 79-84 (1977)
[10] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer-Verlag, New York (2008)
[11] Catlin, P.A.: A reduction method to find spanning Eulerian subgraphs. J. Graph Theory 12(1), 29-44 (1988)
[12] Catlin, P.A.: Supereulerian graphs: a survey. J. Graph Theory 16(2), 177-196 (1992)
[13] Chen, Z.H., Lai, H.-J.: Reduction techniques for super-Eulerian graphs and related topics-a survey. In: Ku, T.-H. (ed) Combinatorics and Graph Theory’ 95, Vol. 1, pp. 53-69. World Scientific Publishing, Singapore, New Jersey, London, Hong Kong (1995)
[14] Gutin, G.: Cycles and paths in directed graphs, PhD thesis. School of Mathematics, Tel Aviv University, (1993)
[15] Gutin, G.: Connected (g;f)-factors and supereulerian digraphs. Ars Combin. 54, 311-317 (2000)
[16] Harary, F., Nash-Williams, C.St.J.A.: On eulerian and hamiltonian graphs and line graphs. Can. Math. Bull. 8(6), 701-710 (1965)
[17] Hong, Y.M., Lai, H.-J., Liu, Q.H.: Supereulerian digraphs. Discrete Math. 330(6), 87-95 (2014)
[18] Hong, Y.M., Liu, Q.H., Lai, H.-J.: Ore-type degree condition of supereulerian digraphs. Discrete Math. 339(8), 2042-2050 (2016)
[19] Huang, Y., He, W., Huang, G., Lai, H.-J., Song, S.: A characterization of graphs with supereulerian line graphs. Int. J. Comput. Math. Comput. Syst. Theory 5, 1-14 (2020)
[20] Lai, H.-J., Shao, Y., Yan, H.: An update on supereulerian graphs. WSEAS Transactions on Mathematics 12, 926-940 (2013)
[21] Liu, J., Lasfar, O., Wei, J., Zhang, X.D., Lai, H.-J.: Matching and spanning trails in digraphs. Discrete Appl. Math. 304, 417-433 (2021)
[22] Liu, J., Yang, H., Lai, H.-J., Zhang, X.D.: Symmetric core and spanning trails in directed networks. Discrete Math. 344, 112584 (2021)
[23] Liu, J., Yang, H., Zhang, X.D., Lai, H.-J.: Hamiltonian-connected line digraphs. Adv. Math. 52, 224-234 (2023)
[24] Zhang, X.D., Liu, J., Wang, L., Lai, H.-J.: Supereulerian bipartite digraphs. J. Graph Theory 89(1), 64-75 (2018)

Spanning Eulerian Subdigraph in Line Digraphs

Spanning Eulerian Subdigraph in Line Digraphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 0

编辑推荐

Metrics

本文评价