The diameter of almost eulerian digraphs

Peter Dankelmann, L. Volkmann

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

Soares [J. Graph Theory 1992] showed that the well known upper bound on the diameter of undirected graphs of order n and minimum degree δ also holds for digraphs, provided they are eulerian. In this paper we investigate if similar bounds can be given for digraphs that are, in some sense, close to being eulerian. In particular we show that a directed graph of order n and minimum degree δ whose arc set can be partitioned into s trails, where s ≤ - 2, has diameter at most. If s also divides δ - 2, then we show the diameter to be at most. The latter bound is sharp, apart from an additive constant. As a corollary we obtain the sharp upper bound on the diameter of digraphs that have an eulerian trail.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume17
Issue number1
DOIs
Publication statusPublished - 2010
Externally publishedYes

Keywords

  • Diameter
  • Digraph
  • Eulerian
  • Semi-eulerian

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The diameter of almost eulerian digraphs'. Together they form a unique fingerprint.

Cite this