  We study the problem of assigning agents to the vertices of a graph such that
no pair of neighbors can benefit from swapping assignments -- a property we
term neighborhood stability. We further assume that agents' utilities are based
solely on their preferences over the assignees of adjacent vertices and that
those preferences are binary. Having shown that even this very restricted
setting does not guarantee neighborhood stable assignments, we focus on special
cases that provide such guarantees. We show that when the graph is a cycle or a
path, a neighborhood stable assignment always exists for any preference
profile. Furthermore, we give a general condition under which neighborhood
stable assignments always exist. For each of these results, we give a
polynomial-time algorithm to compute a neighborhood stable assignment.
