Header menu link for other important links

Improved Bounds for the Oriented Radius of Mixed Multigraphs

, Deepu Benson, Deepak Rajendraprasad
Published in

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∈N, 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 4r2+4r on f(r) [Chung, Garey and Tarjan, Networks, 1985] to 1.5r2+r+1. Our upper bound is tight upto a multiplicative factor of 1.5 since, ∀r∈N, there exists an undirected bridgeless graph of radius r such that every orientation of it has radius at least r2+r [Chvátal and Thomassen, J. Comb. Theory. Ser. B., 1978]. We prove a marginally better lower bound, f(r)≥r2+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 r2+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.5rη. All our proofs are constructive and lend themselves to polynomial time algorithms.

About the journal
Open AccessNo