Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653204 | European Journal of Combinatorics | 2017 | 5 Pages |
Abstract
In 2015, Bau and Dankelmann showed that every bridgeless graph GG of order nn and minimum degree δδ has an orientation of diameter at most 11nδ+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 GG has an orientation of diameter less than 7nδ+1 and give a polynomial-time algorithm to construct one.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michel Surmacs,