Trade-offs in non-reversing diameter

Abstract

Consider a tree T with a number of extra adges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p, no edge is on the unique path (in T) between the endpoints of b is also in p or on the unique path between the two endpoints of any other bridge in p. (Such a path is called non-reversing.) We investigate the trade-off between the number of added bridges and te resulting diameter. Upper and lower bounds of the same order are obtained for alle diameters of constant size. For the special case where T is a chain we also obtain matching uper and lower bounds for diameters of size a(N) + O(l) or of size f(N) where f(N) grows faster than a(N). Some applications are given.