Characterization of eccentric digraphs

The eccentric digraph  ED(G)ED(G) of a digraph G represents the binary relation, defined on the vertex set of G, of being ‘eccentric’; that is, there is an arc from u   to vv in ED(G)ED(G) if and only if vv is at maximum distance from u in G. A digraph G is said to be eccentric if there exists a digraph H   such that G=ED(H)G=ED(H). This paper is devoted to the study of the following two questions: what digraphs are eccentric and when the relation of being eccentric is symmetric.We present a characterization of eccentric digraphs, which in the undirected case says that a graph G   is eccentric iff its complement graph G¯ is either self-centered of radius two or it is the union of complete graphs. As a consequence, we obtain that all trees except those with diameter 3 are eccentric digraphs. We also determine when ED(G)ED(G) is symmetric in the cases when G is a graph or a digraph that is not strongly connected.