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 $n-\lfloor \frac{p}{2}\rfloor$. This bound is sharp for all $n$ and $p$ with $p\ge 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 $\lfloor \frac{3n}{4}\rfloor$ if $n$ is even and $\lfloor \frac{3(n+1)}{4}\rfloor$ if $n$ is odd.

15 pages, 2 figures