I want to label the vertices of a $3$-regular graph, using $2$ labels (say, Up, Down), with the constraint that if all the neighbors of a vertex are Up, the vertex must be Down; otherwise it must be Up.
For such a graph with $n$ vertices, how many different labellings are possible (as a function of $n$)?