Some results on the graph of derangements

Articles in Press

Document Type : Research Paper

Authors

1 Department of Computer Science, University of Garmsar, Garmsar, Semnan, Iran.

2 Department of Mathematics, Faculty of Science, Razi University, Kermanshah, Iran.

Abstract

The graph of derangements, denoted by $\Gamma(D_n)$, is a simple graph whose vertex set is the set of all derangements on $[n]$ and two distinct vertices $f$ and $g$ are adjacent if and only if $f(i)\neq g(i)$, for every $i\in [n]$. In this paper, some properties of this graph are presented. The clique number and the vertex chromatic number of this graph are determined. Then we show that for every positive integer $n\geq 5$, $\Gamma(D_n)$ is neither a perfect graph nor a cograph. Moreover, this graph can not be a line graph unless $n\leq 4$. Maximum cliques and maximum independent sets are studied, too.

Keywords

References

[1] I. Anderson, A First Course in Discrete Mathematics, Springer Undergraduate Mathematics Series, Springer-Verlag London Ltd., London, 2001.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
[3] L. W. Beineke, Characterizations of derived graphs, J. Comb. Theory, 9 (1970) 129-135.
[4] Y. P. Deng and X. D. Zhan, Automorphism group of the derangement graph, Electron. J. Comb., 18 (2011) P198.
[5] R. J. Stones, S. Lin, X. Liu and G. Wang, On computing the number of Latin rectangles, Graphs Combin., 32 No. 3 (2016) 1187-1202.
[6] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2002.
[7] J. Zhang, D. Gray, H. Wang and X. D. Zhang, On the combinatorics of derangements and related permutations, Appl. Math. Comput., 431 (2022) 127341.
Algebraic Structures and Their Applications

Articles in Press, Corrected Proof
Available Online from 15 September 2025

Files

Share

How to cite

Statistics