Article ID Journal Published Year Pages File Type
4651401 Discrete Mathematics 2006 10 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,