Abstract | ||
---|---|---|
Let D be a digraph and let alpha(D), alpha'(D) and lambda(D) be independence number, the matching number and the arc-strong connectivity of D, respectively. Bang-Jensen and Thommasse in 2011 conjectured that every digraph D with lambda(D) >= alpha(D) is supereulerian. In [J. Graph Theory, 81(4), (2016) 393-402], it is shown that every digraph D with lambda(D) >= alpha'(D) is supereulerian. In this paper, we introduced the symmetric core of a digraph and use it to show that each of the following holds for a strong digraph D on n >= 3 vertices with lambda(D) >= alpha'(D) - 1.(i) There exists a family D(n) of well-characterized digraphs such that for any digraph D with alpha'(D) <= 2, D has a spanning trial if and only if D is not a member in D(n).(ii) If alpha'(D) >= 3, then D has a spanning trail.(iii) If alpha'(D) >= 3 and n >= 2 alpha'(D) + 3, then D is supereulerian.(iv) If lambda(D) >= alpha'(D) >= 4 and n >= 2 alpha'(D) + 3, then for any pair of vertices u and v of D, D contains a spanning (u, v)-trail. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.dam.2021.08.014 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Strong arc connectivity, Maximum matching, Directed trails, Su pereu lerian digraphs, Chvatal-Erdos condition | Journal | 304 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Juan Liu | 1 | 16 | 6.58 |
Omaema Lasfar | 2 | 0 | 0.34 |
jia wei | 3 | 4 | 3.09 |
Xindong Zhang | 4 | 68 | 10.79 |
Hong-Jian Lai | 5 | 631 | 97.39 |