Research Article

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

Published in: Quaestiones Mathematicae
Volume 48 , issue 8 : Entrepreneurship and Africa’s Cultural Context , 2024 , pages: 1261–1275
DOI: 10.2989/16073606.2025.2480134
Author(s): P. Dankelmann University of Johannesburg, South Africa, M.J. Morgan School of Mathematics, Statistics and Computer Science, University of KwaZulu-Natal, South Africa, E.J. Rivett-Carnac University of Johannesburg, South Africa,
Keywords: Primary: Primary: 05C12, Secondary: Secondary: 05C20, diameter, oriented diameter, orientation number, block, block graph,
Download full text Get new issue alerts

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.
« On β-adic expansions of powers of an algebraic integer omitting a digit
Evolution, population structure and morphology of the African Black Duck Anas sparsa and Yellow-billed Duck A. undulata »

Get new issue alerts for Quaestiones Mathematicae

CAPTCHA Reload CAPTCHA