The folded -cube
graph, perhaps better termed "folded hypercube graph," is a graph
obtained by merging vertices of the
-hypercube graph
that are antipodal, i.e., lie at a distance
(the graph diameter of
). Brouwer et al. 1989 (p. 222) use the
notation
for the folded
-cube
graph.
For , the folded
-cube graph is regular of
degree
. It has
vertices,
edges, and diameter
. The chromatic
number is 2 for
even and 4 for
odd (Sokolová 1987, Blokhuis et al. 2007). Godsil (2006) observes that
the independence number of the folded
-cube graph
is given by
|
(1)
|
a result which follows from Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even) (S. Wagon, pers. comm.).
Folded cube graphs are distance-regular and distance-transitive. The -folded cube graph contains the Möbius
ladder
as a subgraph for
and so is not unit-distance.
For even , the folded
-cube graph is bipartite,
and either of its halved graphs is a halved
folded cube graph. Equivalently, a halved
folded cube graph is obtained by identifying complementary vertices
in a halved cube graph of dimension
(Chan 2020, p. 772).
The following table summarizes special cases.
| folded | |
| 2 | 2-path graph |
| 3 | tetrahedral graph |
| 4 | complete bipartite graph |
| 5 | Clebsch graph |
| 6 | Kummer graph |
For odd , the bipartite
double graph of the folded
-cube graph is the hypercube
graph
. For even
, it consists of two disjoint
copies of the folded
-cube
graph.
For odd , the total
domination number satisfies
|
(2)
|
where
denotes the domination number of
. Indeed, the total
domination number of a bipartite double
graph is twice that of the original graph. Thus
, and the identity
of Azarija et al. (2017)
gives the result. The known hypercube graph formula
therefore yields
|
(3)
|
for
(Azarija et al. 2017). In particular, determining
is equivalent to determining the minimum size
of a binary covering code of length 10 and radius 1.
A second exact family follows by applying the Hamming code construction of Kwon and Lee (2014). For with
, represent
on the vector space
, with adjacent
vertices differing by a coordinate unit vector
or by the all-ones vector
. Let
be the
matrix whose columns
are all nonzero vectors of
. Each row contains
ones, so
. The set
is a Hamming code
of size
. For each graph
vertex
, the images under
of the
allowed neighbor displacements are exactly the
distinct vectors of
. Hence
has exactly one neighbor in
. Identifying complementary vertices
in the corresponding Hamming code construction on
gives
, since
is invariant under complementation.
Every total dominating set satisfies
by counting neighbor incidences. Consequently,
|
(4)
|
for . More generally, for
,
has an efficient open
dominating set iff
is a power of 2. Necessity follows
from
, and the construction proves sufficiency.