AT-free graphs: linear bounds for the oriented diameter Original Research Article

Let G be a bridgeless connected undirected (b.c.u.) graph. The oriented diameter of G, OD(G), is given by OD(G)=min{diam(H): H is an orientation of G}, where diam(H) is the maximum length computed over the lengths of all the shortest directed paths in H. This work starts with a result stating that, for every b.c.u. graph G, its oriented diameter OD(G) and its domination number γ(G) are linearly related as follows: OD(G)⩽9γ(G)−5.