TAILIEUCHUNG - Báo cáo toán học: "The Diameter of Almost Eulerian Digraphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The Diameter of Almost Eulerian Digraphs. | The Diameter of Almost Eulerian Digraphs Peter Dankelmann L. Volkmann School of Mathematical Sciences Lehrstuhl II fur Mathematik University of KwaZulu-Natal RWTH Aachen University Durban 4000 South Africa 52056 Aachen Germany dankelma@ volkm@ Submitted Oct 9 2008 Accepted Oct 20 2010 Published Nov 19 2010 Mathematics Subject Classification 05C12 05C20 Abstract Soares J. Graph Theory 1992 showed that the well known upper bound d T n O 1 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 3 Ỗ 1 3 -1n O 1 . If s also divides Ỗ 2 then we show the diameter to be at m 11 1 Q Ỉ i I 1 1 1 II I 1 1 1 I I l -1 I ltf lT 11 11 ic i ll 1 T T 1 TA rl Fy. ITn in most 3 Ỗ 1 3 d 2 I s n OO 1 . T he latter bound is siiarp apar t noni an additive constant. As a corollary we obtain the sharp upper bound 3 Ỗ 1 3ffA -1n O 1 on the diameter of digraphs that have an eulerian trail. Keywords digraph eulerian semi-eulerian diameter. 1 Introduction While for undirected graphs bounds on the diameter have been well researched much less is known about the diameter of directed graphs. Most bounds on the diameter of undirected graphs do not have a straightforward analogue for directed graphs. A case in point and the starting point of our investigation is the following well-known bound on the diameter on an undirected graph in terms of order and minimum degree. Theorem 1 Let G be a connected graph of order n and minimum degree 5 3. Then 3 diam G 5 1 n O 1 . Apart from the additive constant this bound is best possible. Financial support by the South African National Research Foundation is gratefully acknowledged THE ELECTRONIC .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học