Name
Abstract | ||
|---|---|---|
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@?V(H), then a vertex map f:U-V(G) is called nonexpansive if for every two vertices x,y@?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@?V(H) and every nonexpansive vertex map f:U-V(G), there is a graph homomorphism @f\"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@?V(G), we can obtain such an extension @f\"f\";\"s that maps each vertex of H closest to the vertex s among all such existing homomorphisms @f\"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 @f\"f\";\"s is unique. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.disc.2006.04.009 | Discrete Mathematics |
Keywords | Field | DocType |
sink extension,reflexive graph,homomorphism,unique sink extension,unique sink extension.,reexiv e graph,graph homomorphism,satisfiability | Discrete mathematics,Circulant graph,Combinatorics,Bound graph,Graph homomorphism,Vertex (graph theory),Neighbourhood (graph theory),Cycle graph,Degree (graph theory),Covering graph,Mathematics | Journal |
Volume | Issue | ISSN |
306 | 17 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.45 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Geir Agnarsson | 1 | 103 | 14.69 |
| Li Chen | 2 | 86 | 38.40 |