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.