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 GG and HH are reflexive graphs and U⊆V(H)U⊆V(H), then a vertex map f:U→V(G)f:U→V(G) is called nonexpansive   if for every two vertices x,y∈Ux,y∈U, the distance between f(x)f(x) and f(y)f(y) in GG is at most that between xx and yy in HH. A reflexive graph GG is said to have the extension property   (EP) if for every reflexive graph HH, every U⊆V(H)U⊆V(H) and every nonexpansive vertex map f:U→V(G)f:U→V(G), there is a graph homomorphism φf:H→Gφf:H→G that agrees with ff on UU. 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∈V(G)s∈V(G), we can obtain such an extension φf;sφf;s that maps each vertex of HH closest to the vertex ss among all such existing homomorphisms φfφf. A reflexive graph GG 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 φf;sφf;s is unique.