Derangement Representation of Graphs

A derangement k-representation of a graph G is a map π of $V(G)$ to the symmetric group Sₖ, such that for any two vertices v and u of $V(G)$, v and u are adjacent if and only if π(v)(i) ≠ π(u)(i) for each i ∈ \1,2,3,…,k\. The derangement representation number of G denoted by $drn(G)$, is the minimum of k such that G has a derangement k-representation. In this paper, we prove that any graph has a derangement k-representation. Also, we obtain some lower and upper bounds for $drn(G)$, in terms of the basic parameters of G. Finally, we determine the exact value or give the better bounds of the derangement representation number of some classes of graphs.