Premium
Directed distance in digraphs: Centers and medians
Author(s) -
Chartrand Gary,
Johns Garry L.,
Tian Songlin,
Winters Steven J.
Publication year - 1993
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190170408
Subject(s) - digraph , combinatorics , vertex (graph theory) , mathematics , path (computing) , directed graph , discrete mathematics , graph , computer science , programming language
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.