Conway & Sloane's "Sphere Packings, Lattices and Groups" references Coxeter's "Regular Polytopes" for the phrase "halfcube", but Coxeter only uses the notation $h\Pi_n$, saying $h$ can be taken to stand for half- or hemi-, for an arbitrary polytope $\Pi_n$ {$p, q, \ldots, w$} with even $p$ (in your case, {$4,3,3,\ldots, 3$}) This construction is section 8.6 in Coxeter. Since then, halfcube seems to have lost favour, and hemi-cube has become the name for a construction of quotienting out vertices, while the term demicube (or demihypercube if you want to be explicit about using hypercubes and not cubes) is reserved for the construction of deleting vertices of a hypercube. See Conway, Burgiel and Goodman-Strass's "Symmetries of Things." Chapter 26 covers this, where they call them hemicubes, and draw some lovely pictures.

Specific dimensional cases have different names. Your $n=3$ case is the complete $K_4$. $n=4$ is the 16-cell, also called a hexadecachoron in older books, and happens to be a cross-polytope (this does not continue in higher dimensions). By $n=5$, the polytopes begin to take shape as their own specific family and no longer have multiple names. See http://en.wikipedia.org/wiki/Demihypercube, and various dimension specific pages there.

I do not know anything about the isoperimetric problem for these graphs, but there has likely been work done on the $n \leq 4$ cases, since those graphs also show up as other constructions.

line graphof the ordinary hypercube graph? $\endgroup$ – Zsbán Ambrus Nov 1 '11 at 22:39