| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4657206 | Journal of Combinatorial Theory, Series B | 2010 | 10 Pages |
Abstract
In 1978, Chvátal 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
