Unique eccentric point graphs of diameter at most four

The eccentricity of a vertex u in a connected graph G is the value ecc(u) = max{d(u, v) | v ∈ V (G)}. A vertex v is an eccentric vertex for u if ecc(u) = d(u, v). A graph is called a unique eccentric point graph (shortly, uep-graph) [2] if every vertex has exactly one eccentric vertex. This is equivalent to saying that the corresponding eccentric digraph ED(G) is functional. Generally speaking, characterizing uep-graphs and describing their eccentric digraphs is a non-trivial problem. To construct uep-graphs with various properties, we have applied evolutionary algorithms, which helped us characterize them for small diameters. The only uep-graph of diameter one is K2. Those of diameter two are exactly the self-centered (n − 2)-regular graphs [2]. A uep-graph of diameter thee is either self-centered or upper-diameter critical [2]. In [1], we obtained a characterization of non-self-centered uep-graphs G of diam(G) = 3 as those whose complement G is a bi-star. We also described eccentric digraphs of uep-graphs via the following classification of their weak components: bald, if it is D0,0; half-bald, if exactly one of the two vertices on a 2-cycle has in-degree one; full otherwise. A digraph D arises as ED(G) for some uep-graph G of diam(G) = 3 if and only if D consists of l ≥ 3 bald components, or D ≃ Dm,k for m, k ≥ 1. For any non-self-centered uep-graph G of diam(G) = 4, it holds [1]: 1. each eccentric vertex in G lies on a cycle in ED(G); 2. A 2-cycle x ↔ y forms a bald weak component in ED(G) if and only if dG(x, y) = 3; 3. ED(G) has no half-bald weak components.