Folded Cube Graph

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 (Godsil 2004). Godsil observes that the independence number of the folded -cube graph is given by

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 following table summarizes special cases.

	folded -cube graph
2	2-path graph
3	tetrahedral graph
4	complete bipartite graph
5	Clebsch graph
6	Kummer graph

The bipartite double graph of the folded -cube graph is the hypercube graph .