Partial cubes and crossing graphs
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.
- Partial cubes and their \(\tau\)-graphs
- On crossing numbers of hypercubes and cube connected cycles
- Cubic graphs with crossing number two
- Cubical graphs and cubical dimensions
- Partial cubes as subdivision graphs and as generalized Petersen graphs
- On Tetha-graphs of partial cubes
- Cube factorizations of complete graphs
- scientific article; zbMATH DE number 2185257
- Partial cubes are distance graphs
- Partition-crossing hypergraphs
- Netlike partial cubes, V: completion and netlike classes
- Induced cycles in crossing graphs of median graphs
- Cubic inflation, mirror graphs, regular maps, and partial cubes
- On some characterizations of antipodal partial cubes
- On partial cubes, well-graded families and their duals with some applications in graphs
- A theorem on Wiener-type invariants for isometric subgraphs of hypercubes
- A correction of a characterization of planar partial cubes
- \(\Theta\)-graceful labelings of partial cubes
- Complete path embeddings in crossed cubes
- On semicube graphs
- The hypergraph of -classes and -graphs of partial cubes.
- On Tetha-graphs of partial cubes
- Crossing Graphs as Joins of Graphs and Cartesian Products of Median Graphs
- Crossing graphs of fiber-complemented graphs
- Crossing graphs of fiber-complemented graphs
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- A relation between the cube polynomials of partial cubes and the clique polynomials of their crossing graphs
- On crossing numbers of hypercubes and cube connected cycles
- Cyclic hyperbolicity in \(\mathrm{CAT}(0)\) cube complexes
- Buneman graphs, partial splits and subtree distances
- Not all partial cubes are \(\Theta \)-graceful
- Partial cubes and their \(\tau\)-graphs
- Partial cubes: Structures, characterizations, and constructions
This page was built for publication: Partial cubes and crossing graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784514)
