  This paper considers the problem of Byzantine dispersion and extends previous
work along several parameters. The problem of Byzantine dispersion asks: given
$n$ robots, up to $f$ of which are Byzantine, initially placed arbitrarily on
an $n$ node anonymous graph, design a terminating algorithm to be run by the
robots such that they eventually reach a configuration where each node has at
most one non-Byzantine robot on it.
  Previous work solved this problem for rings and tolerated up to $n-1$
Byzantine robots. In this paper, we investigate the problem on more general
graphs. We first develop an algorithm that tolerates up to $n-1$ Byzantine
robots and works for a more general class of graphs.
  We then develop an algorithm that works for any graph but tolerates a lesser
number of Byzantine robots.
  We subsequently turn our focus to the strength of the Byzantine robots.
Previous work considers only ``weak" Byzantine robots that cannot fake their
IDs. We develop an algorithm that solves the problem when Byzantine robots are
not weak and can fake IDs.
  Finally, we study the situation where the number of the robots is not $n$ but
some $k$. We show that in such a scenario, the number of Byzantine robots that
can be tolerated is severely restricted. Specifically, we show that it is
impossible to deterministically solve Byzantine dispersion when $\lceil k/n
\rceil > \lceil (k-f)/n \rceil$.
