The diameter of almost Eulerian digraphs
type: Item
instance of: scholarly article
title: The diameter of almost Eulerian digraphs
zbMATH Open document ID: 1204.05042
author: Peter Dankelmann
author: Lutz Volkmann
published in: The Electronic Journal of Combinatorics
publication date: 2010-12-16T00:00:00Z
full work available at URL: https://eudml.org/doc/229522
full work available at URL: v17i1r157.html
review text: Summary: \textit{J. Soares} [J. Graph Theory 16, No.~5, 437--450 (1992; Zbl 0768.05048)] showed that the well known upper bound \(\frac{3}{\delta+1}n+O(1)\) on the diameter of undirected graphs of order \(n\) and minimum degree 5 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 \(\delta\) whose arc set can be partitioned into s trails, where \(s\leq\delta-2\), has diameter at most \(3(\delta+1-\frac s3)^{-1}n+ O(1)\). If s also divides \(\delta-2\), then we show the diameter to be at most \(3(\delta+1- \frac{(\delta-2)s}{3(\delta-2)+s})^{-1}n+ O(1)\). The latter bound is sharp, apart from an additive constant. As a corollary we obtain the sharp upper bound \(3(\delta+1- \frac{\delta-2}{3\delta-5})^{-1}n+ O(1)\) on the diameter of digraphs that have an Eulerian trail.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 5827406
zbMATH Keywords: digraph
zbMATH Keywords: Eulerian
zbMATH Keywords: semi-Eulerian
zbMATH Keywords: diameter
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5827406