Premium
Minimal extensions of graphs to absolute retracts
Author(s) -
Pesch Erwin
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110416
Subject(s) - retract , mathematics , combinatorics , injective function , embedding , discrete mathematics , vertex (graph theory) , graph , metric space , pure mathematics , computer science , artificial intelligence
A graph H is an absolute retract if for every isometric embedding h of, into a graph G an edge‐preserving map g from G to H exists such that g · h is the identity map on H . A vertex v is embeddable in a graph G if G − v is a retract of G . An absolute retract is uniquely determined by its set of embeddable vertices. We may regard this set as a metric space. We also prove that a graph (finite metric space with integral distance) can be isometrically embedded into only one smallest absolute retract (injective hull). All graphs in this paper are finite, connected, and without multiple edges.