An improvement to Chvátal and Thomassen's upper bound for oriented diameter

Publication date 30 September 2021

Abstract: An orientation of an undirected graph

G

is an assignment of exactly one direction to each edge of

G

. The oriented diameter of a graph

G

is the smallest diameter among all the orientations of

G

. The maximum oriented diameter of a family of graphs

m a t h s c r F

is the maximum oriented diameter among all the graphs in

m a t h s c r F

. Chv'atal and Thomassen [JCTB, 1978] gave a lower bound of

f r a c 12 d^{2} + d

and an upper bound of

2 d^{2} + 2 d

for the maximum oriented diameter of the family of

2

-edge connected graphs of diameter

d

. We improve this upper bound to

1.373 d^{2} + 6.971 d - 1

, which outperforms the former upper bound for all values of

d

greater than or equal to

8

. For the family of

2

-edge connected graphs of diameter

3

, Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of

9

and

11

respectively. For the family of

2

-edge connected graphs of diameter

4

, the bounds provided by Chv'atal and Thomassen are

12

and

40

and no better bounds were known. By extending the method we used for diameter

d

graphs, along with an asymmetric extension of a technique used by Chv'atal and Thomassen, we have improved this upper bound to

21

.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: An improvement to Chvátal and Thomassen's upper bound for oriented diameter