Diameter and maximum degree in Eulerian digraphs

被引:6
作者
Dankelmann, Peter [1 ]
Dorfling, Michael [1 ]
机构
[1] Univ Johannesburg, Johannesburg, South Africa
基金
新加坡国家研究基金会;
关键词
Diameter; Maximum degree; Distance; Digraph; Eulerian digraph;
D O I
10.1016/j.disc.2015.11.021
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 Delta is at most 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 Delta + O(Delta(2/3)), and we exhibit an infinite family of such digraphs of diameter n - 2 Delta + Omega(Delta(1/2)). We further show that for bipartite Eulerian digraphs with no 2-cycle the diameter is at most n - 2 Delta + 3, and that this bound is sharp. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:1355 / 1361
页数:7
相关论文
共 15 条
[1]  
Amar D., 1983, ANN DISCRETE MATH, V17, P7
[2]   Diameter of orientations of graphs with given minimum degree [J].
Bau, Sheng ;
Dankelmann, Peter .
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 49 :126-133
[3]  
BOSAK J, 1968, THEORY GRAPHS, P37
[4]   Diameter of 4-colourable graphs [J].
Czabarka, E. ;
Dankelmann, P. ;
Szekely, L. A. .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (05) :1082-1089
[5]   The diameter of directed graphs [J].
Dankelmann, P .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) :183-186
[6]   Distance and size in digraphs [J].
Dankelmann, Peter .
DISCRETE MATHEMATICS, 2015, 338 (01) :144-148
[7]  
Dankelmann P, 2010, ELECTRON J COMB, V17
[8]  
Das KC, 2010, MATCH-COMMUN MATH CO, V64, P647
[9]  
ERDOS P, 1989, J COMB THEORY B, V47, P73
[10]  
Goldsmith D.L., 1981, J COMB INF SYST SCI, V6, P315