Directed distance in digraphs: Centers and medians

The directed distance d D ( u, v ) from a vertex u to a vertex v in a strong digraph D is the length of a shortest (directed) u ‐ v path in D. The eccentricity of a vertex v in D is the directed distance from v to a vertex furthest from v. The distance of a vertex v in D is the sum of the directed distances from v to the vertices of D. The center C ( D ) of D is the subdigraph induced by those vertices of minimum eccentricity, while the median M ( D ) of D is the subdigraph induced by those vertices of minimum distance. It is shown that for every two asymmetric digraphs D 1 and D 2 , there exists a strong asymmetric digraph H such that C ( H ) ≅ D 1 and M ( H ) ≅ D 2 , and where the directed distance from C ( H ) to M ( H ) and from M ( H ) to C ( H ) can be arbitrarily prescribed. Furthermore, if K is a nonempty asymmetric digraph isomorphic to an induced subdigraph of both D 1 and D 2 , then there exists a strong asymmetric digraph F such that C ( F ) ≅ D 1 , M ( F ) ≅ D 2 and C ( F ) ∩ M ( F ) ≅ K. © 1993 John Wiley & Sons, Inc.