A characterization of halved cubes (Q2715935)

Let \(G\) be a bipartite graph with bipartition \(V(G) = X \cup Y\). A halved graph \(G'\) of \(G\) is defined by \(V(G') = X\) and \(uv\in E(G')\) whenever \(u\) and \(v\) have a common neighbor in \(G\). (Obviously, \(G\) has another halved graph with vertex set \(Y\).) Both halved graphs of the \(d\)-cube \(Q_d\) are isomorphic and one can talk about the halved \(d\)-cube \(Q'_d\). NEWLINENEWLINENEWLINEThe authors first derive several properties of halved cubes and then prove that some of these properties already characterize them. The main result claims that, for \(d\geq 5\), a connected, \(\binom {d}{2}\)-regular graph on \(2^{d-1}\) vertices is the halved cube \(Q'_d\) if and only if (i) every edge of \(G\) is contained in exactly two \(d\)-cliques, and (ii) any two \(d\)-cliques of \(G\) do not intersect in a single vertex (\(d\)-clique of \(G\) is, as usual, a maximal complete subgraph of \(G\) on \(d\) vertices).