Jiangdong Ai

A Quadratic Upper Bound for the Maximum Oriented Diameter With Leading Constant 1

ABSTRACT Let be the smallest integer such that every bridgeless graph with has a strong orientation satisfying . In 1978, Chvátal and Thomassen proved . Later, Babu–Benson–Rajendraprasad–Vaka improved the upper bound to . We show that the leading constant can be reduced to 1: We...

Feedback vertex sets of digraphs with bounded maximum degree

A digraph $D$ is an oriented graph if $D$ does not have a pair of opposite arcs. The degree of a vertex $v$ of $D$ is the sum of the in-degree and out-degree of $v.$ Let $fvs(D)$ be the minimum number of vertices whose deletion from $D$ makes it acyclic. Let $D$ be a digraph with...