Spanning Eulerian Subdigraph in Line Digraphs

Abstract

A line digraph L(D) of a directed multigraph

D=(V(D),A(D))

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$D=(V(D),A(D))$$\end{document}

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)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$a=(u,v)$$\end{document}

and

b=(v,w)

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$b=(v,w)$$\end{document}

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

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$|A(D)|\geqslant (|V(D)|-1)^2+1$$\end{document}

, 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

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$|A(D)| = (|V(D)|-1)^2$$\end{document}

without a supereulerian line digraph. (ii) There exists a well-characterized digraph family

\mathcal{M}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\mathcal {M}$$\end{document}

such that if D is strong with

|A(D)|⩽|V(D)|+2

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$|A(D)|\leqslant |V(D)|+2$$\end{document}

, then L(D) is supereulerian if and only if

D\notin \mathcal{M}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$D\not \in \mathcal {M}$$\end{document}

.

Keywords

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

References

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

[2] Algefari MJ, Alsatami KA, Lai H-J, Liu J. Supereulerian digraphs with given local structures. Inf. Process. Lett., 2016, 116(5): 321-326

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

[4] Algefari MJ, Lai H-J, Xu JQ. Locally dense supereulerian digraphs. Discrete Appl. Math., 2018, 238: 24-31

[5] Alsatami KA, Zhang XD, Liu J, Lai H-J. On a class of supereulerian digraphs. Appl. Math., 2016, 7(3): 320-326

[6] Bang-Jensen J, Déprés H, Yeo A. Spanning eulerian subdigraphs avoiding k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$k$$\end{document} prescribed arcs in tournaments. Discrete Math., 2020, 343(12 112129

[7] Bang-Jensen J, Gutin G. Digraphs: Theory, Algorithms and Applications, 20092London, Springer-Verlag

[8] Bang-Jensen J, Maddaloni A. Sufficient conditions for a digraph to be supereulerian. J. Graph Theory, 2015, 791): 8-20

[9] Boesch FT, Suffel C, Tindell R. The spanning subgraphs of eulerian graphs. J. Graph Theory, 1977, 1(1): 79-84

[10] Bondy JA, Murty USR. Graph Theory, 2008, New York, Springer-Verlag

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

[12] Catlin PA. 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] Gutin G. Connected (g;f)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(g;f)$$\end{document}-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] Hong YM, Lai H-J, Liu QH. Supereulerian digraphs. Discrete Math., 2014, 330(6): 87-95

[18] Hong YM, Liu QH, Lai H-J. Ore-type degree condition of supereulerian digraphs. Discrete Math., 2016, 339(8): 2042-2050

[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, 2020, 5: 1-14

[20] Lai H-J, Shao Y, Yan H. An update on supereulerian graphs. WSEAS Transactions on Mathematics, 2013, 12: 926-940

[21] Liu J, Lasfar O, Wei J, Zhang XD, Lai H-J. Matching and spanning trails in digraphs. Discrete Appl. Math., 2021, 304: 417-433

[22] Liu J, Yang H, Lai H-J, Zhang XD. Symmetric core and spanning trails in directed networks. Discrete Math., 2021, 344 112584

[23] Liu J, Yang H, Zhang XD, Lai H-J. Hamiltonian-connected line digraphs.. Adv. Math., 2023, 52: 224-234

[24] Zhang XD, Liu J, Wang L, Lai H-J. Supereulerian bipartite digraphs. J. Graph Theory, 2018, 89(1): 64-75

Funding

NSFC(12261016)

RIGHTS & PERMISSIONS

Shanghai University