Partial cubes and crossing graphs (Q2784514)

The reflexive and symmetric Djoković-Winkler relation \(\Theta\) is defined on the edge set of a graph \(G= (V,E)\) in the following way: Edges \(e= xy\) and \(f= uv\), \(x,y,u,v\in V\), are in relation \(\Theta\) if \(d_G(x,u)+ d_G(y,v)\neq d_G(x,v)+ d_G(y,u)\), where the length of a shortest path in \(G\) from \(w\) to \(z\) is denoted by \(d_G(w,z)\). It is known that a partial cube is defined to be a connected graph that admits an isometric embedding into a hypercube, and in the present paper the structure of the \(\Theta\)-classes of a partial cube \(G\) is considered. For this it is said that two \(\Theta\)-classes \(F_1\) and \(F_2\) cross in \(G\) if edges of \(F_2\) occur in both the components of \(G-F_1\), and then the crossing graph \(G^{\#}\) of a partial cube \(G\) is introduced as the graph whose vertices are the \(\Theta\)-classes of \(G\), where two vertices of \(G^{\#}\) are joined by an edge whenever they cross as \(\Theta\)-classes in \(G\). At first basic facts and properties of the relation \(\Theta\) are put together and then it is proved that every connected graph is a crossing graph of some partial cube and even of some median graph (Theorem 3.1); this result is also given in a more precise form. From the multitude of the further results here only the following let be given:NEWLINENEWLINENEWLINE(1) If \(G\) is a partial cube, then \(G\) is 2-connected iff \(G^{\#}\) is connected (Theorem 3.4).NEWLINENEWLINENEWLINE(2) If \(G\) is a median graph, then \(G\) is a hypercube iff \(G^{\#}\) is complete (Proposition 4.1); this result is also given in a more precise form.NEWLINENEWLINENEWLINE(3) A so-called expansion for partial cubes with complete crossing graphs is given by Proposition 4.4.NEWLINENEWLINENEWLINE(4) If \(G\) is a partial cube, then \(G^{\#}\) is triangle-free iff \(G\) is a cube-free median group (Theorem 5.1). This result allows the characterization of several subclasses of partial cubes having nice crossing graphs, e.g. a tree or a forest.NEWLINENEWLINENEWLINE(5) Let \(G\) be a partial cube. Then \(G^{\#}\) is a cycle of length \(n\geq 4\) iff \(G\) is a cogwheel (which is defined and illustrated in the paper) (Theorem 5.3).NEWLINENEWLINENEWLINE(6) Numerous equivalence statements are proved by Theorems 5.4 and 5.5 (still other types of graphs are investigated).NEWLINENEWLINENEWLINE(7) Let \(G\) be a partial cube. Then \(G^{\#}\) is a complete bipartite graph iff \(G\) is the Cartesian product of two trees (Theorem 6.5).NEWLINENEWLINENEWLINEFinaly all results are summarized in a table and three open problems are formulated.