On the extension of vertex maps to graph homomorphisms

A reflexive graph is a simple undirected graph where a loop has been added at each vertex. If G and H are reflexive graphs and U subset of V(H), then a vertex map f : U -> V(G) is called nonexpansive if for every two vertices x, y is an element of U, the distance between f (x) and f (y) in G is at most that between x and y in H. A reflexive graph G is said to have the extension property (EP) if for every reflexive graph H, every U subset of V(H) and every nonexpansive vertex map f : U -> V(G), there is a graph homomorphism phi(f) : H -> G that agrees with f on U. Characterizations of EP-graphs are well known in the mathematics and computer science literature. In this article we determine when exactly, for a given "sink"-vertex s is an element of V(G), we can obtain such an extension phi(f;s) that maps each vertex of H closest to the vertex s among all such existing homomorphisms of phi(f). A reflexive graph G satisfying this is then said to have the sink extension property (SEP). We then characterize the reflexive graphs with the unique sink extension property (USEP), where each such sink extensions phi(f;s) is unique. (c) 2006 Elsevier B.V. All rights reserved.