×

Symmetric core and spanning trails in directed networks. (English) Zbl 1472.05140

Summary: A digraph \(D\) is supereulerian if \(D\) has a spanning closed trail, and is strongly trail-connected if for any pair of vertices \(u, v \in V(D)\), \(D\) has a spanning \((u, v)\)-trail and a spanning \((v, u)\)-trail. The symmetric core \(J = J(D)\) of a digraph \(D\) is a spanning subdigraph of \(D\) with \(A(J)\) consisting of all symmetric arcs in \(D\). Let \(J_1, J_2, \dots, J_{k ( D )}\) be the connected symmetric components of \(J\) and define \(\lambda_0(D) = \min \{\lambda( J_i) : 1 \leq i \leq k(D) \}\). We prove that the contraction \(D^\prime = D / J\) can be used to predict the existence of spanning trails in \(D\). It is known that if \(k(D) \leq 2\), then \(D\) has a spanning closed trail. In particular, each of the following holds for a strong digraph \(D\) with \(k(D) \geq 3\).
i) If \(\lambda_0(D) \geq k(D) - 2\), then \(D\) has a spanning trail if and only if \(D^\prime\) has a spanning trail.
ii) If \(\lambda_0(D) \geq k(D) - 1\), then \(D\) is supereulerian if and only if \(D^\prime\) is supereulerian.
iii) If \(\lambda_0(D) \geq k(D)\), then \(D\) is strongly trail-connected if and only if \(D^\prime\) is strongly trail-connected.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] Alfegari, M.; Lai, H.-J., Supereulerian digraphs with large arc-strong connectivity, J. Graph Theory, 81, 4, 393-402 (2016) · Zbl 1333.05132
[2] Algefari, M. J.; Alsatami, K. A.; Lai, H.-J.; Liu, J., Supereulerian digraphs with given local structures, Inf. Process. Lett., 116, 321-326 (2016) · Zbl 1352.05075
[3] Algefari, M.; Lai, H.-J.; Xu, J., Locally dense supereulerian digraphs, Discrete Appl. Math., 238, 24-31 (2018) · Zbl 1380.05083
[4] Alsatami, K. A.; Zhang, X.; Liu, J.; Lai, H.-J., On a class of supereulerian digraphs, Appl. Math., 7, 320-326 (2016)
[5] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002
[6] Bang-Jensen, J.; Maddaloni, A., Sufficient conditions for a digraph to be supereulerian, J. Graph Theory, 79, 8-20 (2015) · Zbl 1312.05060
[7] Bang-Jensen, J.; Déprés, H.; Yeo, A., Spanning Eulerian subdigraphs avoiding k prescribed arcs in tournaments, Discrete Math., 343, 12, Article 112129 pp. (2020) · Zbl 1448.05083
[8] Bang-Jensen, J.; Havet, F.; Yeo, A., Spanning Eulerian subdigraphs in semicomplete digraphs · Zbl 1522.05155
[9] Boesch, F. T.; Suffel, C.; Tindell, R., The spanning subgraphs of Eulerian graphs, J. Graph Theory, 1, 79-84 (1977) · Zbl 0363.05042
[10] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001
[11] Catlin, P. A., Supereulerian graphs: a survey, J. Graph Theory, 16, 177-196 (1992) · Zbl 0771.05059
[12] Chen, Z. H.; Lai, H.-J., Reduction techniques for super-Eulerian graphs and related topics-a survey, (Combinatorics and Graph Theory ’95. Combinatorics and Graph Theory ’95, Hefei, vol. 1 (1995), World Sci. Publishing: World Sci. Publishing River Edge, NJ), 53-69
[13] Gutin, G., Cycles and paths in directed graphs (1993), School of Mathematics, Tel Aviv University, PhD thesis · Zbl 0794.05036
[14] Gutin, G., Connected \((g; f)\)-factors and supereulerian digraphs, Ars Comb., 54, 311-317 (2000) · Zbl 0994.05086
[15] Hong, Y.; Lai, H.-J.; Liu, Q., Supereulerian digraphs, Discrete Math., 330, 87-95 (2014) · Zbl 1295.05116
[16] Hong, Y.; Liu, Q.; Lai, H.-J., Ore-type degree condition of supereulerian digraphs, Discrete Math., 339, 2042-2050 (2016) · Zbl 1336.05049
[17] Lai, H.-J.; Shao, Y.; Yan, H., An update on supereulerian graphs, WSEAS Trans. Math., 12, 926-940 (2013)
[18] Liu, F.; Tian, Z.-X.; Li, D. M., Supereulerian locally semicomplete multipartite digraphs, Int. J. Math. Comb., 2, 123-128 (2017)
[19] Pulleyblank, W. R., A note on graphs spanned by Eulerian graphs, J. Graph Theory, 3, 309-310 (1979) · Zbl 0414.05040
[20] Shiloach, Y., Edge-disjoint branching in directed multigraphs, Inf. Process. Lett., 8, 1, 24-27 (1979) · Zbl 0402.68051
[21] Zhang, X. D.; Liu, J.; Wang, L.; Lai, H.-J., Supereulerian bipartite digraphs, J. Graph Theory, 89, 64-75 (2018) · Zbl 1398.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.