Improved bound on the oriented diameter of graphs with given minimum degree. (January 2017)

• Record Type: Journal Article
• Authors: Surmacs, Michel
• Is Part Of: European journal of combinatorics. Volume 59(2017)
• Page Start: 187
• Page End: 191
• Publication Date: 2017-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.08.006
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: In 2015, Bau and Dankelmann showed that every bridgeless graph G of order n and minimum degree δ has an orientation of diameter at most 11 n δ + 1 + 9 . As they were convinced that this bound is not best possible, they posed the problem of improving it. In this paper, we prove that such a graph G has an orientation of diameter less than 7 n δ + 1 and give a polynomial-time algorithm to construct one.