Is there a name for rooted graphs with this property? Suppose we have a graph $G=(V,E)$ and root $r\in V$. This graph has a special property. To demonstrate the property, we label each $v_i\in V$ with the length of the shortest $r$-$v_i$ path. The special property that $G$ has is that neighbors of each vertex $v_i$ with label $l_i$ has either label $l_i+1$ or $l_i-1$. Is there a name for rooted graphs with this property?
Note that such graphs can be layered so that edges only occur as two vertices in adjacent layers.
 A: Let's take it as given that $G$ must be connected, because otherwise we could not label every vertex as described.  I claim that a graph has the mentioned property if and only if it is bipartite.
Assume first that $G$ is not bipartite.  Then it must contain an odd cycle.  Consider such a cycle.  Obviously, the labels on adjacent vertices in this cycle cannot alternate parity, so there are two adjacent vertices on the cycle whose labels have the same parity.  Therefore, $G$ cannot have the property.
Now assume that $G$ is bipartite.  Obviously, the vertices are partitioned such that all the labels in the same part as $r$ are even and the other part has all of the odd labels.  Consider adjacent vertices $v_i,v_j$.  These vertices cannot have the same label: being adjacent they must be in different parts of the partition and thus their labels have different parities.  Without loss of generality, assume $v_i<v_j$.  Then there is a path of length $l_i$ from $r$ to $v_i$.  Simply appending the edge $\{v_i,v_j\}$ to the end of that path gives a path of length $l_i+1$ from $r$ to $v_i$.  Since we know $l_j>l_i$, this path assures us that $l_j=l_i+1$.  Since $v_i,v_j$ were arbitrary adjacent vertices, all adjacent vertices in $G$ must have labels that differ by only one.
