Directed distance in digraphs: Centers and medians
Gary Chartrand, Garry L. Johns, Songlin Tian, Steven J. Winters · Journal of Graph Theory · 1993
Abstract The directed distance dD(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 D1 and D2, there exists a strong asymmetric digraph H such that C(H) ≅ D1 and M(H) ≅ D2, 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 D1 and D2, then there exists a strong asymmetric digraph F such that C(F) ≅ D1, M(F) ≅ D2 and C(F) ∩ M(F) ≅ K. © 1993 John Wiley & Sons, Inc.