A characterization of halved cubes
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\). The 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).
- Distance-regular graphs and halved graphs
- On the characterization of the folded halved cubes by their intersection arrays
- scientific article; zbMATH DE number 764406 (Why is no real title available?)
- scientific article; zbMATH DE number 3895117 (Why is no real title available?)
- Automorphism groups of half cubes
- A characterization of planar partial cubes
This page was built for publication: A characterization of halved cubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2715935)