The retracts of Hamming graphs (Q1193717): Difference between revisions

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 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, \textit{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, \textit{H. M. Mulder}).