A halved 
-cube
graph is either of the two isomorphic connected
components of the graph distance graph 
at distance 2 of the 
-hypercube
graph 
.
The vertex set of 
is 
, with two vertices adjacent iff their graph distance in
is exactly 2.
Each component has 
vertices. A halved 
-cube graph is also called a half cube graph, the halved 
-cube, or sometimes the 
-demi-cube graph (Steinerberger 2023). The most common notation
for each component is 
(Godsil 2004), and it is also written 
. The slash in 
denotes restriction to one parity
class, thereby halving the vertex set, not replacing the dimension 
by 
to form the hypercube graph 
. In the distance-2 notation of
Luo et al. (2026),
 |
One copy contains the even-weight vectors and the other contains the odd-weight vectors. Steinerberger (2023)
uses the notation 
.
The halved 
-cube
graph can also be defined on the even-weight vectors in
, where two such vectors
are adjacent iff their
sum has weight two (Godsil 2004), or as the 2nd graph
power (i.e., the graph square) of 
, where 
denotes the 
-hypercube graph.
For even 
,
identifying complementary vertices in a halved 
-cube graph gives the halved
folded cube graph. The same graph results by first
forming the folded cube graph and then taking
either of its halved graphs (Chan 2020, p. 772).
Embeddings for small-order halved graphs are illustrated above and special cases are summarized in the table below.
 | name |
| 1 | singleton graph  |
| 2 | path graph  |
| 3 | tetrahedral graph  |
| 4 | 16-cell graph  |
| 5 | graph complement of the Clebsch graph |
The 5-halved cube graph is the graph complement of the Clebsch graph. It has Lovász
number 
(Fung 2011, p. 34). Note that Brouwer et al. (1989, pp. 104 and
224) confusingly use the term "Clebsch graph" to refer to the halved 5-cube
graph instead of the folded 5-cube graph meant
by other authors.
The 6-halved cube graph is a distance-regular graph with intersection array 
, and therefore also a Taylor
graph.
The chromatic numbers of the 
-halved cube graphs for 
, 5, ... are 4, 8, 8, 8, 8, 13 or 14, [13, 15], 
, 
, ... (Godsil 2004, p. 67; typos corrected). Brouwer
gives 
chromatic number 8 and independence
number 2; the values 4 and 5 belong to its graph
complement, the folded 5-cube graph.
Luo et al. (2026) proved that the quantum chromatic number of the 
-halved cube graph is
 |
when 
is a prime power satisfying 
, when 
for a positive integer 
, or when 
and 
and 
are odd prime powers. In
particular, 
while 
,
giving a strict quantum-classical separation.
The independence numbers of the 
-halved cube graphs for 
, 2, ... are 1, 1, 1, 2, 2, 4, 8, 16, 20, 40, 72, 144, ...,
where values for 
to 12 are from Godsil (2004, p. 67). This sequence appears identical to the
error-correcting coding function 
(OEIS A005864;
E. W. Weisstein, Dec. 31, 2015).
The domination numbers of 
-halved cube graphs for 
, 2, ... are 1, 1, 1, 2, 2, 2, 4, 7, 12, ..., which agrees
with OEIS A029866 for known terms (E. Weisstein,
Aug. 31, 2016).
