×

The retracts of Hamming graphs. (English) Zbl 0759.05085

All graphs considered are finite undirected simple ones. The object of this article is the investigation of the so-called quasimedian graphs. In detail known results, especially of H. M. Mulder, are presented, the essential concepts and their properties are placed at disposal and to it many definitions are necessary, the most important of them are the following:
– Let \(G\subseteq H\) be an induced subgraph of \(H\), a homomorphism \(f:H\to G\) is a retraction if there exists a homomorphism \(c:G\to H\) such that the composition \(r\circ c\) is the identity on \(G\). The mapping \(c\) is called coretraction and \(G\) is a retract of \(H\); that means that retracts are special examples of isometric subgraphs.
– A cartesian product of complete graphs is called a Hamming graph and especially a cartesian power of \(K_ 2\) is the hypercube.
– Let \((u_ 1,u_ 2,u_ 3)\) be a triple of vertices of \(G\); a triple \((x_ 1,x_ 2,x_ 3)\) is called a quasimedian of \((u_ 1,u_ 2,u_ 3)\) in \(G\), if there is a nonnegative integer \(m\) such that for any distinct \(i,j\in\{1,2,3\}\) and the distance \(d\) hold: \(d(x_ i,x_ j)=m\), \(d(u_ i,u_ j)=d(u_ i,x_ i)+m+d(x_ j,u_ j)\) and \(m\) is minimal for \((u_ 1,u_ 2,u_ 3)\). — Special case: \(m=0\) means \(x_ 1=x_ 2=x_ 3\) and this quasimedian is called a median.
– A graph \(G\) is called a median graph if any triple of vertices in \(G\) has exactly one median in \(G\), and a quasimedian graph is a graph \(G\) such that any three vertices have exactly one quasimedian, it does not contain any \(K_ 4-e\) as an induced graph \((e\) is any edge) and the convex closure of any induced 6-circuit of diameter 3 in \(G\) is a hypercube.
– A subgraph \(K\) of \(G\) is called gated in \(G\), if for every \(x\in G\) there exists a vertex \(k(x)\in K\) such that: \(k(x)\in I(x,u)\) for all \(u\in K\), where \(I(x,u)\) means the interval between \(x\) and \(u\) in \(G\).
By application of the concept of gated subgraphs and a contraction of edges the authoress gets with the help of numerous lemmas and corollaries interesting results, but only a few of them can be mentioned here. Further, already known theorems can be proved in a shorter manner. Here some results and properties:
In a quasimedian graph every clique is gated (this Lemma 4.1 is the important statement for applying the concept of gated subgraphs).
The bipartite quasimedian graphs are exactly the median graphs (Theorem 5.2).
The quasimedian graphs are isometric subgraphs of Hamming graphs (Theorem 5.3, H. M. Mulder). A graph \(G\) is quasimedian iff any triple of vertices of \(G\) has a quasimedian and every interval in \(G\) is a median graph (Theorem 5.6).
If \(G\) is a quasimedian graph and \(ab\) is an edge of \(G\), then the factor graph \(G|_{ab}\) is again a quasimedian graph (Contraction Theorem 6.2).
The class of quasimedian graphs is the smallest class of graphs which contains all complete graphs and is closed under the formation of retracts and cartesian products (Theorem 7.4).
The retracts of hypercubes are precisely the median graphs (Corollary 7.6).
A graph \(G\) is quasimedian iff it is a quasimedian-closed induced subgraph of a Hamming graph (Theorem 7.7, H. M. Mulder).

MSC:

05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, H. J., Retracts of hypercubes, J. Graph Theory, 8, 501-510 (1984) · Zbl 0551.05060
[2] Bandelt, H. J., Graphs with intrinsic \(S_3\) convexities, J. Graph Theory, 13, 215-228 (1989)
[3] Bandelt, H. J.; Hedliková, J., Median algebras, Discrete Math., 45, 1-30 (1983) · Zbl 0506.06005
[4] Bandelt, H. J.; Mulder, H. M.; Wilkeit, E., Quasi-median graphs and algebras (1988), preprint
[5] Chung, F. R.K.; Graham, R.; Saks, M. E., A dynamic location problem for graphs, Combinatorica, 9, 111-131 (1989) · Zbl 0692.05055
[6] Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113
[7] Duffus, D.; Rival, I., A structure theory for ordered sets, Discrete Math., 35, 53-118 (1981) · Zbl 0459.06002
[8] Dress, A. W.M.; Scharlau, R., Gated sets in metric spaces, Aequationes Math., 34, 112-120 (1987) · Zbl 0696.54022
[9] Hell, P., Rétractions de graphes, (Ph.D. Thesis (1972), Université de Montréal)
[10] Hell, P., Absolute retracts in graphs, (Bari, R. A.; Harary, F., Graphs and Combinatorics, Vol. 406 (1974), Springer: Springer Berlin), 291-301, Lecture Notes in Math
[11] Mulder, H. M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[12] Mulder, H. M., The interval function of a graph, Math. Centre Tracts, 132 (1980) · Zbl 0446.05039
[13] Nebeský, L., Algebraic properties of Husimi trees, Časopis Pěst. Mat., 107, 116-123 (1982) · Zbl 0502.05059
[14] Nowakowski, R.; Rival, I., The smallest graph variety containing all paths, Discrete Math., 43, 223-234 (1983) · Zbl 0511.05059
[15] Wilkeit, E., Isometrische Untergraphen von Hamming-Graphen, (Dissertation (1986), Universität Oldenburg) · Zbl 0599.05059
[16] Wilkeit, E., Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B, 50, 179-197 (1990) · Zbl 0657.05023
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.