Spanning Eulerian Subdigraph in Line Digraphs

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)|\geqslant (|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 $\mathcal {M}$ such that if D is strong with $|A(D)|\leqslant |V(D)|+2$, then L(D) is supereulerian if and only if $D\not \in \mathcal {M}$.

Keywords

Supereulerian digraph / Line digraph / t-q-path-cycle cover / Dense digraph / Sparse digraph / 05C20 / 05C76

References

[1] AignerM. On the line graph of a directed graph. Math. Z., 1967, 102(1): 56-61

[2] AlgefariMJ, AlsatamiKA, LaiH-J, LiuJ. Supereulerian digraphs with given local structures. Inf. Process. Lett., 2016, 116(5): 321-326

[3] AlgefariMJ, LaiH-J. Supereulerian digraphs with large arc-strong connectivity. J. Graph Theory, 2016, 81(4): 393-402

[4] AlgefariMJ, LaiH-J, XuJQ. Locally dense supereulerian digraphs. Discrete Appl. Math., 2018, 238: 24-31

[5] AlsatamiKA, ZhangXD, LiuJ, LaiH-J. On a class of supereulerian digraphs. Appl. Math., 2016, 7(3): 320-326

[6] Bang-JensenJ, DéprésH, YeoA. Spanning eulerian subdigraphs avoiding $k$ prescribed arcs in tournaments. Discrete Math., 2020, 34312112129

[7] Bang-JensenJ, GutinGDigraphs: Theory, Algorithms and Applications, 20092London. Springer-Verlag.

[8] Bang-JensenJ, MaddaloniA. Sufficient conditions for a digraph to be supereulerian. J. Graph Theory, 2015, 79(1): 8-20

[9] BoeschFT, SuffelC, TindellR. The spanning subgraphs of eulerian graphs. J. Graph Theory, 1977, 1(1): 79-84

[10] BondyJA, MurtyUSRGraph Theory, 2008, New York. Springer-Verlag.

[11] CatlinPA. A reduction method to find spanning Eulerian subgraphs. J. Graph Theory, 1988, 12(1): 29-44

[12] CatlinPA. Supereulerian graphs: a survey. J. Graph Theory, 1992, 16(2): 177-196

[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] GutinG. Connected $(g;f)$-factors and supereulerian digraphs. Ars Combin., 2000, 54: 311-317

[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] HongYM, LaiH-J, LiuQH. Supereulerian digraphs. Discrete Math., 2014, 330(6): 87-95

[18] HongYM, LiuQH, LaiH-J. Ore-type degree condition of supereulerian digraphs. Discrete Math., 2016, 339(8): 2042-2050

[19] HuangY, HeW, HuangG, LaiH-J, SongS. A characterization of graphs with supereulerian line graphs. Int. J. Comput. Math. Comput. Syst. Theory, 2020, 5: 1-14

[20] LaiH-J, ShaoY, YanH. An update on supereulerian graphs. WSEAS Transactions on Mathematics, 2013, 12: 926-940

[21] LiuJ, LasfarO, WeiJ, ZhangXD, LaiH-J. Matching and spanning trails in digraphs. Discrete Appl. Math., 2021, 304: 417-433

[22] LiuJ, YangH, LaiH-J, ZhangXD. Symmetric core and spanning trails in directed networks. Discrete Math., 2021, 344112584

[23] LiuJ, YangH, ZhangXD, LaiH-J. Hamiltonian-connected line digraphs.. Adv. Math., 2023, 52: 224-234

[24] ZhangXD, LiuJ, WangL, LaiH-J. Supereulerian bipartite digraphs. J. Graph Theory, 2018, 89(1): 64-75

Funding

NSFC(12261016)

RIGHTS & PERMISSIONS

Shanghai University

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.