01600909

j

01600909 Imrich, Wilfried Klav\v{z}ar, Sandi Vesel, Aleksander A characterization of halved cubes. Ars Comb. 48, 27-32 (1998). 1998 Charles Babbage Research Centre, Winnipeg, MB EN hypercube halved cube characterization 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\ge 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). Ivan Havel (Praha)