Crossing Graphs as Joins of Graphs and Cartesian Products of Median Graphs
Boštjan Brešar, Sandi Klavžar · SIAM Journal on Discrete Mathematics · 2007
For a partial cube G its crossing graph $G^#$ is the graph whose vertices are the ϴ‐classes of G, two classes being adjacent if they cross on some cycle in G. The following problem posed in [S. Klavžar and H. M. Mulder, SIAM J. Discrete Math., 15 (2002), pp. 235–251, Problem 7.1] is considered: What can be said about the partial cube G if $G^#$ is the join $A\oplus B$ of graphs A and B with at least one edge? It is proved that for arbitrary graphs A and B, where at least one of them contains an edge, there exists a Cartesian prime partial cube G such that $G^# = A\oplus B$. On the other hand, if G is a median graph, then $G^# = A\oplus B$ if and only if $G=H\,\square\, K$, where $H^# = A$ and $K^# = B$. Along the way some new facts about partial cubes are obtained; for instance, a bipartite graph of radius 2 is a partial cube if and only if it is $K_{2,3}$‐free.