# Derangement Representation of Graphs

Somayeh Ashofteh, Moharram N. Iradmusa
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 $\pi$ of $V(G)$ to
the symmetric group $S_{k}$, such that for any two vertices $v$ and $u$ of
$V(G)$, $v$ and $u$ are adjacent if and only if $\pi(v)(i)\neq\pi(u)(i)$ for
each $i\in\\{1,2,3,\ldots,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.

##  1 Introduction

All graphs we consider in this paper are simple, finite, and undirected. For a
graph $G$, we denote its vertex set and edge set by $V(G)$ and $E(G)$,
respectively. Also we use the notations $p(G)$, $q(G)$, $\omega(G)$ and
$G^{c}$ for the order, the size, the maximum size of cliques and the
complement graph of $G$, respectively. The path and the cycle of order $n$ are
denoted by $P_{n}$ and $C_{n}$, respectively. From now on, we use the notation
$[n]$ and $\mathbb{N}_{\geq n}$ instead of $\\{1,\ldots,n\\}$ and
$\\{m\in\mathbb{N}|\ m\geq n\\}$, respectively. We mention some definitions
that are referred to throughout this paper and for other necessary definitions
and notation we refer the reader to a standard text-book [3].
There are many geometric and algebraic representations of graphs, such as
intersection graphs, interval graphs [11], orthogonal latin square graphs [8],
and Cayley graphs. Formally, an intersection graph $G$ is a graph formed from
a family of finite sets $\mathcal{F}=\\{S_{1},S_{2},\ldots,S_{n}\\}$, by
creating one vertex $v_{i}$ for each set $S_{i}$, and connecting two vertices
$v_{i}$ and $v_{j}$ by an edge whenever the corresponding two sets have a
nonempty intersection, that is, $E(G)=\\{\\{v_{i},v_{j}\\}\mid i\neq j,\
S_{i}\cap S_{j}\neq\emptyset\\}$. The intersection number of a graph $G$ is
the minimum total number of elements in a representation of $G$ as an
intersection graph of finite sets. In 1966, Erdos et al. proved that the
intersection number of $G$ is at most $\frac{n^{2}}{4}$, where $n$ is the
order of $G$ [7].

Replacing the finite sets by open intervals, the interval number of a graph
$G$, denoted by $i(G)$, is the minimum $t$ such that $G$ is the intersection
graph of sets consisting of at most $t$ intervals on the real line [11]. Such
a description of $G$ is called a $t$-interval representation of $G$.

An orthogonal latin square graph (OLSG) is one in which the vertices are latin
squares of the same order and on the same symbols, and two vertices are
adjacent if and only if the corresponding latin squares are orthogonal [8].
Erdos and Evans proved that any finite graph can be realized as an orthogonal
latin square graph [6].

A Cayley graph is a graph on a group $G$ with connection set $S$ satisfying
$1\notin S$ and $S=S^{-1}$, denoted by $Cay(G,S)$, such that the vertices are
the elements of $G$ and there is an edge joining $g$ and $h$ if and only if
$h=sg$ for some $s\in S$ [2]. This concept was introduced by Arthur Cayley in
$1878$ [4]. We know that any Cayley graph is a vertex-transitive graph and so
the family of Cayley graphs is a proper subfamily of the family of all graphs.
But Babai and Sos in a probabilistic approach showed that if $G$ is a finite
graph, then every sufficiently large group has a Cayley graph containing an
induced subgraph isomorphic to $G$, precisely if $X$ is a finite graph of
order $n$ and $G$ is a group of order at least $c_{1}n^{3}$, then $X$ is
isomorphic to an induced subgraph of $Cay(G,S)$ for some $S\subseteq G$ [1].
Furthermore, in group theory, the Cayley theorem states that every group $G$
is isomorphic to a subgroup of a symmetric group [4]. Therefore the study of
Cayley graphs on symmetric groups has great importance.

The main objective of this work is to provide an algebraic approach for
finding a Cayley graph containing an induced subgraph that is isomorphic to
any given graph $G$. To show that we first, introduce a new representation of
graphs using derangements. A permutation on a finite set $X$ is a bijection on
$X$ and the set of all permutations on $X$ is denoted by $S_{X}$. When
$X=[n]$, $S_{X}$ is usually denoted by $S_{n}$. We use the notation
$(\pi_{1},\ldots,\pi_{n})$ for the permutation $\pi\in S_{n}$ where
$\pi(i)=\pi_{i}$ for each $i\in[n]$. A derangement $\sigma\in S_{n}$ is a
permutation that has no fixed points, which means $\sigma_{i}\neq i$ for all
$i\in[n]$. The set of all derangements of $S_{k}$ is denoted by $D_{k}$.

###### Definition 1

Let $G$ be a graph and $k\in\mathbb{N}$. We say $G$ is a derangement
$k$-representable if there exists an injective map $\pi:V(G)\rightarrow
S_{k}$, such that for any two vertices $v$ and $u$ of $G$, $v$ and $u$ are
adjacent if and only if $\pi(v)(i)\neq\pi(u)(i)$ for all $i\in[k]$. In other
words, $\pi(v)^{-1}\circ\pi(u)\in D_{k}$. In this case, $\pi$ is called a
derangement $k$-representation of $G$. The derangement representation number
of $G$, denoted by $drn(G)$, is the minimum of $k$ such that $G$ has a
derangement $k$-representation.

###### Example 2

Figure 1 shows a derangement 4-representation of $P_{3}$ ($=K_{3}-K_{2}$). In
addition, we prove that $P_{3}$ has no derangement 3-representation. Suppose
that $\pi:V(P_{3})\rightarrow S_{3}$ is a derangement 3-representation of
$P_{3}$. So $\pi(v_{1})^{-1}\circ\pi(v_{2})\in D_{3}$ and
$\pi(v_{2})^{-1}\circ\pi(v_{3})\in D_{3}$. In addition
$D_{3}=\\{\sigma,\sigma^{-1}\\}$, where $\sigma=(2,3,1)$. Therefore,
$\\{\pi(v_{1})^{-1}\circ\pi(v_{2}),\pi(v_{2})^{-1}\circ\pi(v_{3})\\}=\\{\sigma,\sigma^{-1}\\}$.
So we have
$\pi(v_{1})^{-1}\circ\pi(v_{2})\circ\pi(v_{2})^{-1}\circ\pi(v_{3})=\pi(v_{1})^{-1}\circ\pi(v_{3})=1$
which concludes $\pi(v_{1})=\pi(v_{3})$, a contradiction. Then $drn(P_{3})=4$.

$(1,2,3,4)$$(3,4,1,2)$$(1,2,4,3)$$v_{1}$$v_{2}$$v_{3}$ Figure 1: A derangement
4-representation of $P_{3}$

According to the Definition 1, we can prove the following theorem which shows
the relationship between Cayley graphs associated to the symmetric groups and
derangement representation of graphs.

###### Theorem 3

Let $G$ be a graph. Then $G$ is derangement $l$-representable if and only if
$G$ is isomorphic to an induced subgraph of $\Gamma=Cay(S_{l},D_{l})$.

As said before, the main result of [1] and Cayley theorem in group theory
confirm that any graph has a deranement $l$-representation for some
$l\in\mathbb{N}$. In the next theorems we will prove this fact by finding some
general upper bounds for derangement representation number of graphs.

###### Theorem 4

(1) $drn(K_{n})=n$ for any $n\in\mathbb{N}$.
(2) $drn(K_{n}-K_{2})=n$ for any positive integer $n\geq 4$.
(3) Let $G$ be a graph of order $n$ and $q(G^{c})\geq 2$. Then
$drn(G)\leq(n-1)q(G^{c})$.

A clique decomposition of a graph $G$ is a collection of non-trivial cliques
which partition the edge set of $G$.

###### Theorem 5

Let $G$ be a graph of order $n$, $D=\\{C_{1},C_{2},\ldots,C_{s}\\}$ be a
clique decomposition of $G^{c}$ and $s\geq 2$. Then

$drn(G)\leq s(n+1)-\sum_{i=1}^{s}p(C_{i}).$

###  1.1 Structure of the paper

After this introductory section where we established the background, purpose,
and some basic definitions and theorems of the paper, we divide the paper into
four sections. In Section 2, we prove Theorems 3, 4 and 5 and some basic
lemmas and theorems and introduce the concept derangement representation
matrix of graphs. In Section 3, we determine the exact value of the
derangement representation number for some nearly complete graphs and give the
better bounds of the parameter for some classes of graphs. In Section 4, we
present some computations that performed by SageMath [10] and in the last
section, we state some conjectures and open problems.

##  2 Proofs of Thorems 3, 4 and 5

At first, we prove Theorem 3.
Proof of Theorem 3. Let $G$ be a derangement $l$-representable graph and
$\pi:V(G)\rightarrow S_{l}$ be a derangement $l$-representation of $G$. Then
for each vertex $v_{i}$, $\pi(v_{i})$ is a vertex of $Cay(S_{l},D_{l})$ and
for every two vertices $v_{i}$ and $v_{j}$ of $G$, we have
$\pi(v_{i})^{-1}\circ\pi(v_{j})\in D_{l}$ if and only if $v_{i}$ and $v_{j}$
are adjacent. Therefore $\pi$ is an isomorphism from $G$ to the subgraph of
$Cay(S_{l},D_{l})$ induced by $\pi(V(G))$.
Now suppose that $G$ is isomorphic to an induced subgraph of
$Cay(S_{l},D_{l})$ and $\pi$ is this isomorphism. Easily one can show that
$\pi$ is a derangement $l$-representation of $G$. $\square$

###### Lemma 6

Let $G$ be a graph and $H$ be an induced subgraph of $G$. Then $drn(G)\geq
drn(H)$.

###### Proof

Suppose that $drn(G)=k$. Hence $G$ is isomorphic to an induced subgraph of
$Cay(S_{k},D_{k})$ such as $\Gamma$. Let $\alpha:V(G)\rightarrow V(\Gamma)$ be
an isomorphism. Therefore, the subgraph of $\Gamma$ induced by $\alpha(V(H))$
is isomorphic to $H$. So $H$ is isomorphic to an induced subgraph of
$Cay(S_{k},D_{k})$. Thus $H$ is derangement $k$-representable and so
$drn(H)\leq k$.  $\blacksquare$

In the next definition, we introduce an equivalent representation of graphs
using matrices.

###### Definition 7

Let $G$ be a graph with $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and $\pi$ is a
derangement $k$-representation of $G$. A derangement $k$-representation matrix
of $G$ associated to $\pi$ is defined as follows:

$L(\pi,G)=\begin{bmatrix}\pi(v_{1})(1)&\pi(v_{1})(2)&\cdots&\pi(v_{1})(k)\\\
\pi(v_{2})(1)&\pi(v_{2})(2)&\cdots&\pi(v_{2})(k)\\\
\vdots&\vdots&\ddots&\vdots\\\
\pi(v_{n})(1)&\pi(v_{n})(2)&\cdots&\pi(v_{n})(k)\end{bmatrix}$

The next definition is used in the proof of Theorem 4.

###### Definition 8

Let $L=[l_{i,j}]$ be a latin square of order $n-1$ and $1\leq r<s\leq n$. Then
$L(r,s)=[l^{\prime}_{i,j}]_{n\times(n-1)}$, where

$l^{\prime}_{i,j}=\begin{cases}l_{i,j}&i<s\\\ l_{r,j}&i=s\\\
l_{(i-1),j}&i>s\end{cases}.$

Note that in $L(r,s)$, $l^{\prime}_{i,j}\neq l^{\prime}_{i^{\prime},j}$ for
all $j\in[n-1]$ when $\\{r,s\\}\neq\\{i,i^{\prime}\\}$ and
$l^{\prime}_{i,j}=l^{\prime}_{i^{\prime},j}$ for all $j\in[n-1]$ when
$\\{r,s\\}=\\{i,i^{\prime}\\}$.

Proof of Theorem 4. (1) Any latin square of order $n$ is a derangement
$n$-representation matrix of $K_{n}$. So $drn(K_{n})\leq n$. Now suppose that
$\pi:V(K_{n})\rightarrow S_{k}$ is a derangement $k$-representation of
$K_{n}$. If $i\neq j$ then $\pi(v_{i})(1)\neq\pi(v_{j})(1)$. Therefore,
$|\\{\pi(v_{i})(1)|i\in[n]\\}|=n$. Hence we have $k\geq n$ and so
$drn(K_{n})=n$.
(2) Let $G=K_{n}-K_{2}$, $n\geq 4$ and $V(G)=\\{v_{1},\ldots,v_{n}\\}$.
Suppose that $v_{1}$ and $v_{2}$ are two non-adjacent vertices. Since
$G-v_{1}$ is a clique of $G$, $drn(G)\geq drn(G-v_{1})=n-1$. Now we choose a
latin square $L$ of order $n$ such that the first two rows of $L$ are
$R_{1}=[1\ 2\ 3\ 4\ \cdots\ n]$ and $R_{2}=[2\ 1\ 4\ 5\ \cdots\ n\ 3]$. Then
we replace $R_{2}$ with $R_{2}^{\prime}=[1\ 2\ 4\ 5\ \cdots\ n\ 3]$. The
resulting matix is a derangement $n$-representation matrix of $K_{n}$ ans so
$drn(K_{n})\leq n$. We prove that $drn(G)>n-1$. In contrary, suppose that
$A=[a_{i,j}]_{n\times(n-1)}$ is a derangement $(n-1)$-representation matrix of
$K_{n}-K_{2}$ where the corresponding vertex to $R_{i}$ (the $i$-th row of
$A$) is $v_{i}$ and $v_{1}\nsim v_{2}$. The subgraph $K_{n}-v_{1}$ and
$K_{n}-v_{2}$ are two cliques of order $n-1$. So the resulting matrices
obtained from $A$ by removing any row of $\\{R_{1},R_{2}\\}$ are latin squares
of order $n-1$. In these latin squares, the last $n-2$ rows are the same rows,
implying that $R_{1}=R_{2}$, a contradiction. Therefore $drn(K_{n}-K_{2})=n$.
(3) Suppose that $N=(n-1)q(G^{c})$, $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and
$E(G^{c})=\\{\\{v_{i_{t}},v_{j_{t}}\\}|1\leq t\leq m,i_{t}<j_{t}\\}$. Also
suppose that $L^{(1)},\ldots,L^{(m)}$ are latin squares of order $n-1$ with
mutually distinct symbols, such that the union set of all symbols is $[N]$.
Now consider the following block matrix:

$L=\bigg{[}\begin{array}[]{c|c|c|c}L^{(1)}(i_{1},j_{1})&L^{(2)}(i_{2},j_{2})&\cdots&L^{(m)}(i_{m},j_{m})\end{array}\bigg{]}.$

We show that $L$ is a derangement $N$-representation matrix of $G$ associated
to the map $\alpha:V(G)\rightarrow S_{N}$, where $\alpha(v_{i})$ is $i$-th row
of the matrix $L$. Suppose that $v_{i}$ and $v_{i^{\prime}}$ are adjacent.
Then $\\{i,i^{\prime}\\}\notin\\{\\{i_{t},j_{t}\\}|1\leq t\leq
m,i_{t}<j_{t}\\}$ and so $l^{\prime(k)}_{i,j}\neq
l^{\prime(k)}_{i^{\prime},j}$ for all $j\in[n-1]$ and all $k\in[m]$. Therefore
$\alpha(v_{i})(j)\neq\alpha(v_{i^{\prime}})(j)$ for all $j\in[N]$. Now suppose
that $v_{i}$ and $v_{i^{\prime}}$ are not adjacent. Then
$\\{i,i^{\prime}\\}=\\{i_{k_{0}},j_{k_{0}}\\}$ for some $k_{0}\in[m]$ and so
$l^{\prime(k_{0})}_{i,j}=l^{\prime(k_{0})}_{i^{\prime},j}$ for all
$j\in[n-1]$. Therefore $\alpha(v_{i})(j_{0})=\alpha(v_{i^{\prime}})(j_{0})$
for some $j_{0}\in[N]$. In addition, since $m\geq 2$, $L$ has $n$ different
rows and so $\alpha$ is an injective map. Therefore $drn(G)\leq N$. $\square$
Applying Lemma 6 and Theorem 4, we conclude the following corollary.

###### Corollary 9

Let $G$ be a graph with clique number $\omega(G)$. Then $drn(G)\geq\omega(G)$.

###### Definition 10

Let $L=[l_{i,j}]$ be a latin square of order $n-k+1$,
$S=\\{s_{1},\ldots,s_{k}\\}$ and $1\leq s_{1}<\cdots<s_{k}\leq n$. Then
$L(S)=[l^{\prime}_{i,j}]_{n\times(n-k+1)}$, where

$l^{\prime}_{i,j}=\begin{cases}l_{s_{1},j}&i\in\\{s_{2},\ldots,s_{k}\\}\\\
l_{i,j}&i<s_{2}\\\ l_{(i-1),j}&s_{2}<i<s_{3}\\\ l_{(i-2),j}&s_{3}<i<s_{4}\\\
\cdots&\cdots\\\ l_{(i-k+2),j}&s_{k-1}<i<s_{k}\\\
l_{(i-k+1),j}&s_{k}<i\end{cases}.$

Note that in $L(S)$, $l^{\prime}_{i,j}\neq l^{\prime}_{i^{\prime},j}$ for all
$j\in[n-1]$ when $\\{i,i^{\prime}\\}\nsubseteq S$ and
$l^{\prime}_{i,j}=l^{\prime}_{i^{\prime},j}$ for all $j\in[n-1]$ when
$\\{i,i^{\prime}\\}\subseteq S$.

Proof of Theorem 5. For any $i\in[s]$ let $N_{i}=n-p_{i}+1$ and $L^{(i)}$ be a
latin square of order $N_{i}$ where $p_{i}=p(C_{i})$. Suppose that
$A_{i}=V(C_{i})=\\{v^{i}_{j_{1}},\ldots,v^{i}_{j_{p_{i}}}\\}$. Then we have
$s$ latin squares $L^{(1)},\ldots,L^{(s)}$, with mutually distinct symbols
such that the union set of all symbols is $\\{1,2,\ldots,N\\}$ where
$N=\sum_{i=1}^{s}N_{i}=s(n+1)-\sum_{i=1}^{s}p_{i}$. Now consider the following
block matrix:

$L=\bigg{[}\begin{array}[]{c|c|c|c}L^{(1)}(A_{1})&L^{(2)}(A_{2})&\cdots&L^{(s)}(A_{s})\end{array}\bigg{]},$

in which $L^{(i)}(A_{i})$ is a matrix of order $n\times(n-p_{i}+1)$. We show
that $L$ is a derangement $N$-representation matrix of $G$ associated to the
map $\alpha:V(G)\rightarrow S_{N}$, where $\alpha(v_{i})$ is $i$-th row of the
matrix $L$. Suppose that $v_{i}$ and $v_{i^{\prime}}$ are adjacent. Then
$\\{i,i^{\prime}\\}\nsubseteq A_{t}$ for all $t\in[s]$ and so
$l^{\prime(k)}_{i,j}\neq l^{\prime(k)}_{i^{\prime},j}$ for all
$j\in[n-p_{k}+1]$ and all $k\in[s]$. Therefore
$\alpha(v_{i})(j)\neq\alpha(v_{i^{\prime}})(j)$ for all $j\in[N]$. Now suppose
that $v_{i}$ and $v_{i^{\prime}}$ are not adjacent. Then
$\\{i,i^{\prime}\\}\subseteq A_{k_{0}}$ for some $k_{0}\in[s]$ and so
$l^{\prime(k_{0})}_{i,j}=l^{\prime(k_{0})}_{i^{\prime},j}$ for all
$j\in[n-p_{k_{0}}+1]$. Therefore
$\alpha(v_{i})(j_{0})=\alpha(v_{i^{\prime}})(j_{0})$ for some $j_{0}\in[N]$.
In addition, since $s\geq 2$, $L$ has $n$ different rows and so $\alpha$ is an
injective map. Therefore $drn(G)\leq N$. $\square$

##  3 Improved results for some classes of graphs

In this section, we will calculate some better lower and upper bounds or the
exact amount of derangement representation numbers for specific families of
graphs.
To prove the next theorem, we need the definition of intersecting family of
permutations.

###### Definition 11

A subset $S$ of $S_{n}$ is intersecting if for any two permutations $g$ and
$h$ in $S$, $g(i)=h(i)$ for some $i\in[n]$ or equivalently $h^{-1}\circ
g\notin D_{n}$.

In [5], M. Deza and P. Frankl proved that $|S|\leq(n-1)!$ for any intersecting
family $S$ of permutations of symmetric group $S_{n}$.

###### Theorem 12

Let $n,k\in\mathbb{N}$ and $(k-1)!<n\leq k!$. Then
$drn(\overline{K_{n}})=k+1$.

###### Proof

Suppose that $drn((\overline{K_{n}})=t$ and
$\pi:V(\overline{K_{n}})\rightarrow S_{t}$ is a derangement $t$-representation
of $\overline{K_{n}}$. Therefore $\pi(V(\overline{K_{n}}))$ is an intersecting
subset of $S_{t}$ and so $|\pi(V(\overline{K_{n}}))|=n\leq(t-1)!$. Thus
$t-1\geq k$ and hence $drn((\overline{K_{n}})=t\geq k+1$.
To complete the proof, we give a derangement $(k+1)$-representation matrix of
$\overline{K_{n}}$. Let $A=[a_{i,j}]_{n\times k}$ be a matrix that its rows
represent $n$ permutations of $S_{k}$. Then the following matrix is a
derangement $(k+1)$-representation matrix of $\overline{K_{n}}$:

$L(\overline{K_{n}})=\left[\begin{array}[]{c|c}\begin{array}[]{c}k+1\\\
\vdots\\\ k+1\end{array}&A\end{array}\right].$

$\blacksquare$

we know that $drn(K_{n})=drn(K_{n}-K_{2})=n$. Now we investigate to find the
derangement representation number of nearly complete graphs. A graph is nearly
complete if it can be obtained by removing a small number of edges from a
complete graph relative to the size of the graph.

###### Theorem 13

(1) $drn(K_{n}-P_{3})=n$ when $n\in\\{3,4\\}$, and
(2) $drn(K_{n}-P_{3})=n-1$ when $n\in\mathbb{N}_{\geq 5}$.

###### Proof

(1) $\overline{K_{2}}$ is an induced subgraph of $K_{3}-P_{3}$. So
$drn(K_{3}-P_{3})\geq drn(\overline{K_{2}})=3$ by Theorem 12 and Lemma 6. In
addition, the following matrix is a derangement $3$-representation matrix of
$K_{3}-P_{3}$:

$L(K_{3}-P_{3})=\left[\begin{array}[]{ccc}{\bf 1}&2&3\\\ 2&{\bf 3}&1\\\ {\bf
1}&{\bf 3}&2\\\ \end{array}\right].$

Therefore, $drn(K_{3}-P_{3})=3$.
$P_{3}$ is an induced subgraph of $K_{4}-P_{3}$. So $drn(K_{4}-P_{3})\geq
drn(P_{3})=4$ by Lemma 6 and Example 2. In addition, the following matrix is a
derangement $4$-representation matrix of $K_{4}-P_{3}$:

$L(K_{3}-P_{3})=\left[\begin{array}[]{cccc}{\bf 1}&{\bf 2}&3&4\\\ 4&1&2&{\bf
3}\\\ 3&4&1&2\\\ {\bf 1}&{\bf 2}&4&{\bf 3}\\\ \end{array}\right].$

Therefore, $drn(K_{4}-P_{3})=4$.
(2) $K_{n-1}$ is an induced subgraph of $K_{n}-P_{3}$. So
$drn(K_{n}-P_{3})\geq drn(K_{n-1})=n-1$ by Lemma 6. Suppose that $A$ is a
latin square of order $n-1$ such that the first two rows of $A$ are
$R_{1}=\left[\begin{array}[]{ccccccc}1&2&3&4&5&\cdots&n-1\\\
\end{array}\right]$ and
$R_{2}=\left[\begin{array}[]{ccccccc}2&1&n-1&3&4&\cdots&n-2\\\
\end{array}\right]$. Now the following matrix is a derangement
$(n-1)$-representation matrix of $K_{n}-P_{3}$:

$L(K_{n}-P_{3})=\left[\begin{array}[]{c}A\\\
\hline\cr\begin{array}[]{ccccccc}1&2&n-1&3&4&\cdots&n-2\\\
\end{array}\end{array}\right].$

Therefore, $drn(K_{n}-P_{3})=n-1$.  $\blacksquare$

###### Theorem 14

(1) $drn(K_{n}-2K_{2})=n$ when $n\in\\{4,5,6\\}$, and
(2) $drn(K_{n}-2K_{2})=n-1$ when $n\in\mathbb{N}_{\geq 7}$.

###### Proof

(1) $P_{3}$ is an induced subgraph of $K_{4}-2K_{2}$. So
$drn(K_{3}-2K_{2})\geq drn(P_{3})=4$ by Lemma 6. In addition, the following
matrix is a derangement $4$-representation matrix of $K_{4}-2K_{2}$:

$L(K_{4}-2K_{2})=\left[\begin{array}[]{cccc}{\bf 1}&{\bf 2}&3&4\\\ {\bf
1}&{\bf 2}&4&3\\\ 3&4&{\bf 1}&{\bf 2}\\\ 4&3&{\bf 1}&{\bf 2}\\\
\end{array}\right].$

Therefore, $drn(K_{4}-2K_{2})=4$.
The following matrix is a derangement $5$-representation matrix of
$K_{5}-2K_{2}$:

$L(K_{4}-2K_{2})=\left[\begin{array}[]{ccccc}5&{\bf 2}&3&4&1\\\ 1&{\bf
2}&4&5&3\\\ {\bf 3}&5&1&2&4\\\ {\bf 3}&4&5&1&2\\\ 4&1&2&3&5\\\
\end{array}\right].$

Therefore, $drn(K_{5}-2K_{2})\leq 5$. We show that $drn(K_{5}-2K_{2})>4$. In
contrary, suppose that $A=[a_{i,j}]_{5\times 4}$ is a derangement
$4$-representation matrix of $K_{5}-2K_{2}$ where the corresponding vertex to
the $i$-th row is $v_{i}$, $v_{1}\nsim v_{2}$ and $v_{3}\nsim v_{4}$.
Therefore we have $a_{1,j}=a_{2,j}$ or $a_{3,j}=a_{4,j}$ in each column
$C_{j}$ of $A$. In addition $1\leq|\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}|\leq 2$ and
$1\leq|\\{j\in[4]|\ a_{3,j}=a_{4,j}\\}|\leq 2$. So $|\\{j\in[4]|\
a_{1,j}=a_{2,j}\\}|=|\\{j\in[4]|\ a_{3,j}=a_{4,j}\\}|=2$ and $\\{j\in[4]|\
a_{1,j}=a_{2,j}\\}\cap\\{j\in[4]|\ a_{3,j}=a_{4,j}\\}=\emptyset$. Without loss
of generality, assume that

$A=\left[\begin{array}[]{ccccc}{\bf a}&{\bf b}&c&d\\\ {\bf a}&{\bf b}&d&c\\\
c&d&{\bf a}&{\bf b}\\\ d&c&{\bf a}&{\bf b}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}\\\ \end{array}\right].$

So $a_{5,1}=a_{5,3}=b$ and $a_{5,2}=a_{5,4}=a$, a contradiction. Therefore,
$drn(K_{5}-2K_{2})=5$.
The following matrix is a derangement $6$-representation matrix of
$K_{6}-2K_{2}$:

$L(K_{6}-2K_{2})=\left[\begin{array}[]{cccccc}{\bf 2}&6&{\bf 4}&1&3&{\bf 5}\\\
{\bf 2}&1&{\bf 4}&3&6&{\bf 5}\\\ {\bf 3}&4&5&{\bf 6}&1&{\bf 2}\\\ {\bf
3}&5&1&{\bf 6}&4&{\bf 2}\\\ 1&2&3&4&5&6\\\ 4&3&6&5&2&1\\\ \end{array}\right].$

Therefore, $drn(K_{6}-2K_{2})\leq 6$. We show that $drn(K_{6}-2K_{2})>5$. In
contrary, suppose that $A=[a_{i,j}]_{6\times 5}$ is a derangement
$5$-representation matrix of $K_{6}-2K_{2}$ where the corresponding vertex to
the $i$-th row is $v_{i}$, $v_{1}\nsim v_{2}$ and $v_{3}\nsim v_{4}$.
Therefore we have $a_{1,j}=a_{2,j}$ or $a_{3,j}=a_{4,j}$ in each column
$C_{j}$ of $A$. In addition $1\leq|\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}|\leq 3$ and
$1\leq|\\{j\in[4]|\ a_{3,j}=a_{4,j}\\}|\leq 3$. So there are three cases:
Case 1. $|\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}|=|\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}|=3$ and $\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}\cap\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}=\\{j_{0}\\}$. Without loss of generality, assume that
$j_{0}=3$, $\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}=\\{1,2,3\\}$ and $\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}=\\{3,4,5\\}$ and

$A=\left[\begin{array}[]{cccccc}{\bf a}&{\bf b}&{\bf c}&d&e\\\ {\bf a}&{\bf
b}&{\bf c}&e&d\\\ a_{3,1}&a_{3,2}&{\bf x}&{\bf y}&{\bf z}\\\
a_{4,1}&a_{4,2}&{\bf x}&{\bf y}&{\bf z}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}&a_{5,5}\\\
a_{6,1}&a_{6,2}&a_{6,3}&a_{6,4}&a_{6,5}\\\ \end{array}\right].$

In this case, we have $y,z\notin\\{d,e\\}$ and hence
$\\{d,e\\}\setminus\\{x,y,z\\}\neq\emptyset$. Therefore at least one of
numbers $\\{d,e\\}$ must apear in the cells $\\{a_{3,1},a_{4,2}\\}$ or
$\\{a_{4,1},a_{3,2}\\}$. But in this case, that number must apear in the cells
$\\{a_{5,3},a_{6,3}\\}$, a contradiction.
Case 2. $|\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}|=2$ and $|\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}|=3$ and $\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}\cap\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}=\emptyset$. Without loss of generality, assume that
$\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}=\\{1,2\\}$ and $\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}=\\{3,4,5\\}$ and

$A=\left[\begin{array}[]{cccccc}{\bf a}&{\bf b}&c&d&e\\\ {\bf a}&{\bf
b}&d&e&c\\\ a_{3,1}&a_{3,2}&{\bf x}&{\bf y}&{\bf z}\\\ a_{4,1}&a_{4,2}&{\bf
x}&{\bf y}&{\bf z}\\\ a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}&a_{5,5}\\\
a_{6,1}&a_{6,2}&a_{6,3}&a_{6,4}&a_{6,5}\\\ \end{array}\right].$

In this case, we have $|\\{x,y,z\\}\cap\\{c,d,e\\}|=1$ and hence
$|\\{c,d,e\\}\setminus\\{x,y,z\\}|=2$. Therefore two numbers of $\\{c,d,e\\}$
must apear in the cells $\\{a_{3,1},a_{4,2},a_{4,1},a_{3,2}\\}$. But in this
case, that numbers must apear in the cells $\\{a_{5,3},a_{6,3}\\}$, a
contradiction.
Case 3. $|\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}|=3$ and $|\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}|=2$ and $\\{j\in[4]|\ a_{1,j}=a_{2,j}\\}\cap\\{j\in[4]|\
a_{3,j}=a_{4,j}\\}=\emptyset$. This case is similar to the previous case.
Therefore, $drn(K_{6}-2K_{2})=6$.
(2) $K_{n-1}-K_{2}$ is an induced subgraph of $K_{n}-2K_{2}$. So
$drn(K_{n}-2K_{2})\geq drn(K_{n-1}-K_{2})=n-1$ by Lemma 6 and Theorem 4.
Suppose that $A$ is a latin square of order $n-1$ such that the first three
rows of $A$ are
$R_{1}=\left[\begin{array}[]{ccccccccc}1&2&3&|&4&5&\cdots&n-2&n-1\\\
\end{array}\right]$ (corresponding to $v_{1}$),
$R_{2}=\left[\begin{array}[]{ccccccccc}3&1&2&|&5&6&\cdots&n-1&4\\\
\end{array}\right]$ (corresponding to $v_{2}$), and
$R_{3}=\left[\begin{array}[]{ccccccccc}2&3&1&|&6&7&\cdots&4&5\\\
\end{array}\right]$ (corresponding to $v_{3}$). At first, we replace the
second row of $A$ with

$R^{\prime}_{2}=\left[\begin{array}[]{ccccccccc}1&2&3&|&5&6&\cdots&n-1&4\\\
\end{array}\right]$

to achieve a derangement $(n-1)$-representation matrix $A^{\prime}$ of
$K_{n-1}-K_{2}$ in which $v_{1}$ and $v_{2}$ are not adjacent. Now the
following matrix is a derangement $(n-1)$-representation matrix of
$K_{n}-2K_{2}$:

$L(K_{n}-2K_{2})=\left[\begin{array}[]{c}A^{\prime}\\\
\hline\cr\begin{array}[]{ccccccccc}3&1&2&|&6&7&\cdots&4&5\\\
\end{array}\end{array}\right],$

where the second part of the $n$-th row is the second part of the third row
and the corresponding vertex to the last row is not adjacent to $v_{3}$.
Therefore, $drn(K_{n}-2K_{2})=n-1$.  $\blacksquare$

###### Theorem 15

(1) $drn(K_{n}-K_{3})=n$ when $n\in\\{4,5,6\\}$, and
(2) $drn(K_{n}-K_{3})=n-1$ when $n\in\mathbb{N}_{\geq 7}$.

###### Proof

(1) $P_{3}$ is an induced subgraph of $K_{4}-K_{3}$. So $drn(K_{4}-K_{3})\geq
drn(P_{3})=4$ by Lemma 6. In addition, the following matrix is a derangement
$4$-representation matrix of $K_{4}-2K_{2}$:

$L(K_{4}-2K_{2})=\left[\begin{array}[]{cccc}{\bf 1}&{\bf 4}&2&3\\\ {\bf
1}&{\bf 4}&{\bf 3}&2\\\ {\bf 1}&2&{\bf 3}&4\\\ 2&3&4&1\\\ \end{array}\right].$

Therefore, $drn(K_{4}-K_{3})=4$.
The following matrix is a derangement $5$-representation matrix of
$K_{5}-K_{3}$:

$L(K_{5}-K_{3})=\left[\begin{array}[]{ccccc}{\bf 1}&{\bf 2}&3&4&{\bf 5}\\\
{\bf 1}&4&{\bf 3}&2&{\bf 5}\\\ 4&{\bf 2}&{\bf 3}&1&{\bf 5}\\\ 2&3&5&4&1\\\
3&1&2&5&4\\\ \end{array}\right].$

Therefore, $drn(K_{5}-K_{3})\leq 5$. We show that $drn(K_{5}-K_{3})>4$. In
contrary, suppose that $A=[a_{i,j}]_{5\times 4}$ is a derangement
$4$-representation matrix of $K_{5}-K_{3}$ where the corresponding vertex to
the $i$-th row is $v_{i}$, $v_{1}\nsim v_{2}$, $v_{1}\nsim v_{3}$ and
$v_{2}\nsim v_{3}$. Therefore we have $a_{1,j}=a_{2,j}$, $a_{2,j}=a_{3,j}$ or
$a_{3,j}=a_{1,j}$ in each column $C_{j}$ of $A$. Let $a^{i,j}=|\\{k\in[4]|\
a_{i,k}=a_{j,k}\\}|$. So $1\leq a^{i,j}\leq 2$ for any
$\\{i,j\\}\subset\\{1,2,3\\}$ and $a^{1,2}+a^{2,3}+a^{3,1}\geq 4$. So
$a^{i,j}=2$ for some $\\{i,j\\}\subset\\{1,2,3\\}$. Without loss of
generality, assume that $a^{1,2}=2$ and

$A=\left[\begin{array}[]{ccccc}{\bf a}&{\bf b}&c&d\\\ {\bf a}&{\bf b}&d&c\\\
a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}\\\ a_{4,1}&a_{4,2}&a_{4,3}&a_{4,4}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}\\\ \end{array}\right].$

If $(a_{3,3},a_{3,4})=(a_{1,3},a_{2,4})$ or $(a_{1,4},a_{2,3})$ then
$a_{3,3}=a_{3,4}$, a contradiction. If $(a_{3,3},a_{3,4})=(c,d)$, then
$a_{3,1}=a$ or $a_{3,2}=b$ which force the equality of the first and the third
rows, a contradiction. Similarly, we have a contradiction when
$(a_{3,3},a_{3,4})=(d,c)$. Therefore, $drn(K_{5}-K_{3})=5$.
The following matrix is a derangement $6$-representation matrix of
$K_{6}-K_{3}$:

$L(K_{6}-K_{3})=\left[\begin{array}[]{cccccc}{\bf 1}&{\bf 2}&3&4&{\bf 5}&{\bf
6}\\\ {\bf 1}&{\bf 2}&{\bf 4}&{\bf 3}&6&5\\\ 2&1&{\bf 4}&{\bf 3}&{\bf 5}&{\bf
6}\\\ 3&4&5&6&1&2\\\ 4&3&6&5&2&1\\\ 5&6&1&2&3&4\\\ \end{array}\right].$

Therefore, $drn(K_{6}-K_{3})\leq 6$. We show that $drn(K_{6}-K_{3})>5$. In
contrary, suppose that $A=[a_{i,j}]_{6\times 5}$ is a derangement
$5$-representation matrix of $K_{6}-K_{3}$ where the corresponding vertex to
the $i$-th row is $v_{i}$, $v_{1}\nsim v_{2}$, $v_{2}\nsim v_{3}$ and
$v_{3}\nsim v_{1}$. Therefore we have $a_{1,j}=a_{2,j}$, $a_{2,j}=a_{3,j}$ or
$a_{3,j}=a_{1,j}$ in each column $C_{j}$ of $A$. Let $a^{i,j}=|\\{k\in[4]|\
a_{i,k}=a_{j,k}\\}|$. So $1\leq a^{i,j}\leq 3$ for any
$\\{i,j\\}\subset\\{1,2,3\\}$ and $a^{1,2}+a^{2,3}+a^{3,1}\geq 5$. So there
are two cases:
Case 1. $a^{i,j}=3$ for some $\\{i,j\\}\subset\\{1,2,3\\}$. Without loss of
generality, assume that $a^{1,2}=3$ and $\\{j\in[4]|\
a_{1,j}=a_{2,j}\\}=\\{1,2,3\\}$. Therefore,

$A=\left[\begin{array}[]{cccccc}{\bf a}&{\bf b}&{\bf c}&d&e\\\ {\bf a}&{\bf
b}&{\bf c}&e&d\\\ a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}&a_{3,5}\\\
a_{4,1}&a_{4,2}&a_{4,3}&a_{4,4}&a_{4,5}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}&a_{5,5}\\\
a_{6,1}&a_{6,2}&a_{6,3}&a_{6,4}&a_{6,5}\\\ \end{array}\right].$

If $(a_{3,4},a_{3,5})=(a_{1,4},a_{2,5})$ or $(a_{1,5},a_{2,4})$ then
$a_{3,4}=a_{3,5}$, a contradiction. If
$(a_{3,4},a_{3,5})\in\\{(d,e),(e,d)\\}$, then
$(a_{3,1},a_{3,2},a_{3,3})\in\\{(a,c,b),(c,b,a),(b,a,c)\\}$. Without loss of
generality, assume that $(a_{3,4},a_{3,5})=(d,e)$ and
$(a_{3,1},a_{3,2},a_{3,3})=(a,c,b)$. Then

$A=\left[\begin{array}[]{cccccc}{\bf a}&{\bf b}&{\bf c}&{\bf d}&{\bf e}\\\
{\bf a}&{\bf b}&{\bf c}&e&d\\\ {\bf a}&c&b&{\bf d}&{\bf e}\\\
a_{4,1}&a_{4,2}&a_{4,3}&a_{4,4}&a_{4,5}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}&a_{5,5}\\\
a_{6,1}&a_{6,2}&a_{6,3}&a_{6,4}&a_{6,5}\\\ \end{array}\right].$

But in this case we have $\\{b,c,d,e\\}\subset\\{a_{4,1},a_{5,1},a_{6,1}\\}$,
a contradiction.
Case 2. $a^{i,j}=2$ and $a^{j,k}=2$ where $\\{i,j,k\\}=[3]$. Without loss of
generality, assume that $a^{1,2}=a^{2,3}=2$ and $\\{j\in[5]|\
a_{1,j}=a_{2,j}\\}=\\{1,2\\}$ and $\\{j\in[5]|\ a_{2,j}=a_{3,j}\\}=\\{3,4\\}$
and

$A=\left[\begin{array}[]{cccccc}{\bf a}&{\bf b}&c&d&e\\\ {\bf a}&{\bf b}&{\bf
d}&{\bf e}&c\\\ a_{3,1}&a_{3,2}&{\bf d}&{\bf e}&a_{3,5}\\\
a_{4,1}&a_{4,2}&a_{4,3}&a_{4,4}&a_{4,5}\\\
a_{5,1}&a_{5,2}&a_{5,3}&a_{5,4}&a_{5,5}\\\
a_{6,1}&a_{6,2}&a_{6,3}&a_{6,4}&a_{6,5}\\\ \end{array}\right].$

Since
$\\{a_{1,5},a_{2,5},a_{3,5}\\}\cap\\{a_{4,5},a_{5,5},a_{6,5}\\}=\emptyset$ and
$\\{a_{1,5},a_{2,5},a_{3,5}\\}\cup\\{a_{4,5},a_{5,5},a_{6,5}\\}\subseteq[5]$
hence $a_{3,5}\in\\{c,e\\}$. But $a_{3,5}\neq a_{3,4}=e$ and so $a_{3,5}=c$,
which contradicts by $a^{2,3}=2$.
Therefore, $drn(K_{6}-K_{3})=6$.
(2) $K_{n-2}$ is an induced subgraph of $K_{n}-K_{3}$. So
$drn(K_{n}-K_{3})\geq drn(K_{n-2})=n-2$ by Lemma 6 and Theorem 4. We show that
$drn(K_{n}-K_{3})>n-2$. In contrary, suppose that $A=[a_{i,j}]_{n\times(n-2)}$
is a derangement $(n-2)$-representation matrix of $K_{n}-K_{3}$ where the
corresponding vertex to $R_{i}$ (the $i$-th row of $A$) is $v_{i}$,
$v_{1}\nsim v_{2}$, $v_{2}\nsim v_{3}$ and $v_{3}\nsim v_{1}$. The subgraphs
induced by removing any two vertices of $\\{v_{1},v_{2},v_{3}\\}$ are cliques
of order $n-2$. So the resulting matrices obtained from $A$ by removing any
two rows of $\\{R_{1},R_{2},R_{3}\\}$ are latin squares of order $n-2$. In
these latin squares, the last $n-3$ rows are the same rows, implying that
$R_{1}=R_{2}=R_{3}$, a contradiction.
Suppose that $A$ is a latin square of order $n-1$ such that the first two rows
of $A$ are

$R_{1}=\left[\begin{array}[]{ccccccccccc}1&2&|&3&4&|&5&6&\cdots&n-2&n-1\\\
\end{array}\right]$

(corresponding to $v_{1}$) and
$R_{2}=\left[\begin{array}[]{ccccccccccc}2&1&|&4&3&|&6&7&\cdots&n-1&5\\\
\end{array}\right]$ (corresponding to $v_{2}$). At first, we replace the
second row of $A$ by
$R^{\prime}_{2}=\left[\begin{array}[]{ccccccccccc}1&2&|&4&3&|&6&7&\cdots&n-1&5\\\
\end{array}\right]$ to achieve a derangement $(n-1)$-representation matrix
$A^{\prime}$ of $K_{n-1}-K_{2}$ in which $v_{1}$ and $v_{2}$ are not adjacent.
Now the following matrix is a derangement $(n-1)$-representation matrix of
$K_{n}-K_{3}$:

$L(K_{n}-K_{3})=\left[\begin{array}[]{c}A^{\prime}\\\
\hline\cr\begin{array}[]{ccccccccccc}2&1&|&3&4&|&6&7&\cdots&n-1&5\\\
\end{array}\end{array}\right],$

where the second part of the $n$-th row is the second part of the second row
and the corresponding vertex to the last row is not adjacent to $v_{1}$ and
$v_{2}$. Therefore, $drn(K_{n}-K_{3})=n-1$.  $\blacksquare$

###### Theorem 16

(1) $drn(K_{4}-P_{4})=4$.
$drn(K_{n}-P_{4})=n-1$ when $n\in\mathbb{N}_{\geq 5}$.

###### Proof

(1) Obviously, $K_{4}-P_{4}\cong P_{4}$. Also $P_{3}$ is an induced subgraph
of $K_{3}-P_{4}$. So $drn(K_{4}-P_{4})\geq drn(P_{3})=4$ by Lemma 6 and
Theorem 4.
In addition, the following matrix is the derangement $4$-representation matrix
of $K_{4}-P_{4}$ and so $drn(K_{4}-P_{4})=4$.

$L(K_{4}-P_{4})=\left[\begin{array}[]{cccc}{\bf 1}&2&{\bf 3}&{\bf 4}\\\ {\bf
2}&1&4&3\\\ {\bf 1}&4&{\bf 3}&2\\\ {\bf 2}&3&1&{\bf 4}\\\ \end{array}\right].$

(2) Suppose that $G=K_{n}-P_{4}$, $V(G)=\\{v_{i}|\ i\in[n]\\}$, $v_{1}\nsim
v_{2}$, $v_{2}\nsim v_{n}$ and $v_{n}\nsim v_{3}$. $G-v_{n}\cong
K_{n-1}-K_{2}$ is an induced subgraph of $K_{n}-P_{4}$. So
$drn(K_{n}-P_{4})\geq drn(K_{n-1}-K_{2})=n-1$ by Lemma 6 and Theorem 4.
For $n\in\\{5,6\\}$, the following matrices are the derangement
$(n-1)$-representation matrices of $K_{n}-P_{4}$:

$L(K_{5}-P_{4})=\left[\begin{array}[]{cccc}1&2&3&4\\\ {\bf 3}&{\bf 4}&2&{\bf
1}\\\ {\bf 2}&1&{\bf 4}&3\\\ {\bf 3}&{\bf 4}&1&2\\\ {\bf 2}&3&{\bf 4}&{\bf
1}\\\ \end{array}\right],L(K_{6}-P_{4})=\left[\begin{array}[]{ccccc}{\bf
1}&2&{\bf 3}&{\bf 4}&{\bf 5}\\\ {\bf 2}&{\bf 1}&{\bf 3}&{\bf 5}&4\\\ {\bf
2}&{\bf 1}&4&{\bf 5}&3\\\ {\bf 1}&3&2&{\bf 4}&{\bf 5}\\\ 4&5&1&3&2\\\
3&4&5&2&1\\\ \end{array}\right].$

Now suppose that $n\geq 7$ and $A$ is a latin square of order $n-1$ such that
the first three rows of $A$ are

$R_{1}=\left[\begin{array}[]{ccccccccc}1&2&3&|&4&5&\cdots&n-2&n-1\\\
\end{array}\right]$

(corresponding to $v_{1}$),
$R_{2}=\left[\begin{array}[]{ccccccccc}2&3&1&|&5&6&\cdots&n-1&4\\\
\end{array}\right]$ (corresponding to $v_{2}$) and
$R_{3}=\left[\begin{array}[]{ccccccccc}3&1&2&|&6&\cdots&n-1&4&5\\\
\end{array}\right]$ (corresponding to $v_{3}$). At first, we replace the
second row of $A$ by
$R^{\prime}_{2}=\left[\begin{array}[]{ccccccccc}1&2&3&|&5&6&\cdots&n-1&4\\\
\end{array}\right]$ to achieve a derangement $(n-1)$-representation matrix
$A^{\prime}$ of $G-v_{n}$ in which $v_{1}$ and $v_{2}$ are not adjacent. Now
the following matrix is a derangement $(n-1)$-representation matrix of $G$:

$L(K_{n}-P_{4})=\left[\begin{array}[]{c}A^{\prime}\\\
\hline\cr\begin{array}[]{ccccccccccc}3&1&2&|&5&6&\cdots&n-1&4\\\
\end{array}\end{array}\right],$

where the second part of the $n$-th row is the second part of the second row
and the corresponding vertex to the last row ($v_{n}$) is not adjacent to
$v_{2}$ and $v_{3}$. Therefore, $drn(K_{n}-K_{3})=n-1$.  $\blacksquare$

###### Theorem 17

$drn(K_{n}-(P_{3}\cup P_{2}))=n-1$ when $n\in\mathbb{N}_{\geq 5}$.

###### Proof

Suppose that $G=K_{n}-(P_{3}\cup P_{2})$, $V(G)=\\{v_{i}|\ i\in[n]\\}$,
$v_{1}\nsim v_{2}$, $v_{n}\nsim v_{3}$ and $v_{n}\nsim v_{4}$. $G-v_{n}\cong
K_{n-1}-K_{2}$ is an induced subgraph of $G$. So $drn(G)\geq
drn(K_{n-1}-K_{2})=n-1$ by Lemma 6 and Theorem 4.
For $n\in\\{5,6\\}$, the following matrices are the derangement
$(n-1)$-representation matrices of $G$:

$L(K_{5}-(P_{3}\cup P_{2}))=\left[\begin{array}[]{cccc}1&2&{\bf 3}&{\bf 4}\\\
2&1&{\bf 3}&{\bf 4}\\\ {\bf 3}&{\bf 4}&1&2\\\ 4&3&{\bf 2}&{\bf 1}\\\ {\bf
3}&{\bf 4}&{\bf 2}&{\bf 1}\\\ \end{array}\right],L(K_{6}-(P_{3}\cup
P_{2})=\left[\begin{array}[]{ccccc}1&2&{\bf 3}&{\bf 4}&{\bf 5}\\\ 2&1&{\bf
3}&{\bf 4}&{\bf 5}\\\ {\bf 4}&{\bf 3}&5&1&2\\\ 5&4&{\bf 2}&3&{\bf 1}\\\
3&5&1&2&4\\\ {\bf 4}&{\bf 3}&{\bf 2}&5&{\bf 1}\\\ \end{array}\right].$

Now suppose that $n\geq 7$ and $A$ is a latin square of order $n-1$ such that
the first four rows of $A$ are
$R_{1}=\left[\begin{array}[]{cccccccc}1&2&|&3&4&\cdots&n-2&n-1\\\
\end{array}\right]$ (corresponding to $v_{1}$),
$R_{2}=\left[\begin{array}[]{ccccccccc}2&1&|&4&5&\cdots&n-1&3\\\
\end{array}\right]$ (corresponding to $v_{2}$),
$R_{3}=\left[\begin{array}[]{ccccccccc}3&4&|&5&6&\cdots&(n-1)&1&2\\\
\end{array}\right]$ (corresponding to $v_{3}$) and
$R_{4}=\left[\begin{array}[]{ccccccccc}4&3&|&6&\cdots&(n-1)&1&2&5\\\
\end{array}\right]$ (corresponding to $v_{4}$). At first, we replace the
second row of $A$ by
$R^{\prime}_{2}=\left[\begin{array}[]{ccccccccc}1&2&|&4&5&\cdots&n-1&3\\\
\end{array}\right]$ to achieve a derangement $(n-1)$-representation matrix
$A^{\prime}$ of $G-v_{n}$ in which $v_{1}$ and $v_{2}$ are not adjacent. Now
the following matrix is a derangement $(n-1)$-representation matrix of $G$:

$L(K_{n}-(P_{3}\cup P_{2}))=\left[\begin{array}[]{c}A^{\prime}\\\
\hline\cr\begin{array}[]{cccccccc}3&4&|&6&\cdots&1&2&5\\\
\end{array}\end{array}\right],$

where the second part of the $n$-th row is the second part of $R_{4}$ and the
corresponding vertex to the last row ($v_{n}$) is not adjacent to $v_{3}$ and
$v_{4}$. Therefore, $drn(K_{n}-(P_{3}\cup P_{2}))=n-1$.  $\blacksquare$

In Theorems 3, 13, 16 and 15, we find the derangement representation number of
$K_{n}-P_{k}$ (for $2\leq k\leq 4$) and $K_{n}-C_{3}$. In the following
theorems, we obtain upper and lower bounds for the derangement representation
number of $K_{n}-P_{k}$ and $K_{n}-C_{3}$ for the other values of $n$ and $k$.

###### Theorem 18

Let $n,k\in\mathbb{N}$. If $n\geq k\geq 5$, then
$n-\bigg{\lceil}\dfrac{k}{2}\bigg{\rceil}+1\leq drn(K_{n}-P_{k})\leq n$.

###### Proof

Let $G=K_{n}-P_{k}$, $V(G)=\\{v_{i}|\ i\in[n]\\}$, $E(G^{c})=\\{v_{i}v_{i+1}|\
i\in[k-1]\\}$, $V_{0}=\\{v_{2i}|\ 1\leq i\leq\lfloor\frac{k}{2}\rfloor\\}$ and
$V_{1}=\\{v_{2i-1}|\ 1\leq i\leq\lceil\frac{k}{2}\rceil\\}$.
Case 1. $k=2t+1$: The subgraph of $G$ induced by $V(G)\setminus V_{0}$ is a
clique of order $n-t$. So
$drn(G)\geq\omega(G)=n-t=n-\bigg{\lceil}\dfrac{k}{2}\bigg{\rceil}+1$.
Case 2. $k=2t$: The subgraph of $G$ induced by $(V(G)\setminus
V_{0})\cup\\{v_{k}\\}$ is isomorphic to $K_{p}-K_{2}$ where $p=n-t+1$. So
$drn(G)\geq drn(K_{p}-K_{2})\geq
p=n-\bigg{\lceil}\dfrac{k}{2}\bigg{\rceil}+1$.
Now we prove that $K_{n}-P_{k}$ is derangement $n$-representable. Consider the
latin square $L=[l_{i,j}]_{n\times n}$ with $l_{i,j}=j-i+1$ when $j\geq i$ and
$l_{i,j}=n+1+j-i$ when $j<i$.

$L=\left[\begin{array}[]{ccccccc}1&2&3&4&\cdots&n-1&n\\\
n&1&2&3&\cdots&n-2&n-1\\\ n-1&n&1&2&\cdots&n-3&n-2\\\
n-2&n-1&n&1&\cdots&n-4&n-3\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 3&4&5&6&\cdots&1&2\\\
2&3&4&5&\cdots&n&1\\\ \end{array}\right].$

Let $M_{i,j}=\\{l_{i,j},l_{i+1,j+1},l_{i+1,j},l_{i+2,j+1}\\}$ for any
$i,j\in[n]$ (the indices being taken modulo $n$). We have
$l_{i,j}=l_{i+1,j+1}$ and $l_{i+1,j}=l_{i+2,j+1}$. If we replace together two
cells $l_{i+1,j+1}$ and $l_{i+1,j}$ in $L$, then the result matix is a
derangement representation matrix of $K_{n}-P_{2}$. We call this change a flip
change. Therefore, to achieve the derangement $n$-representation matrix of
$K_{n}-P_{k}$, it is enough to do the flip change on $M_{1,1}$, $M_{2,3}$,
$\ldots$, and $M_{k-2,2k-5}$ where the indices being taken modulo $n$. In
fact, the flip change on $M_{i,2i-1}$, remove the edge $v_{i}v_{i+1}$ from
$E(K_{n})$.  $\blacksquare$

###### Example 19

As explained in the proof of the Theorem 18, the following matrx is a
derangement representation matrix of $K_{8}-P_{6}$:

$L(K_{8}-P_{6})=\left[\begin{array}[]{cccccccc}{\bf 1}&2&3&4&5&6&7&8\\\ {\bf
1}&{\bf 8}&{\bf 2}&3&4&5&6&7\\\ 7&{\bf 8}&{\bf 2}&{\bf 1}&{\bf 3}&4&5&6\\\
6&7&8&{\bf 1}&{\bf 3}&{\bf 2}&{\bf 4}&5\\\ 5&6&7&8&1&{\bf 2}&{\bf 4}&{\bf
3}\\\ 4&5&6&7&8&1&2&{\bf 3}\\\ 3&4&5&6&7&8&1&2\\\ 2&3&4&5&6&7&8&1\\\
\end{array}\right].$

###### Theorem 20

Let $n,k\in\mathbb{N}$. If $n\geq k\geq 4$, then
$n-\bigg{\lfloor}\dfrac{k}{2}\bigg{\rfloor}\leq drn(K_{n}-C_{k})\leq n$.

###### Proof

Let $G=K_{n}-C_{k}$, $V(G)=\\{v_{i}|\ i\in[n]\\}$, $E(G^{c})=\\{v_{i}v_{i+1}|\
i\in[k-1]\\}\cup\\{v_{k}v_{1}\\}$, $V_{0}=\\{v_{2i}|\ 1\leq
i\leq\lfloor\frac{k}{2}\rfloor\\}$ and $V_{1}=\\{v_{2i-1}|\ 1\leq
i\leq\lceil\frac{k}{2}\rceil\\}$.
Case 1. $k=2t$: The subgraph of $G$ induced by $V(G)\setminus V_{0}$ is a
clique of order $n-t$. So
$drn(G)\geq\omega(G)=n-t=n-\bigg{\lfloor}\dfrac{k}{2}\bigg{\rfloor}$.
Case 2. $k=2t+1$: The subgraph of $G$ induced by $V(G)\setminus V_{0}$ is
isomorphic to $K_{p}-K_{2}$ where $p=n-t$. So $drn(G)\geq drn(K_{p}-K_{2})\geq
p=n-\bigg{\lfloor}\dfrac{k}{2}\bigg{\rfloor}$.
To prove the upper bound, we consider three cases:
Case 1. $n=k$: Similar to the proof of Theorem 18, to achieve the derangement
$n$-representation matrix of $K_{n}-P_{n}$, it is enough to do the flip change
on $M_{1,1}$, $M_{3,3}$, $\ldots$, and $M_{n-1,n-1}$. In fact, the flip change
on $M_{i,i}$, remove two edge $v_{i}v_{i+1},v_{i+1}v_{i+2}$ from $E(K_{n})$.
Case 2. $n>k=2t\geq 4$: Let $A$ and $B$ be latin squares of order $t$ and
$n-t$, with symbol sets $[t]$ and $[n]\setminus[t]$, respectively. Also the
$i$-th row of a matrix $X$ is denoted by $X_{i}$. Obviously,

$L=\left[\begin{array}[]{c}A_{1}\ B_{1}\\\ \vdots\ \ \ \vdots\\\ A_{t}\
B_{t}\\\ \end{array}\right]$

is a latin rectangle of order $t\times n$ and so by use of Hall’s Theorem, we
can extend $L$ to the following latin rectangle:

$L^{\prime}=\left[\begin{array}[]{c}A_{1}\ B_{1}\\\ \vdots\ \ \vdots\\\ A_{t}\
B_{t}\\\ C_{1}\\\ \vdots\\\ C_{n-2t}\\\ \end{array}\right]$

Now easily one can show that the following matrix is a derangement
$n$-representation matrix of $K_{n}-C_{k}$:

$L^{\prime\prime}=\left[\begin{array}[]{c}A_{1}\ B_{t}\\\ A_{1}\ B_{1}\\\
A_{2}\ B_{1}\\\ A_{2}\ B_{2}\\\ A_{3}\ B_{2}\\\ \vdots\ \ \ \vdots\\\ A_{t}\
B_{t-1}\\\ A_{t}\ B_{t}\\\ C_{1}\\\ \vdots\\\ C_{n-2t}\\\ \end{array}\right].$

Case 3. $n>k=2t-1\geq 5$: At first, similar to the previous case we define
$A$, $B$ of order $t\times t$ and $t\times(n-t)$, such that $A_{1}=[1\ 2\ 3\
\cdots\ t]$, $A_{t}=[2\ 3\ \cdots\ t\ 1]$, and $B_{1}=[t+1\ \cdots\ n]$.
Similarly, we define $L$ (of order $t\times n$) and then we change the symbols
$1\rightarrow 2\rightarrow t+1\rightarrow 1$ in the first row of $L=[l_{i,j}]$
such that $l_{1,1}=l_{t,1}=2$. Then by use of Hall’s Theorem, we can extend
$L$ to the row latin rectangle $L^{\prime}$ (of order $(n-t+1)\times n$) by
adding $n-2t+1$ rows $C_{1},\ldots,C_{n-2t+1}$ such that
$\\{c_{i,j}|i\in[n-2t+1]\\}\cap\\{l_{i,j}|i\in[t]\\}=\emptyset$ and
$c_{i,j}\neq c_{i^{\prime},j}\ (i\neq i^{\prime})$ for any $j\in[n]$. Finally,
to achieve a derangement $n$-representation matrix of $K_{n}-C_{k}$ we define
$L^{\prime\prime}$ as follows:

$L^{\prime\prime}=\left[\begin{array}[]{c}A_{1}\ B_{1}\\\ A_{1}\ B_{2}\\\
A_{2}\ B_{2}\\\ A_{2}\ B_{3}\\\ A_{3}\ B_{3}\\\ \vdots\ \ \ \vdots\\\ A_{t-1}\
B_{t-1}\\\ A_{t-1}\ B_{t}\\\ A_{t}\ B_{t}\\\ C_{1}\\\ \vdots\\\ C_{n-2t+1}\\\
\end{array}\right].$

$\blacksquare$

To prove the next theorem, we need an special type of latin squares.

###### Definition 21

A latin square is idempotent if every symbol appears on the main diagonal.

It was proved in [9] that there exists an idempotent latin square of order $n$
for any positive integer $n\neq 2$,

###### Theorem 22

$drn(C_{n})\leq\lceil\dfrac{n}{2}\rceil+1$ for any positive integer $n\geq 3$.

###### Proof

Let $V(C_{n})=\\{v_{1},v_{2},\ldots,v_{n}\\}$,
$E(C_{n})=\\{v_{1}v_{2},v_{2}v_{3},\ldots,v_{n}v_{1}\\}$. We consider two
cases:
Case 1. $n=2k$:
Suppose that $V_{1}=\\{v_{1},v_{3},\ldots,v_{2k-1}\\}$, and
$V_{0}=\\{v_{2},v_{4},\ldots,v_{2k}\\}$. There is an idempotent latin square
$M=[m_{i,j}]$ of order $k$. Without loss of generality, we assume that
$m_{i,i}=i$. Also matrices $N=[n_{i,j}]_{k\times k}$, $L_{1}$ and $L_{0}$ are
defined as follows.

$N=\left[\begin{array}[]{cccccc}2&k+1&3&\cdots&k-1&k\\\ \\\
1&3&k+1&\cdots&k-1&k\\\ \\\ 1&2&4&\cdots&k-1&k\\\ \\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ \\\ 1&2&3&\cdots&k&k+1\\\ \\\
k+1&2&3&\cdots&k-1&1\\\
\end{array}\right],L_{1}=\left[\begin{array}[]{c|c}\begin{array}[]{c}k+1\\\
\vdots\\\ k+1\\\ \end{array}&M\\\ \end{array}\right],\
L_{0}=\left[\begin{array}[]{c|c}\begin{array}[]{c}1\\\ 2\\\ \vdots\\\ k\\\
\end{array}&N\\\ \end{array}\right].$

Now if we assign $L_{1}$ and $L_{0}$ to the vertices of $V_{1}$ and $V_{0}$,
respectively then $L=\left[\begin{array}[]{c}L_{1}\\\ L_{0}\\\
\end{array}\right]$ is a derangement $(k+1)$-representation of $C_{n}$.
Case 2. $n=2k+1$:
Suppose that $V_{1}=\\{v_{3},v_{5},\ldots,v_{2k-1}\\}$,
$V_{0}=\\{v_{2},v_{4},\ldots,v_{2k}\\}$. We know there is an idempotent latin
square $M=[m_{ij}]$ of order $k$. Without loss of generality, we assume that
$m_{i,i}=i$. Also matrices $N=[n_{i,j}]_{(k-1)\times k}$, $L_{1}$, $L_{0}$,
$W_{1}$ (corresponding to vertex $v_{1}$), and $W_{0}$ (corresponding to
vertex $v_{2k+1}$) are defined as follows.

$N=\left[\begin{array}[]{cccccc}2&k+1&3&\cdots&k-1&k\\\ \\\
1&3&k+1&\cdots&k-1&k\\\ \\\ 1&2&4&\cdots&k-1&k\\\ \\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ \\\ 1&2&3&\cdots&k&k+1\\\
\end{array}\right],$
$L_{0}=\left[\begin{array}[]{c|c}\begin{array}[]{cc}k+2&k+1\\\ \vdots\\\
k+2&k+1\\\ \end{array}&M\\\
\end{array}\right],L_{1}=\left[\begin{array}[]{c|c}\begin{array}[]{cc}1&k+2\\\
2&k+2\\\ \vdots\\\ k-1&k+2\\\ \end{array}&N\\\ \end{array}\right],$
$W_{0}=[k+1,\,1\,|\,k+2\,,2\,,3\,,\cdots,k],$
$W_{1}=[m_{k1},\,k+2\,|\,k+1\,,m_{12}\,,m_{23}\,,\cdots,m_{k-1k}].$

Now if we assign $L_{1}$ and $L_{0}$ to the vertices of $V_{1}$ and $V_{0}$,
respectively then $L=\left[\begin{array}[]{c}L_{1}\\\ W_{1}\\\ L_{0}\\\
W_{0}\\\ \end{array}\right]$ is a derangement $(k+2)$-representation of
$C_{n}$. $\blacksquare$

###### Example 23

As explained in the proof of the Theorem 22, the following matrices are the
derangement representations matrices of $C_{10}$ and $C_{11}$:

$L(C_{10})=\left[\begin{array}[]{c|ccccc}6&1&4&2&5&3\\\ 6&4&2&5&3&1\\\
6&2&5&3&1&4\\\ 6&5&3&1&4&2\\\ 6&3&1&4&2&5\\\ \hline\cr 1&2&6&3&4&5\\\
2&1&3&6&4&5\\\ 3&1&2&4&6&5\\\ 4&1&2&3&5&6\\\
5&6&2&3&4&1\end{array}\right],L(C_{11})=\left[\begin{array}[]{cc|ccccc}7&6&1&4&2&5&3\\\
7&6&4&2&5&3&1\\\ 7&6&2&5&3&1&4\\\ 7&6&5&3&1&4&2\\\ 7&6&3&1&4&2&5\\\ \hline\cr
6&1&7&2&3&4&5\\\ \hline\cr 1&7&2&6&3&4&5\\\ 2&7&1&3&6&4&5\\\ 3&7&1&2&4&6&5\\\
4&7&1&2&3&5&6\\\ 3&7&6&4&5&1&2\\\ \end{array}\right]$

###### Theorem 24

Let $G$ be a path graph of order greater than $4$, then
$drn(P_{n})\leq\lceil\dfrac{n}{2}\rceil+1.$

###### Proof

Let
$V(G)=\\{v_{1},v_{2},\ldots,v_{2k}\\}$,$E(G)=\\{v_{1}v_{2},v_{2}v_{3},\ldots,v_{n-1}v_{n}\\}$.
We consider two cases:
Case 1. $n=2k$: Suppose that $V_{1}=\\{v_{1},v_{3},\ldots,v_{2k-1}\\}$, and
$V_{0}=\\{v_{2},v_{4},\ldots,v_{2k}\\}$. There is an idempotent latin square
$M=[m_{i,j}]$ of order $k$. Without loss of generality, we assume that
$m_{i,i}=i$. Also matrices $N=[n_{i,j}]_{k\times k}$, $L_{1}$ and $L_{0}$ are
defined as follows.

$N=\left[\begin{array}[]{cccccc}2&k+1&3&\cdots&k-1&k\\\ \\\
1&3&k+1&\cdots&k-1&k\\\ \\\ 1&2&4&\cdots&k-1&k\\\ \\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ \\\ 1&2&3&\cdots&k&k+1\\\ \\\
1&2&3&\cdots&k-1&k+1\\\
\end{array}\right],L_{1}=\left[\begin{array}[]{c|c}\begin{array}[]{c}k+1\\\
\vdots\\\ k+1\\\ \end{array}&M\\\ \end{array}\right],\
L_{0}=\left[\begin{array}[]{c|c}\begin{array}[]{c}1\\\ 2\\\ \vdots\\\ k\\\
\end{array}&N\\\ \end{array}\right].$

Now if we assign $L_{1}$ and $L_{0}$ to the vertices of $V_{1}$ and $V_{0}$,
respectively then $L=\left[\begin{array}[]{c}L_{1}\\\ L_{0}\\\
\end{array}\right]$ is a derangement $(k+1)$-representation of $P_{n}$.
Case 2. $n=2k-1$: $P_{2k-1}$ is an induced subgraph of $P_{2k}$. So
$drn(P_{2k-1})\leq
drn(P_{2k})\leq\lceil\frac{2k}{2}\rceil+1=k+1=\lceil\frac{n}{2}\rceil+1$.
$\blacksquare$

###### Example 25

As explained in the proof of the Theorem 24, the following matrices are the
derangement representations matrices of $C_{10}$ and $C_{11}$:

$L(P_{9})=\left[\begin{array}[]{c|ccccc}6&1&4&2&5&3\\\ 6&4&2&5&3&1\\\
6&2&5&3&1&4\\\ 6&5&3&1&4&2\\\ 6&3&1&4&2&5\\\ \hline\cr 1&2&6&3&4&5\\\
2&1&3&6&4&5\\\ 3&1&2&4&6&5\\\
4&1&2&3&5&6\end{array}\right],L(P_{10})=\left[\begin{array}[]{c|ccccc}6&1&4&2&5&3\\\
6&4&2&5&3&1\\\ 6&2&5&3&1&4\\\ 6&5&3&1&4&2\\\ 6&3&1&4&2&5\\\ \hline\cr
1&2&6&3&4&5\\\ 2&1&3&6&4&5\\\ 3&1&2&4&6&5\\\ 4&1&2&3&5&6\\\
5&1&2&3&4&6\end{array}\right].$

###### Theorem 26

Let $n,r\in\mathbb{N}$ and $1<r<n$. Then $drn(K_{n}-K_{r})\leq\max\\{n,2r\\}$.

###### Proof

Suppose that $V(K_{n}-K_{r})=\\{v_{1},\ldots,v_{n}\\}$. At first, suppose that
$n\geq 2r$. We give a derangement $n$-representation matrix $L$ of $G$. Let
$A=[a_{i,j}]_{r\times r}$ and $B=[b_{i,j}]_{(n-r)\times(n-r)}$ be two latin
squares with disjoint sets of symbols $[r]$ and $\\{r+1,\ldots,n\\}$,
respectively. Let $B_{1}$ be the matrix of order $r\times(n-r)$ that contains
the first $r$ rows of $B$. Now we define the first $r$ rows of $L_{1}$ as
follows: $L_{1}=\big{[}\begin{array}[]{c|c}A&B_{1}\end{array}\big{]}$. Then we
extend this latin rectangle to a complete latin square $L_{2}$ of order $n$ by
use of Hall’s Theorem. Finally, we replace all rows of $A$ with the first row
of $A$ in $L_{2}$ to achieve $L=[l_{i,j}]_{n\times n}$. Now
$l_{i,j}=l_{i^{\prime},j}$ for some $j\in[n]$ if and only if
$i,i^{\prime}\in[r]$ and in other cases, we have $l_{i,j}\neq
l_{i^{\prime},j}$ for all $j\in[n]$. Therefore, $L$ is a derangement
$n$-representation matrix of $G$.
Now suppose that $n<2r$. In this case, $K_{n}-K_{r}$ is an induced subgraph of
$K_{2r}-K_{r}$. Therefore $drn(K_{n}-K_{r})\leq drn(K_{2r}-K_{r})\leq 2r$ by
Lemma 6.  $\blacksquare$

##  4 Computational results using Sage

We can compute the derangement representation number of graphs of small
orders. For example, the following simple code in Sage tests the derangement
$4$-representability of the fork graph (See the Figure 2):

$(1,2,4,3)$$(3,1,2,4)$$(2,4,3,1)$$(1,4,2,3)$$(1,2,3,4)$ Figure 2: A
derangement $4$-representation of fork graph

In Table 1, we show the derangement representation number of cycle $C_{n}$ for
any $n\in\\{3,\ldots,20\\}$:

$n$ | $drn(C_{n})$
---|---
3 | 3
4,…, 6 | 4
7,…, 12 | 5
13,…, 20 | 6

Table 1: $drn(C_{n})$ for $3\leq n\leq 20$

In Table 2, we show the derangement representation number of path $P_{n}$ for
any $2\leq n\leq 29$:

$n$ | $drn(P_{n})$
---|---
2 | 2
3,…, 8 | 4
9,…, 14 | 5
15,…, 22 | 6
23,…, 29 | 7

Table 2: $drn(P_{n})$ for $2\leq n\leq 29$

In Table 3, we find the derangement representation number of complete
bipartite graph $K_{r,s}$ when $r,s\in[10]$:

$r$ | $s$ | $drn(K_{r,s})$
---|---|---
1 | 1 | 2
1,2 | 2,3 | 4
3 | 3 | 5
1,…,4 | 4 | 5
1,…,5 | 5 | 5
1,…,6 | 6 | 5
1,…,4 | 7 | 5
5,…,7 | 7 | 6
1,…,4 | 8 | 5
5,…,8 | 8 | 6
1,2 | 9 | 5
3,…,6 | 9 | 6
7,…,9 | 9 | 7
1 | 10 | 5
2,…,6 | 10 | 6
7,…,10 | 10 | 7

Table 3: $drn(K_{r,s})$ for $r,s\in[10]$

Suppose that $Cay^{not}(i)$ represents the number of graphs of order $i$ which
are not induced subgraphs of $Cay(S_{i},D_{i})$. For some small values of $i$,
we compute $Cay^{not}(i)$ using SAGE, with the following code. The results for
$i\in[7]$ have been shown in Table 4.

$i$ | $Cay^{not}(i)$
---|---
1 | 0
2 | 1
3 | 2
4,…,7 | 0

Table 4: $Cay^{not}(i)$ for $i\in[7]$

Using the code ”$G$.subgraph$\\_$search($H$, induced=True).show()” in Sage, we
can identify an induced subgraph of $G$ that is isomorphic to $H$. For
instance, in the following code we identify the graphs of order $6$ with
derangement representation number $6$. In fact, $K_{6}$, $K_{6}-K_{2}$,
$K_{6}-2K_{2}$ and $K_{6}-K_{3}$ are the only graphs of order six with
derangement representation number six: (See Figure 3).

$(2,1,4,3,6,5)$$(1,2,6,4,5,3)$$(5,6,1,2,3,4)$$(1,2,3,5,4,6)$$(3,4,5,6,1,2)$$(1,2,3,4,5,6)$

$(2,6,4,1,3,5)$$(4,3,6,5,2,1)$$(3,4,5,6,1,2)$$(2,1,4,3,6,5)$$(1,2,3,4,5,6)$$(3,5,1,6,4,2)$

$(5,6,1,2,3,4)$$(3,4,5,6,1,2)$$(2,5,4,1,6,3)$$(1,2,3,4,5,6)$$(4,3,6,5,2,1)$$(2,1,4,3,6,5)$

Figure 3: Derangement $6$-representations of $K_{6}-K_{3}$, $K_{6}-2K_{2}$ and
$K_{6}-K_{2}$

##  5 Further questions

As outlined in Sections 3 and 4, especially in Table 4, we see that the
derangement representation number of any graph which is reviewed in this paper
is less than its order, except a finite number of graphs
($\mathcal{F}=\\{\overline{K_{2}},\overline{K_{3}},P_{3}\\}$). So we propose
the following conjecture:

###### Conjecture 27

$drn(G)\leq p(G)$ for any finite graph $G$ except the graphs of the family
$\mathcal{F}$.

We can easily show that the complete graph $K_{n}$ is derangement
$k$-representable for all $k\geq n$. In fact, any latin rectangle of order
$n\times k$ is a derangement representation matrix of $K_{n}$. There is a
similar result for the graph $\overline{K_{n}}$.

###### Problem 28

Characterise all graphs $G$ which are derangement $k$-representable for any
positive integer $k\geq drn(G)$.

## References

  * [1] L. Babai and V.T. Sos, Sidon sets in groups and induced subgraphs of Cayley graphs, European Journal of Combinatorics 6 (1985), no.2, 101–114.
  * [2] L. W. Beineke, and R.J. Wilson, Topics in algebraic graph theory, Cambridge University Press, (2004).
  * [3] J. A. Bondy and U. S. R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, (2008).
  * [4] A. Cayley, On the theory of groups, as depending on the symbolic equation $\theta^{n}=1$, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 7 (1854), no.42, 40–47.
  * [5] M. Deza and P. Frankl, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A 22 (1977), no.3, 352–360.
  * [6] P. Erdos and A. B. Evans,Representations of graphs and orthogonal latin square graphs, Journal of Graph Theory 13 (1989), no.5, 593–595.
  * [7] P. Erdos, A. W. Goodman, and L. Posa, The representation of a graph by set intersections, Canadian Journal of Mathematics 18 (1966), no.1, 106–112.
  * [8] C. C. Lindner, E. Mendelsohn, N. S. Mendelsohn, and B. Wolk, Orthogonal latin square graphs, Journal of Graph Theory 3 (1979), no.4, 325–338.
  * [9] C. C. Lindner and C. A. Rodger, Design theory. Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, (2009).
  * [10] SageMath, the Sage Mathematics Software System (Version 9.4), The Sage Developers, (2021), https://www.sagemath.org.
  * [11] W. T. Trotter Jr, and F. Harary, On double and multiple interval graphs. Journal of Graph Theory 3 (1979), no.3, 205–211.