2022/12/14 by P. Dankelmann, M. J. Morgan, Dankelmann, P. +3 · 1 citation
Computer Science · Mathematics · #05C12 (Primary) 05C20 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2212.07257
openalex publication_date 2022/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (p)/(2) \rfloor. 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 \lfloor (3n)/(4) \rfloor if n is even and \lfloor (3(n+1))/(4) \rfloor if n is odd.