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)2+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)2 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.
[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)
