Improved Bounds for the Oriented Radius of Mixed Multigraphs
share
A mixed multigraph is a multigraph which may contain both undirected and directed edges. An orientation of a mixed multigraph G is an assignment of exactly one direction to each undirected edge of G. A mixed multigraph G can be oriented to a strongly connected digraph if and only if G is bridgeless and strongly connected [Boesch and Tindell, Am. Math. Mon., 1980]. For each r ∈ℕ, let f(r) denote the smallest number such that any strongly connected bridgeless mixed multigraph with radius r can be oriented to a digraph of radius at most f(r). We improve the current best upper bound of 4r^2+4r on f(r) [Chung, Garey and Tarjan, Networks, 1985] to 1.5 r^2 + r + 1. Our upper bound is tight upto a multiplicative factor of 1.5 since, ∀ r ∈ℕ, there exists an undirected bridgeless graph of radius r such that every orientation of it has radius at least r^2 + r [Chvátal and Thomassen, J. Comb. Theory. Ser. B., 1978]. We prove a marginally better lower bound, f(r) ≥ r^2 + 3r + 1, for mixed multigraphs. While this marginal improvement does not help with asymptotic estimates, it clears a natural suspicion that, like undirected graphs, f(r) may be equal to r^2 + r even for mixed multigraphs. En route, we show that if each edge of G lies in a cycle of length at most η, then the oriented radius of G is at most 1.5 r η. All our proofs are constructive and lend themselves to polynomial time algorithms.
READ FULL TEXT