Absolute reflexive retracts and absolute bipartite retracts (Q686243): Difference between revisions

A subgraph \(G=(V,E)\) of \(G'=(V',E')\) is a retract of \(G'\) if there is some edge-preserving mapping \(f:V' \to V\) such that \(f(x)=x\) for a every \(x \in V\). An absolute reflexive (respectively bipartite) retract is a reflexive (respectively bipartite) graph \(G\) with the property that if \(G\) is an isometric subgraph of some reflexive (respectively bipartite) graph \(G'\), then \(G\) is a retract of \(G'\). Several characterizations of absolute reflexive retracts or absolute bipartite retracts are known. These characterizations are very similar. In the paper under review, this connection is made explicit in the following sense: Four transformations between the class of reflexive graphs and the class of bipartite graphs are presented. Well known are the bigraph \(B(G)\) and the vertex-clique incidence graph \(I(G)\) of a reflexive graph \(G\). Conversely, if \(H\) is a bipartite graph with given bipartition \(X \cup Y\), then the sesqui-power \(S_ X (H)\) is the reflexive graph with vertex set \(X\cup Y\) and two vertices adjacent if their \(H\)-distance is at most 1, or if both belong to \(X\) and their \(H\)-distance is at most 2. The sesqui-power \(S_ Y (H)\) is defined analogously. The edge graph \(E(H)\) has the edges of \(H\) as vertices, and two such vertices are adjacent in \(E(H)\) whenever the corresponding edges intersect, or lie on a 4-cycle of \(H\). It is shown that these transformations map absolute reflexive retracts into absolute bipartite retracts, and conversely. Moreover, also the ingredients of the characterizations behave in this sense under the transformations.