Diameter and maximum degree in Eulerian digraphs

详细信息    查看全文

• 作者：Peter Dankelmann ; ^{pdankelmann@uj.ac.za" class="auth_mail" title="E-mail the corresponding author} ; Michael Dorfling ^{mdorfling@uj.ac.za" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Diameter ; Maximum degree ; Distance ; Digraph ; Eulerian digraph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1355-1361
• 全文大小：370 K

文摘

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 3228c9f9425c1a24d120f9a9f3" title="Click to view the MathML source">n$n$ and maximum degree Δ$\Delta$ is at most n−Δ+3$n-\Delta +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)$n-2\Delta +O\left({\Delta }^{2/3}\right)$, and we exhibit an infinite family of such digraphs of diameter n−2Δ+Ω(Δ^1/2)$n-2\Delta +\Omega \left({\Delta }^{1/2}\right)$. We further show that for bipartite Eulerian digraphs with no 2-cycle the diameter is at most n−2Δ+3$n-2\Delta +3$, and that this bound is sharp.