Bandelt, H. J. Retracts of hypercubes. (English) Zbl 0551.05060 J. Graph Theory 8, 501-510 (1984). A median of vertices u,v,w is a vertex x which lies simultaneously on shortest paths joining u with v, v with w, and w with u. A median graph is a connected graph in which any triple u,v,w has a unique median. A subgraph G of a graph H is a retract of H if there exists a mapping \(r:V(H)\to V(G)\) such that \(hh'\in E(H)\) implies \(r(h)r(h')\in E(G)\) and \(g\in V(G)\) implies \(r(g)=g\). The hypercube \(Q_ n\) is the Cartesian nth power of \(K_ 2\). Both graph retracts and median graphs have been previously studied - by Rival, Nowakowski, Quilliot, and the reviewer, and by Mulder, Schrijver, Hedlíková, and the author. The main result of the present paper is the very nice theorem asserting that G is a median graph if and only if it is (isomorphic to) a retract of some \(Q_ n\). As a corollary, the author deduces the following theorem of D. Duffus and I. Rival [Proc. Am. Math. Soc. 88, 197-200 (1983; Zbl 0513.06004)] which motivated his research: G is the (Hasse) diagram of a distributive lattice if and only if it is a retract of \(Q_ n\) with \(n=diam G\). The class of median graphs is also characterized as the smallest class containing \(K_ 2\) and closed under taking retracts and weak Cartesian products. Similar results are obtained for reflexive graphs. Reviewer: P.Hell Cited in 1 ReviewCited in 53 Documents MSC: 05C99 Graph theory Keywords:edge-preserving map; retract; median graph; hypercube Citations:Zbl 0513.06004 PDFBibTeX XMLCite \textit{H. J. Bandelt}, J. Graph Theory 8, 501--510 (1984; Zbl 0551.05060) Full Text: DOI References: [1] Avann, Proc. Amer. Math. Soc. 12 pp 407– (1961) [2] Bandelt, Algebra Universalis [3] Bandelt, Discrete Math. 45 pp 1– (1983) [4] Bandelt, J. Graph Theory 7 pp 487– (1983) [5] Theory of Retracts. Monografie Matematyczne, Warszawa (1967). [6] Duffus, Discrete Math. 35 pp 53– (1981) [7] Duffus, Proc. Amer. Math. Soc. 88 pp 197– (1983) [8] Evans, Colloq. Math. Soc. János Bolyai 29 pp 225– (1982) [9] Rétractions de graphes. Ph.D. thesis, Université de Montréal (1972). [10] Hell, J. Combinatorial Theory 17 pp 5– (1974) [11] Hell, Lecture Notes Math. 406 pp 291– (1974) [12] Graph retractions. Colloq. Intern. Teorie Combinatorie II, Roma (1976) 263–268. [13] Isbell, Trans. Amer. Math. Soc. 260 pp 319– (1980) [14] Mulder, Discrete Math. 24 pp 197– (1978) [15] Mulder, J. Graph Theory 4 pp 107– (1980) [16] Mulder, Discrete Math. 25 pp 41– (1979) [17] Nebesk, Comment. Math. Univ. Carolinae 12 pp 317– (1971) [18] Nieminen, Math. Nachr. 77 pp 87– (1977) [19] Nowakowski, J. Graph Theory 3 pp 339– (1979) [20] Nowakowski, Combinatorica 2 pp 79– (1982) [21] Nowakowski, Discrete Math. 43 pp 223– (1983) [22] Nowakowski, Discrete Math. 43 pp 235– (1983) [23] Rival, Proc. Amer. Math. Soc. 37 pp 417– (1973) [24] Rival, Proc. Amer. Math. Soc. 44 pp 263– (1974) [25] The retract construction. Ordered Sets (ed.). Reidel, Dordrecht (1982) 97–122. [26] Sabidussi, Math. Z. 72 pp 446– (1960) [27] Sholander, Proc. Amer. Math. Soc. 5 pp 808– (1954) 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.