7 papers · 1 filter
The asymptotic maximum oriented diameter of graphs
Jiangdong Ai, Yaokun Feng, Hui Lei +1
The oriented diameter of a connected bridgeless graph is the minimum diameter of a strong orientation. Let be the maximum oriented diameter among all such graphs of diameter…
An improved upper bound for oriented diameter of graphs with diameter
Yaokun Feng, Hui Lei, Xiaopan Lian +1
Let denote the smallest integer such that every bridgeless graph of diameter admits a strong orientation with diameter at most . It is known that and $f(3…
Avoidability of Digraphs with Height Functions and Orientations of
Hui Lei, Xiaoyi Wang, Zhijun Xu +1
A digraph is avoidable if, for every positive integer , there exists an integer such that every digraph of minimum out-degree at least contains an -free subdigrap…
Feedback-arc robustness in random orientations of pseudorandom triangle-free graphs
Hui Lei, Danning Wang, Yiqiao Wang
For an oriented graph , let be the maximum order of an induced acyclic subdigraph, its dichromatic number, and the minimum number of arcs…
Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
Gregory Gutin, Hui Lei, Anders Yeo +1
An oriented multigraph is a directed multigraph without directed 2-cycles. Let denote the minimum size of a feedback arc set in an oriented multigraph . The degre…
Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
Jiangdong Ai, Gregory Gutin, Hui Lei +2
An oriented graph is converse invariant if, for any tournament , the number of copies of in is equal to that of its converse . El Sahili and Ghazo Hanna [J. Grap…
On the -anti-traceability Conjecture
Bin Chen, Stefanie Gerke, Gregory Gutin +3
An oriented graph is called -anti-traceable if the subdigraph induced by every subset with vertices has a hamiltonian anti-directed path. In this paper, we consider an anti-…