Is there a name for rooted graphs with this property?

58 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.