The retracts of Hamming graphs
type: Item
instance of: scholarly article
title: The retracts of Hamming graphs
zbMATH Open document ID: 0759.05085
DOI: 10.1016/0012-365X(92)90054-J
author: Elke Wilkeit
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: 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 \textit{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 contracti…
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 65065
zbMATH Keywords: retracts
zbMATH Keywords: Hamming graphs
zbMATH Keywords: quasimedian graphs
zbMATH Keywords: retraction
zbMATH Keywords: median
zbMATH Keywords: gated subgraphs
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Retracts of hypercubes
cites work: Graphs with intrinsic s3 convexities
cites work: Median algebras
cites work: A dynamic location problem for graphs
cites work: Distance-preserving subgraphs of hypercubes
cites work: A structure theory for ordered sets
cites work: Gated sets in metric spaces
cites work: Q4049082
cites work: The structure of median graphs
cites work: Q3890733
cites work: Algebraic properties of Husimi trees
cites work: The smallest graph variety containing all paths
cites work: Q3734453
cites work: Isometric embeddings in Hamming graphs
Recommended article: Retracts of infinite Hamming graphs
Recommended article: Generalized Hamming graphs: some new results
Recommended article: Hamming graphs in Nomura algebras
Recommended article: On the complexity of recognizing Hamming graphs and related classes of graphs
Recommended article: Resolvability of Hamming Graphs
Recommended article: On induced subgraphs of the Hamming graph
Recommended article: Partial Hamming graphs and expansion procedures
Recommended article: Characterizing subgraphs of Hamming graphs
Recommended article: Spectral characterization of the Hamming graphs
Recommended article: A retraction problem in graph theory
description: scientific article; zbMATH DE number 65065