The halved cube graph 
is the graph distance graph at distance 2
of the 
-hypercube graph 
. Its vertex set is 
, with two vertices adjacent iff their graph distance in
is exactly 2.
is the disjoint
union of two isomorphic connected
components on 
vertices, each of which is called a halved 
-cube graph, 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.
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
agrees that 
has chromatic number 4 and gives its independence
number as 5.
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).
