Oriented diameter of graphs with diameter 3

被引：21

作者：

Kwok, Peter K. ^{[1
]}

Liu, Qi ^{[1
]}

West, Douglas B. ^{[1
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2010年 / 100卷 / 03期

关键词：

Diameter; Oriented diameter; MINIMUM DIAMETER; ORIENTATIONS;

D O I：

10.1016/j.jctb.2009.08.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1978, Chvatal and Thomassen proved that every 2-edge-connected graph with diameter 2 has an orientation with diameter at most 6. They also gave general bounds on the smallest value f(d) such that every 2-edge-connected graph G with diameter d has an orientation with diameter at most f(d). For d = 3, their general bounds reduce to 8 <= f(3) <= 24. We improve these bounds to 9 <= f(3) <= 11. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：265 / 274

页数：10

共 10 条

[1]

CHVATAL V, 1978, J COMB THEORY B, V24, P61, DOI 10.1016/0095-8956(78)90078-3

[2] AT-free graphs: linear bounds for the oriented diameter [J].