×

Minimal extensions of graphs to absolute retracts. (English) Zbl 0649.05050

All graphs considered here are finite, connected, and without multiple edges. An induced subgraph H of a graph G is said to be a retract of G if there is an edge-preserving map from G to H which is the identity on H. A graph H is said to be an absolute retract if for every isometric embedding h of H into a graph G an edge-preserving map g from G to H exists such that \(g\circ h\) is the identity on H. A vertex v of G is said to be embeddable if G-v is a retract of G. It is shown that an absolute retract is uniquely determined by its set of embeddable vertices, and that a graph can be isometrically embedded into only one smallest absolute retract.
Reviewer: A.T.White

MSC:

05C75 Structural characterization of families of graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aronszajn, Pac. J. Math. 6 pp 405– (1956) · Zbl 0074.17802 · doi:10.2140/pjm.1956.6.405
[2] Bandelt, Eur. J. Combinatorics
[3] Bandelt, Discrete Appl. Math. 16 pp 191– (1987)
[4] Dress, Adv. Math. 53 pp 321– (1984)
[5] Rétractions de graphes. Ph.D thesis, Université de Montréal (1972).
[6] Hell, Lecture Notes Math. 406 pp 291– (1974)
[7] Hell, Teorie Combinatorie 17 pp 263– (1976) · Zbl 0349.05003
[8] Hell, Can. J. Math.
[9] Isbell, Comment. Math. Helv. 39 pp 65– (1964)
[10] Les rétractions dans les graphes, applications et généralisation. Thèse de 3{\(\deg\)} Cycle, Lyon (1983).
[11] Jawhari, Contemp. Math. 57 pp 175– (1986) · doi:10.1090/conm/057/856237
[12] Rétracts absolus d’ ensembles ordonnés et de graphes, propriété du point fixe. Thèse de 3{\(\deg\)} Cycle, Lyon (1984).
[13] Nowakowski, J. Graph Theory 3 pp 339– (1979)
[14] Nowakowski, Discrete Math. 43 pp 223– (1983)
[15] Nowakowski, Discrete Math. 43 pp 235– (1983)
[16] Pesch, Discrete Math.
[17] A branch and bound method for Helly graph construction, submitted.
[18] Pesch, Discrete Math. 57 pp 99– (1985)
[19] Homomorphismes, points fixes, rétractions et jeux de poursuite dans les graphs, les ensembles ordonnés et les espaces métriques. Thèse de Doctorat d’Etat, Paris (1983).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.