  Two permutations of the vertices of a graph $G$ are called $G$-different if
there exists an index $i$ such that $i$-th entry of the two permutations form
an edge in $G$. We bound or determine the maximum size of a family of pairwise
$G$-different permutations for various graphs $G$. We show that for all
balanced bipartite graphs $G$ of order $n$ with minimum degree $n/2 - o(n)$,
the maximum number of pairwise $G$-different permutations of the vertices of
$G$ is $2^{(1-o(1))n}$. We also present examples of bipartite graphs $G$ with
maximum degree $O(\log n)$ that have this property. We explore the problem of
bounding the maximum size of a family of pairwise graph-different permutations
when an unlimited number of disjoint vertices is added to a given graph. We
determine this exact value for the graph of 2 disjoint edges, and present some
asymptotic bounds relating to this value for graphs consisting of the union of
$n/2$ disjoint edges.
