  We consider the problem of locating a single facility on a vertex in a given
graph based on agents' preferences, where the domain of the preferences is
either single-peaked or single-dipped. Our main interest is the existence of
deterministic social choice functions (SCFs) that are Pareto efficient and
false-name-proof, i.e., resistant to fake votes. We show that regardless of
whether preferences are single-peaked or single-dipped, such an SCF exists (i)
for any tree graph, and (ii) for a cycle graph if and only if its length is
less than six. We also show that when the preferences are single-peaked, such
an SCF exists for any ladder (i.e., 2-by-m grid) graph, and does not exist for
any larger hypergrid.
