The Zero Forcing Number of Twisted Hypercubes

Abstract

Twisted hypercubes are graphs that generalize the structure of the hypercube by relaxing the symmetry constraint while maintaining degree-regularity and connectivity. We study the zero forcing number of twisted hypercubes. Zero forcing is a graph infection process in which a particular colour change rule is iteratively applied to the graph and an initial set of vertices. We use the alternative framing of forcing arc sets to construct a family of twisted hypercubes of dimension k$\ge 3$ with zero forcing sets of size $2^{k-1}-2^{k-3}+1$, which is below the minimum zero forcing number of the hypercube.