Derangement Representation of Graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematical Sciences, Shahid Beheshti University, G.C., P.O. Box 19839-63113, Tehran, Iran

Abstract

A derangement k-representation of a graph G is a map π of V(G) to the symmetric group Sk, 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.

Keywords

Main Subjects

References

[1] Sagemath, the sage mathematics software system (version 9.4), The Sage Developers (2021), https://www.sagemath.org.
[2] L. Babai and V.T. S´os, Sidon sets in groups and induced subgraphs of Cayley graphs, Eur. J. Comb. 6 (1985), no. 2, 101–114.  https://doi.org/10.1016/S0195-6698(85)80001-9
[3] L.W. Beineke and R.J. Wilson, Topics in Algebraic Graph Theory, Cambridge University Press, 2004.
[4] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Publishing Company, Incorporated, 2008.
[5] A. Cayley, On the theory of groups, as depending on the symbolic equation θn=1, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 7 (1854), no. 42, 40–47.
[6] P. Erd¨os and A.B. Evans, Representations of graphs and orthogonal Latin square graphs, J. Graph Theory 13 (1989), no. 5, 593–595.  https://doi.org/10.1002/jgt.3190130509
[7] P. Erdös, A.W. Goodman, and L. Pósa, The representation of a graph by set intersections, Can. J. Math. 18 (1966), 106–112.  https://doi.org/10.4153/CJM-1966-014-3
[8] P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Comb. Theory Ser. A. 22 (1977), no. 3, 352–360.  https://doi.org/10.1016/0097-3165(77)90009-7
[9] C.C. Lindner, E. Mendelsohn, N.S. Mendelsohn, and B. Wolk, Orthogonal Latin square graphs, J. Graph Theory 3 (1979), no. 4, 325–338. https://doi.org/10.1002/jgt.3190030403
[10] C.C. Lindner and C.A. Rodger, Design Theory, Chapman and Hall/CRC, 2017.
[11] W.T. Trotter Jr and F. Harary, On double and multiple interval graphs, J. Graph Theory 3 (1979), no. 3, 205–211. https://doi.org/10.1002/jgt.3190030302
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 June 2025

Files

Share

How to cite

Statistics