Diameter of orientations of graphs with given order and number of blocks

Abstract

A strong orientation of a graph G is an assignment of a direction to each edge such that G is strongly connected. The oriented diameter of G is the smallest diameter among all strong orientations of G. A block of G is a maximal connected subgraph of G that has no cut vertex. A block graph is a graph in which every block is a clique. We show that every bridgeless graph of order n containing p blocks has an oriented diameter of at most . This bound is sharp for all n and p with p ≥ 2. As a corollary, we obtain a sharp upper bound on the oriented diameter in terms of order and number of cut vertices. We also show that the oriented diameter of a bridgeless block graph of order n is bounded above by if n is even and if n is odd.