2021/05/05 by Jasine Babu, Babu, Jasine, Deepu Benson +3 · 1 citation
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2105.02356
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 4r2+4r on f(r) [Chung, Garey and Tarjan, Networks, 1985] to 1.5 r2 + 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 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.5 r η. All our proofs are constructive and lend themselves to polynomial time algorithms.