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

arXiv2212.07257MaRDI QIDQ6420533FDOQ6420533

Authors: Peter Dankelmann, M. J. Morgan, E. J. Rivett-Carnac 

Publication date: 14 December 2022

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. We show that every bridgeless graph of order $n$ containing $p$ blocks, has an oriented diameter of at most $n-lfloorfracp2floor$. This bound is sharp for all $n$ and $p$ with $pgeq2$. As a corollary, we obtain a sharp upper bound in terms of order and number of cut vertices.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12)

This page was built for publication: Diameter of orientations of graphs with given order and number of blocks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420533)