Diameter and maximum degree in Eulerian digraphs

Peter Dankelmann, Michael Dorfling

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


In this paper we consider upper bounds on the diameter of Eulerian digraphs containing a vertex of large degree. Define the maximum degree of a digraph to be the maximum of all in-degrees and out-degrees of its vertices. We show that the diameter of an Eulerian digraph of order n and maximum degree Δ is at most n-Δ+3, and this bound is sharp. We also show that the bound can be improved for Eulerian digraphs with no 2-cycle to n-2Δ+O(Δ2/3), and we exhibit an infinite family of such digraphs of diameter n-2Δ+Ω(Δ1/2). We further show that for bipartite Eulerian digraphs with no 2-cycle the diameter is at most n-2Δ+3, and that this bound is sharp.

Original languageEnglish
Pages (from-to)1355-1361
Number of pages7
JournalDiscrete Mathematics
Issue number4
Publication statusPublished - 6 Apr 2016


  • Diameter
  • Digraph
  • Distance
  • Eulerian digraph
  • Maximum degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Diameter and maximum degree in Eulerian digraphs'. Together they form a unique fingerprint.

Cite this