On the Monotonicity of Minimum Diameter with Respect to Order and Maximum Out-Degree

Considering the three parameters of a directed graph: order, diameter and maximum out-degree, there are three optimal problems that arise if we optimise in turn each one of the parameters while holding the other two parameters fixed. These three problems are related but as far as we know not equivalent. One way to prove the equivalence of the three problems would be to prove that the optimal value of each parameter is monotonic in each of the other two parameters. It is known that maximum order is monotonic in both diameter and maximum out-degree and that minimum diameter is monotonic in maximum out-degree. In general, it is not known whether the other three possible monotonicity implications hold. In this paper, we consider the problem of determining the smallest diameter K(n, d) of a digraph G given order n and maximum out-degree d. Using a new technique for construction of digraphs, we prove that K(n, d) is monotonic for all n such that \( \frac{{d^k - d}} {{d - 1}} < n \leqslant d^k + d^{k - 1} \), thus solving an open problem posed in 1988 by Miller and Fris.

Authors and Affiliations

1. Department of Computer Science and Software Engineering, The University of Newcastle, NSW, 2308, Australia

   Mirka Miller &  Slamin

Editors and Affiliations

1. Department of Computer Science and Engineering, University of Minnesota, MN 55455, Minneapolis, USA

   Ding-Zhu Du

2. Department of Computer Science and Software Engineering, University of Newcastle, Callaghan, NSW 2308, Australia

   Peter Eades  & Vladimir Estivill-Castro  & 

3. School of Computer Science and Engineering, University of Newcastle, NSW 2052, Sydney, Australia

   Xuemin Lin  & Arun Sharma  & 

Reprints and permissions

© 2000 Springer-Verlag Berlin Heidelberg

Policies and ethics