## Abstract

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 language | English |
---|---|

Pages (from-to) | 1355-1361 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 339 |

Issue number | 4 |

DOIs | |

Publication status | Published - 6 Apr 2016 |

## Keywords

- Diameter
- Digraph
- Distance
- Eulerian digraph
- Maximum degree

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics