% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P23}{20(1)}{2013}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title

\title{\bf The Distinguishing Chromatic Number\\ of Kneser Graphs}
\author{Zhongyuan Che\\
\small Dept. of Mathematics\\[-0.8ex]
\small Penn State University, Beaver Campus\\[-0.8ex] 
\small  Monaca, PA, U.S.A\\
\small\tt zxc10@psu.edu\\
\and Karen L. Collins\\
\small Dept. of Mathematics and Computer Science\\[-0.8ex] 
\small Wesleyan University\\[-0.8ex]
\small Middletown, CT,  U.S.A.\\
\small\tt kcollins@wesleyan.edu
}

\date{\dateline{Aug 10, 2009}{Jan 21, 2013}{Jan 29, 2013}\\
\small Mathematics Subject Classifications: 05C15, 05C25}

\begin{document}

\maketitle
\begin{abstract}
A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ of the vertex
set of a graph $G$ is said to be proper $d$-distinguishing if it is
a proper coloring of $G$ and any nontrivial automorphism of $G$ maps
at least one vertex to a vertex with a different label.  The
distinguishing chromatic number of $G$, denoted by $\chi_D(G)$, is
the minimum $d$ such that $G$ has a proper $d$-distinguishing
labeling. Let $\chi(G)$ be the chromatic number of $G$ and $D(G)$ be
the distinguishing number of $G$.  Clearly, 
$\chi_D(G) \ge \chi(G)$ and
$\chi_D(G) \ge D(G)$. 
Collins, Hovey and Trenk \cite{CHT09} have given a tight
upper bound on $\chi_D(G)-\chi(G)$ in terms of the order of the
automorphism group of $G$, improved when the automorphism group of
$G$ is a finite abelian group. 
The Kneser graph $K(n,r)$ is a graph whose vertices are
the $r$-subsets of an $n$ element set, and two vertices of $K(n,r)$ are adjacent if
their corresponding two $r$-subsets are disjoint. 
In this paper, we provide a class of
graphs $G$, namely Kneser graphs $K(n,r)$, 
whose automorphism group is the symmetric group, $S_n$,
such that $\chi_D(G) - \chi(G) \le 1$.
In particular, we prove that
$\chi_D(K(n,2))=\chi(K(n,2))+1$ for $n\ge 5$. In addition, we show
that $\chi_D(K(n,r))=\chi(K(n,r))$ for $n \ge 2r+1$ and $r\ge 3$.

% keywords are optional
%\bigskip\noindent \textbf{Keywords:} 
%distinguishing number, proper coloring, distinguishing chromatic number, Kneser graphs
\end{abstract}

\section{Introduction}

In 1996, Albertson and Collins \cite{AC96} invented the
distinguishing number of a graph. It is the smallest number of
colors with which the vertices of a graph can be labeled so that
every non-trivial automorphism of the graph moves a label. Since
then this concept has been studied extensively, including the recent
work on the distinguishing number of planar graphs by Arvind, Cheng
and Devanur \cite{ACD08}; augmented cubes and hypercube powers by
Chan \cite{Ch08}; Cartesian products of complete graphs by Imrich,
Jerebic and Klav\v{z}ar \cite{IJK08}; infinite graphs
by Imrich, Klav\v{z}ar and Trofimov \cite{IKT07}; and
locally finite trees by Watkins and Zhou \cite{WaZh07}. The concept
has been extended beyond graphs by Tymoczko \cite{T04} and
Klav\v{z}ar, Wong and Zhu \cite{KWZ06}.

In 2006, Collins and Trenk \cite{CT06} created the distinguishing
chromatic number of a graph. It is the smallest number of colors
with which the vertices of a graph can be labeled so that no two
adjacent vertices have the same color and the only automorphism of
the graph that preserves color classes is the trivial automorphism.
Their paper proved versions of Brooks' Theorem for both the
distinguishing number and the distinguishing chromatic number.
Collins, Hovey and Trenk \cite{CHT09} proved further bounds on the
distinguishing chromatic number using the automorphism group of a
graph, while Choi, Hartke and Kaul \cite{CHK10} provided bounds on the
distinguishing chromatic number of Cartesian products of graphs.
Weigand and Jacobson \cite{WJ08} gave the distinguishing and
distinguishing chromatic numbers of generalized Petersen graphs.


Let $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ be a labeling of the
vertex set of a graph $G$. Then the labeling $f$ is called a \emph{
proper $d$-coloring} if any two adjacent vertices have different
labels. The chromatic number of $G$, denoted by $\chi(G)$, is the
minimum $d$ such that $G$ has a proper $d$-coloring. Albertson and
Collins introduced the definition of a distinguishing labeling and
the distinguishing number of a graph in \cite{AC96}, inspired from
Frank Rubin's key problem \cite{R79}: Given a ring of keys with
similar  shape, how many colors are needed to distinguish them? A
labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ is called \emph{
$d$-distinguishing} if the only automorphism of $G$ which preserves all
vertex labels is the trivial automorphism, that is, any nontrivial
automorphism of $G$ must map at least one vertex to a vertex with a
different label. The \emph{ distinguishing number} of $G$ is the
minimum $d$ such that $G$ has a $d$-distinguishing labeling, and
denoted by $D(G)$.

In the definition of distinguishing labeling of a graph, there is no
need to require that two adjacent vertices receive different colors.
To study the problem of how to store reactive chemicals so that the
chemicals are uniquely identified by their storage bins, and also
arranged in a way that prevents chemical reactions, Collins and
Trenk introduced the definition of a proper distinguishing labeling,
and the distinguishing chromatic number of a graph.

\begin{definition}\rm\cite{CT06}
A labeling $f: V(G) \rightarrow \{1, 2, \ldots, d\}$ of the vertex
set of a graph $G$ is said to be  \emph{proper $d$-distinguishing} if
it is both a proper $d$-coloring and a $d$-distinguishing labeling
of $G$. The \emph{distinguishing chromatic number} of $G$, denoted by
$\chi_D(G)$, is the minimum $d$ such that $G$ has a proper
$d$-distinguishing labeling.
\end{definition}


From the definition, $\chi_D(G) \ge \chi(G)$ and $\chi_D(G) \ge D(G)$.  
It is easy to see that $\chi_D(G)\le \chi(G)\cdot D(G)$, by assigning ordered pairs
to the vertices of $G$, where the first component represents proper coloring, 
and second component represents distinguishing labeling. 
It is tempting to believe, however, that in many cases, $\chi_D(G)$ should
only be a little bit bigger than $\chi(G)$, or be bounded by the
addition of a constant to the chromatic number.  Let $G^t$ be the
Cartesian product of $t$ copies of $G$.  Choi, Hartke and Kaul
\cite{CHK10} have shown that for $t\ge t_{G}$, $\chi_D(G^t)\le
\chi(G^t)+1=\chi(G)+1$, where $t_{G}$ is a constant that depends on
$G$. In particular, for $t\ge 5$, $\chi_D(K_{n}^{t})\le n+1$. On the
other hand, let $G\circ H$ be the lexicographic product of $G$ and
$H$, see \cite{IK00}. Let $G_1=C_{2k}\circ \overline{K_m}$ for $k\ge
4$. Tang \cite{T07} showed that \[\chi_D(G_1) = \chi(G_1) \cdot
D(G_1) -1.\] 
In addition, let $G_2=C_{2k+1}\circ \overline{K_m}$ for $k\ge 3$, 
\[\chi_D(G_2) = \chi(G_2) \cdot D (G_2) -2- D(G_2) + \lceil (D(G_2)-1)/k\rceil.\]
From these latter examples, we see that for some classes of graphs,
the distinguishing chromatic number may be bounded close to its
maximum value.  However, the chromatic number of
$C_{2k}\circ\overline{K_m}$ is 2 and the chromatic number of
$C_{2k+1}\circ\overline{K_m}$ is 3, so these are very special cases.

Recently, Collins, Hovey and Trenk \cite{CHT09} have provided  two
upper bounds on $\chi_D(G) - \chi(G)$ based on the automorphism
group of $G$, and each of them is tight:

(i) If $aut(G)$ is finite of order $p_1^{i_1}p_2^{i_2} \cdots
p_k^{i_k}$ where the $p_i$'s are distinct primes, then
$\chi_D(G)-\chi(G) \le i_1+i_2+\cdots +i_k$;

(ii) If $aut(G)$ is a finite abelian group written as
$aut(G)=Z_{p_1^{i_1}} \times Z_{p_2^{i_2}} \times \cdots \times
Z_{p_k^{i_k}}$ where the $p_i$'s are distinct primes, then
$\chi_D(G) -\chi(G) \le k$.

We are interested in bounds on the distinguishing chromatic number,
and in the construction of infinite families of graphs that achieve
those bounds. We will provide a class of graphs $G$ whose
automorphism group is the symmetric group $S_n$ and
$\chi_D(G)-\chi(G) \le 1$. Let $n$ and $r$ be positive integers with
$1 \le r \le \frac{n}{2}$. Let $[n]$ denote the set of integers from $1$ to $n$.
The \emph{Kneser graph} $K(n,r)$ is a graph whose vertices are
the $r$-subsets of $[n]$. A vertex corresponding to the $r$-subset 
$\{i_{1}, i_{2}, \ldots, i_{r}\}$ is denoted by $v_{\{i_{1}, i_{2}, \ldots, i_{r}\}}$ where $i_{1}, i_{2}, \ldots, i_{r}$ 
are integers from $[n]$. Two vertices  $v_{\{i_{1}, i_{2}, \ldots, i_{r}\}}$ and  $v_{\{j_{1}, j_{2}, \ldots, j_{r}\}}$ 
of $K(n,r)$ are adjacent if
their corresponding two $r$-subsets $\{i_{1}, i_{2}, \ldots, i_{r}\}$ and $\{j_{1}, j_{2}, \ldots, j_{r}\}$ are disjoint. 
When $r=1$, the Kneser  graph $K(n,1)$ is the complete graph $K_n$. When
$n=2r$, $K(2r,r)$ is a set of disjoint edges. When $n=2r+1$, the
Kneser graph $K(2r+1,r)$ is also called the odd graph.
It is known that the chromatic number of $K(n,r)$ is $n-2r+2$, 
and the automorphism group of $K(n,r)$ is $S_n$, see \cite{HT96}, 
and that the distinguishing number of $K(n,r)$ is $2$ for $n\ge 6$ and $r \ge
2$, see \cite{AB07}. 

In this paper, we show that
$\chi_D(K(n,r))-\chi(K(n,r))\le 1$ for all $n \ge 2r+1$. In
particular, we show that $\chi_D(K(n,2))-\chi(K(n,2))=1$ for $n \ge
5$, and that $\chi_D(K(n,r))=\chi(K(n,r))$ for $n \ge 2r+1$ and
$r\ge 3$. This answers a question raised by Weigand and Jacobson
\cite{WJ08}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The distinguishing chromatic number of $K(n,2)$}

In this section, we prove that the distinguishing chromatic number
of $K(n,2)$ equals $n-1$ (where $n \ge 5$), which is its chromatic number $n-2$ plus $1$. 
We first introduce some basic definitions and notations.

\begin{definition} \rm \label{D:SetPattern}
Let $S$ be an independent set of $K(n,r)$ with at least two vertices. 
Then every pair of vertices in $S$ have nonempty intersection. 
If the intersection of all vertices in $S$ is $\{i\}$, a single element set containing the
integer $i$, then we call $S$ a \emph{$1$-pattern} with the
intersection $\{i\}$. On the other hand, if the intersection of all
vertices in $S$ is an empty set, then we call $S$ a \emph{$0$-pattern}.
\end{definition}

It is well-known \cite{HT96} that any maximum independent set of
$K(n,r)$ (where $n \ge 2r+1$) is a $1$-pattern with size $\binom{n-1}{r-1}$. 
We use $M_{\{i\}}$ to represent the maximum independent set of $K(n,r)$
such that the intersection of all its vertices is $\{i\}$. When
$r=2$, any independent set of $K(n,2)$ with two or more vertices is
either a $1$-pattern or a $0$-pattern. Moreover, any $0$-pattern
independent set of $K(n,2)$ is a set of three vertices with the form $\{v_{\{i,j\}},
v_{\{i,k\}}, v_{\{j,k\}} \}$ where $i,j,k$ are three pairwise different
integers from $[n]$.

\begin{lemma}\rm \label{L:K(n,2)1}
For any proper $(n-2)$-coloring of $K(n,2)$ where $n \ge 5$, each
color class has size at least $2$.
\end{lemma}
\begin{proof} Let $\phi$ be a proper $(n-2)$-coloring of $K(n,2)$ with color
classes  $C_{i}$ for $1 \le i \le n-2$.  Suppose that $\phi$ has one color
class of size one, say $C_{n-2}=\{v_{\{n-1,n\}}\}$. Then no color class of $\phi$ is a
$1$-pattern with the intersection $\{n-1\}$ or $\{n\}$. Otherwise,
we can add the vertex $v_{\{n-1, n\}}$ into such a color class, and so
$\chi(K(n,2)) \le n-3$. This is a contradiction.  Therefore, we can assume that
any $1$-pattern color class with the intersection $\{i\}$ satisfies $1 \le i \le n-2$.

Let $S=\{v_{\{i,n-1\}} \mid 1 \le i \le n-2\} \cup  \{v_{\{i,n\}} \mid 1 \le i \le n-2\} $.
Then at most two vertices from
$S$ can be contained in the same color class of $\phi$: either
$v_{\{i,n-1\}}, v_{\{i,n\}}$, or $v_{\{i,n-1\}}, v_{\{j,n-1\}}$, or $v_{\{i,n\}}, v_{\{j,n\}}$ for some 
$1 \le i \neq j \le n-2$. It follows that each of $n-2$ color classes of $\phi$ contains
some vertices of $S$. This is impossible since $S \subseteq K(n,2) \setminus C_{n-2}$. 
Therefore, $|C_i| > 1$ for $1 \le i \le n-2$. 
\end{proof}

\begin{lemma}\rm\label{L:K(n,2)}
For any proper $(n-2)$-coloring of $K(n,2)$ where $n \ge 5$, there is exactly one color
class that is a $0$-pattern while all other color classes are $1$-patterns.
\end{lemma}
\begin{proof} Let $\phi$ be a proper $(n-2)$-coloring of $K(n,2)$ with color classes 
$C_{i}$ for $1 \le i \le n-2$. By Lemma \ref{L:K(n,2)1},  $|C_{i}| \ge 2$ for each $1 \le i \le n-2$.
So $C_{i}$ is either a $0$-pattern or $1$-pattern. If all color classes of $\phi$ are $0$-patterns, 
then $|V(K(n,2))|=|\cup_{1 \le i \le n-2} C_{i}| =3 (n-2)$. 
This is not possible since $|V(K(n,2))|={n \choose 2} > 3(n-2)$ for $n \ge 5$.
Hence, $\phi$ has at least one color class that is a $1$-pattern.
If all color classes of $\phi$ are $1$-patterns, then
without loss of generality, we can assume that $C_i \subseteq M_{\{i\}}$ for
$1 \le i \le n-2$. It follows that vertex $v_{\{n-1,n\}}$ is not
contained in any color class of $\phi$. This is a contradiction. 
So $\phi$ has at most $n-3$ color classes that are $1$-patterns.

Assume that $C_{1}, C_{2}, \ldots, C_{k}$ are $1$-patterns of $\phi$. Then $1 \le k \le n-3$.   
Without loss of generality,  we can assume that $C_{i} \subseteq M_{\{i\}}$ for $1 \le i \le k$.
Note that $|M_{\{i\}}| = n-1$, $|M_{\{i_{1}\}} \cap M_{\{i_{2}\}}| = 1$ and 
$|M_{\{i_1\}} \cap M_{\{i_2\}}\cap M_{\{i_3\}}| = 0$ for distinct $i_1,i_2, i_3$.  
Hence, by the principle of inclusion-exclusion:
\begin{eqnarray*}
|\cup_{i=1}^{k} C_{i}| \le  |\cup_{1\le i\le k} {M_{\{i\}}}| 
&=& \sum\limits_{i=1}^{k} |M_{\{i\}}| - \sum\limits_{1 \le i_{1}, i_{2} \le k} |M_{\{i_{1}\}} \cap M_{\{i_{2}\}}| \\
&=&k(n-1) -{k \choose 2} \\
&=&(n-1)+(n-2)+\cdots +(n-k).
\end{eqnarray*}
Now each $0$-pattern color class has size 3, and these are  $C_{k+1}, C_{k+2}, $ $ \ldots, C_{n-2}$.  Thus
\[|\cup_{i=k+1}^{n-2} C_{i}|=3(n-2-k). \]
The set of all vertices in $K(n,2)$ is equal to the union of all color classes, hence 
\begin{eqnarray*} 
{n \choose 2} &=& |\cup_{i=1}^{k} C_{i}|+|\cup_{i=k+1}^{n-2} C_{i}|\\
&\le& (n-1)+(n-2)+\cdots +(n-k)+3(n-k-2).
\end{eqnarray*}
Note that \[{n \choose 2} = (n-1)+(n-2)+\cdots +(n-k)+(n-k-1)+\cdots + 3+2+1.\]
Hence, $3(n-k-2) \ge  (n-k-1)+\cdots +3+2+1$, which implies that  $k \ge n-4$,
and $\phi$ has at least $n-4$ color classes 
that are $1$-patterns and so at most two color classes that are $0$-patterns. 
So $C_{i}$'s ($1 \le i \le n-4$)  are $1$-patterns of $\phi$ which have intersections $\{1\}, \{2\}, \ldots, \{n-4\}$ respectively.
Consider vertices $v_{\{n-3,n-2\}}$, $v_{\{n-3,n-1\}}$, $v_{\{n-3,n\}}$, $v_{\{n-2,n-1\}}$,  
$ v_{\{n-2,n\}}$, $v_{\{n-1,n\}}$. None is contained in any of the 1-pattern color classes $C_i$ for $1\leq i\leq n-4$, 
and the subgraph induced by these vertices  is isomorphic to $K(4,2)$, a disjoint union of three edges.  
It is easy to check that any proper $2$-coloring of $K(4,2)$ has a $0$-pattern color class and a $1$-pattern color class, 
each of size $3$.  It follows that exactly one of $C_{n-3}$ and $C_{n-2}$ is a $0$-pattern. 
\end{proof}

%\begin{remark} \rm
\noindent{\it Remark.} \
Lemma \ref{L:K(n,2)} is not true for Kneser graphs $K(n,r)$ when $r
\ge 3$. For example, the following table provides a proper
$3$-coloring of $K(7,3)$ where each color class is a $0$-pattern. In
the table, we use $ijk$ to represent the vertex $v_{\{i,j,k\}}$
briefly.
%\end{remark}

\begin{center} \small 
    \begin{tabular}{ |ccl|}
    \hline
    $C_1$  & = & \{123, 124, 125, 126, 127, 134, 135, 136, 137, 234, 235, 236, 237\} \\
    \hline
    $C_2$  & = & \{145, 146, 147, 245, 246, 247, 345, 346, 347, 567\} \\
    \hline
    $C_3$  & = & \{156, 157, 167, 256, 257, 267, 356, 357, 367, 456, 457, 467\} \\
    \hline
 \end{tabular}
\end{center}
%\qed\\
\normalsize

\medskip

\begin{theorem}\rm\label{T:K(n,2)}
Let $n \ge 5$. Then $\chi_D(K(n,2))=\chi(K(n,2))+1=n-1$.
\end{theorem}
\begin{proof} We first show that $\chi_D(K(n,2))>n-2$. Let $\phi$ be a proper
$(n-2)$-coloring of $K(n,2)$ with color classes $C_i$ for $1 \le i
\le n-2$. By Lemma \ref{L:K(n,2)}, we can assume that $C_i \subseteq
M_{\{i\}}$ is a $1$-pattern where $1 \le i \le n-3$, and
$C_{n-2}=\{v_{\{n-2, n-1\}}, v_{\{n-2, n\}}, v_{\{n-1, n\}} \}$ is a
$0$-pattern.  Since the automorphism group of $K(n,2)$ is $S_{n}$ by \cite{HT96}, we
can consider an automorphism of $K(n,2)$ as a permutation of $[n]$.  
Let $\sigma$ be an automorphism of $K(n,2)$ which
fixes each $i$ for $1 \le i \le n-3$ and permutes $\{n-2, n-1, n\}$.
Then $\sigma$ is nontrivial and
preserves all the color classes of $\phi$.

We now show that $\chi_D(K(n,2)) \le n-1$. Define a proper
$(n-1)$-coloring $\psi$ of $K(n,2)$ with color classes $D_{i}$ for $1 \le i \le n-1$:
\begin{eqnarray*}\small
D_{1}& = & M_{\{1\}} \setminus \{v_{\{1,n\}}\},\\
D_{i} & =& M_{\{i\}}\setminus \cup_{j < i} M_{\{j\}}, \mbox{  for }  2 \le i \le n-2, \\
D_{n-1}  & = & \{v_{\{n-1, n\}}, v_{\{1, n\}}\}.
\end{eqnarray*} \normalsize
We claim that $\psi$ is also distinguishing. 
Note that for any $1$-pattern color class with the intersection $\{i\}$ in $K(n,2)$, 
the integer $i$ appears at least twice while each of other integers appears at most once.
All color classes of $\psi$ are $1$-patterns: $D_{i}$ ($1 \le i \le n-2$) is a 
$1$-pattern with the intersection $\{i\}$, and $D_{n-1}$ is a $1$-pattern with the
intersection $\{n\}$. Let $\sigma$ be an automorphism of $K(n,2)$ which preserves the above color classes. 
To preserve color class $D_{i}$ ($1 \le i \le n-2$),
$\sigma$ fixes integer $i$ ($1 \le i \le n-2$),  and to preserve  color class $D_{n-1}$, $\sigma$ fixes 
integer $n$. It follows that $\sigma$ fixes integer $n-1$ and so $\sigma$ is trivial. 
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The distinguishing chromatic number of $K(n,r)$,\\where $n \ge 2r+1$ and $r \ge 3$}

In this section, we show that the distinguishing chromatic number of
$K(n,r)$ (where $n \ge 2r+1$ and $r \ge 3$) is equal to its chromatic
number $n-2r+2$. We start with the odd graph, $K(2r+1,r)$, where $r \ge
3$. We choose a partition of its vertex set $C_1 \cup C_2 \cup C_3$ as follows.
\begin{align*}
C_1 &= M_{\{1\}},\\
C_2 &= M_{\{2\}}\setminus M_{\{1\}},\\
C_3 &= [M_{\{1\}} \cup M_{\{2\}}]^c.
\end{align*} 

\begin{table}[ht] 
\caption{Occurrences of each integer $i$ in color classes $C_{1}, C_{2}, C_{3}$ of $K(2r+1,r)$} 
\centering \begin{tabular}{|c|ccc|ccc| ccc|} 
\hline $i$ && $C_{1}$ &&& $C_{2}$ &&& $C_{3}$ & \\ 
% inserts table 
\hline \hline
$1$   &&  $\binom{2r}{r-1}$&&&  $0$	&&& $0$&	  \\
\hline
$2$   &&  $\binom{2r-1}{r-2}$ &&& $\binom{2r-1}{r-1}$&&& $0$&   \\
\hline 
$3 \le i \le 2r+1$   &&  $\binom{2r-1}{r-2}$ &&& $\binom{2r-2}{r-2}$ &&& $\binom{2r-2}{r-1}$ &\\
\hline 
\end{tabular} 
\label{Ccolors} 
\end{table}


\begin{lemma} \rm\label{L:K(2r+1,r)}
The coloring $\{C_{1}, C_{2},C_{3}\}$ is a proper $3$-coloring  but not a distinguishing coloring of $K(2r+1,r)$. 
\end{lemma}
\begin{proof} It is easy to see that both $C_{1}$ and $C_{2}$ are independent sets since
each vertex of $C_{1}$  contains the integer $1$, and
each vertex of $C_{2}$ contains the integer $2$.  
Since each vertex of $C_{3}$ is a $r$-subset of $2r-1$ integers from $\{3, 4, \ldots, 2r+1\}$,
any two vertices of $C_{3}$ must have a nonempty intersection. 
Then $C_{3}$ is also an independent set. Therefore,  $\{C_{1}, C_{2}, C_{3}\}$ is a proper $3$-coloring
of $K(2r+1,r)$. On the other hand, this is not a distinguishing coloring by Table \ref{Ccolors}. 
Let $\sigma \in S_{2r+1}$ be a nontrivial permutation which fixes integer $1$ and integer $2$ and permutes 
integers $3, 4, \ldots, 2r+1$, then $\sigma$ preserves each color class $C_{1}, C_{2}, C_{3}$.  
\end{proof}



\begin{example} \rm \label{E:K(7,3)} 
A proper and distinguishing $3$-coloring of $K(7,3)$ which is derived from a proper $3$-coloring 
of $K(7,3)$ in Lemma \ref{L:K(2r+1,r)} shows that $\chi_D(K(7,3)) =3$. 
\end{example}


In the following tables, we represent the vertex $v_{\{i,j,k\}}$ by
$ijk$ briefly.  Table \ref{PCK(7,3)} provides a proper $3$-coloring $\{C_{1}, C_{2}, C_{3}\}$ of
$K(7,3)$ by Lemma \ref{L:K(2r+1,r)}.  We remove vertices $v_{\{1,2,5\}}$ and $v_{\{1,3,4\}}$ from $C_{1}$
and add the former to $C_{2}$, and latter to $C_{3}$. Then we switch vertex $v_{\{2,3,4\}} \in C_{2}$ 
with vertex $v_{\{5,6,7\}} \in C_{3}$. Finally, we switch vertex $v_{\{2,4,7\}} \in C_{2}$ with vertex $v_{\{3,5,6\}} \in C_{3}$.
We obtain a coloring $\{D_{1}, D_{2}, D_{3}\}$ of $K(7,3)$ in Table \ref{PDCK(7,3)}, where 
we underline those vertices moved around from coloring $\{C_{1}, C_{2}, C_{3}\}$. 
It is easy to check that $\{D_{1}, D_{2}, D_{3}\}$
is a proper $3$-coloring.

\begin{table}[ht] 
\caption{\label{PCK(7,3)}A proper $3$-coloring of $K(7,3)$} 
\begin{center}
    \begin{tabular}{ | l l l |}
    \hline
    $C_{1}$  & = & \{123, 124, 125, 126, 127, 134, 135, 136, 137, 145,\\
    && \ \ \ \ \ \ \ \  146, 147, 156, 157, 167\} \\
    \hline
    $C_{2}$  & = & \{234, 235, 236, 237, 245, 246, 247, 256,
257, 267\} \\
    \hline
    $C_{3}$  & = & \{567, 467, 457, 456,  367, 357, 356, 347,
346, 345\} \\
    \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[ht] 
\caption{\label{PDCK(7,3)}A proper and distinguishing $3$-coloring of $K(7,3)$} 
\begin{center}    \begin{tabular}{ | l l l |}
    \hline
    $D_{1}$  & = & \{123, 124, 126, 127, 135, 136, 137, 145, \\
    && \  \  \  \ \ \ \ \ 146, 147, 156, 157, 167\} \\
    \hline
    $D_{2}$  & = & \{\underline{567}, 235, 236, 237, 245, 246, \underline{356}, 256,
257, 267, $\underline{125}$\} \\
    \hline
    $D_{3}$  & = & \{\underline{234}, 467, 457, 456, 367, 357, \underline{247}, 347,
346, 345, $\underline{134}$\} \\
    \hline
\end{tabular}
\end{center}
\end{table}

The coloring $\{D_{1}, D_{2}, D_{3}\}$ is distinguishing by 
Table \ref{K(7,3)}, which contains the number of occurrences of integers 
$1 \le i \le 7$ in each color class.  Since all rows are pairwise different,
the only automorphism of $K(7,3)$ which preserves color classes must be
trivial.  
\qed\\

\begin{table}[ht] 
\caption{\label{K(7,3)}
Occurrences of each integer $i$ in color classes $D_{1}, D_{2}, D_{3}$ of $K(7,3)$} 
\begin{center}
\begin{tabular}{ | c | c | c | c |}
\hline
$i$ & $D_{1}$ & $D_{2}$ & $D_{3}$ \\ \hline\hline
1 & 13 & 1 & 1 \\ \hline
2 & 4 & 9 & 2\\ \hline
3 & 4 & 4 & 7 \\ \hline
4 & 4 & 2 & 9 \\ \hline
5 & 4 & 7 & 4 \\ \hline
6 & 5 & 6 & 4 \\ \hline
7 & 5 & 4 & 6 \\  \hline
\end{tabular}
\end{center}
\end{table}



Similar to the idea of Example \ref{E:K(7,3)}, we will construct a proper and distinguishing $3$-coloring 
$\{D_{1}, D_{2}, D_{3}\}$ of $K(2r+1, r)$  from the proper $3$-coloring $\{C_{1}, C_{2}, C_{3}\}$ 
of $K(2r+1,r)$ in Lemma \ref{L:K(2r+1,r)} by rearranging vertices among $C_{1}, C_{2}, C_{3}$. 
We list some special vertices of $K(2r+1,r)$ to clarify notations in
this section. Those vertices are denoted as $x_{j}$ (where $1 \le j \le r-1$), 
and $y_1$, $y_2$, $z_1$, $z_2$.
\large
\begin{eqnarray*}
x_j &=&  v_{\{1, 2; \ 4+j, 4+j+1, \ldots, r+1; \
2r-j, 2r-j+1, \ldots, 2r-1\}},\\
 & & \normalsize \mbox{ for  $1 \le j\le r-3$}.\\
x_{r-2}    &=&   v_{\{1, 2; \ r+2, r+3, \ldots, 2r-1\}},\\
x_{r-1}     &=&   v_{\{1; \ 3,4, \ldots, r+1\}},\\
y_{1}   &=&  v_{\{2, 3,4, \ldots, r+1\}},\\
y_{2}  &=&   v_{\{2; \ 4,5, \ldots, r+1; \ 2r+1\}},\\
z_{1}   &=&   v_{\{r+2, r+3, \ldots, 2r-1, 2r, 2r+1\}},\\
z_{2}  &=&   v_{\{3; \ r+2, r+3, \ldots, 2r-1, 2r\}}.
\end{eqnarray*}
\normalsize

\noindent Examples
\begin{itemize}
\item If $r=3$, then the above listed vertices are
\large

$x_{1} =  v_{\{1, 2; \ 5\}}$,
$x_{2}  =   v_{\{1; \ 3, 4\}}$

$y_{1}  =  v_{\{2, 3, 4\}}$,
$y_{2}  =   v_{\{2; \ 4; \ 7\}}$,

$z_{1}  =   v_{\{5, 6, 7\}}$,
$z_{2}  =   v_{\{3; \ 5, 6\}}$.
\vskip .2in
\normalsize
\item If $r=5$, then the above listed vertices are 

\large
$x_{1} =  v_{\{1, 2; \ 5, 6; \ 9\}}$,
$x_{2} =  v_{\{1, 2; \ 6; \ 8, 9\}}$,

$x_{3}  =   v_{\{1, 2; \ 7, 8, 9\}}$, 
$x_{4}   =   v_{\{1; \ 3, 4, 5, 6\}}$, 

$y_{1}  =  v_{\{2, 3,4, 5, 6\}}$,
$y_{2}  =   v_{\{2; \ 4,5, 6; \ 11\}}$,

$z_{1}  =   v_{\{7, 8, 9, 10, 11\}}$,
$z_{2}  =   v_{\{3; \ 7, 8, 9, 10\}}$.
\vskip .2in
\normalsize
\end{itemize}
\normalsize


\begin{table}[ht] 
\caption{Occurrences of each integer $i$ in the set of vertices $\{x_{j} | (1 \le j \le r-2)\}$, $\{x_{r-1}\}$,
$\{y_{1}, y_{2}\}$,  and $\{z_{1}, z_{2}\}$.} 
\centering \begin{tabular}{|c||cc|cc||ccc||ccc|} 
\hline 
$i$ &  	&$\{x_{j}| 1 \le j \le r-2\}$& $\{x_{r-1}\}$&		&		&$\{y_{1}, y_{2}\}$ &		&	
&$\{z_{1}, z_{2}\}$ &\\ 
\hline
$1$&  	&$r-2$&$1$& 		&	&$0$&		& 	&$0$&\\
$2$& 	&$r-2$&$0$ & 		&	&$2$& 		& 	&$0$&\\
\hline \hline
$3$& 	&$0$&$1$& 		&	&$1$&		& 	&$1$&\\
\hline\hline
$4$& 	&$0$&$1$&     		&	&$2$&     		&	&$0$&\\
$5$& 	&$1$&$1$&     		&	&$2$&     		&	&$0$&\\
$6$& 	&$2$&$1$&     		&	&$2$&     		&	&$0$&\\
$\vdots$& 	&$\vdots$&$\vdots$&     		&	&$\vdots$&     		&	&$\vdots$&\\
$r-1$& 	&$r-5$&$1$&     		&	&$2$&     		&	&$0$&\\
$r$& 	&$r-4$&$1$&     		&	&$2$&     		&	&$0$&\\
$r+1$& 	&$r-3$&$1$&     		&	&$2$&     		&	&$0$&\\
\hline\hline
$r+2$& 	&$1$&$0$&     		&	&$0$&     		&	&$2$&\\
$r+3$& 	&$2$&$0$&     		&	&$0$&     		&	&$2$&\\
$r+4$& 	&$3$&$0$&     		&	&$0$&     		&	&$2$&\\
$\vdots$& 	&$\vdots$&$\vdots$&     		&	&$\vdots$&     		&	&$\vdots$&\\
$2r-3$& 	&$r-4$&$0$&     		&	&$0$&     		&	&$2$&\\
$2r-2$& 	&$r-3$&$0$&     		&	&$0$&     		&	&$2$&\\
$2r-1$& 	&$r-2$&$0$&     		&	&$0$&     		&	&$2$&\\
\hline\hline
$2r$& 	&$0$&$0$&     		&	&$0$&     		&	&$2$&\\
$2r+1$& 	&$0$&$0$&     		&	&$1$&     		&	&$1$&\\
\hline
\end{tabular} 
\label{vertices} 
\end{table}

\begin{theorem}\label{T:K(2r+1,r)}
$\chi_D(K(2r+1,r)) = \chi(K(2r+1,r))=3$ for $r \ge 3$.
\end{theorem}
\begin{proof} It is known that $\chi_D(K(2r+1,r))\ge\chi(K(2r+1,r))=3$. To
show that $\chi_D(K(2r+1,r)) \le 3$, we construct a proper and
distinguishing $3$-coloring of $K(2r+1,r)$ with color classes $D_{1},
D_{2}, D_{3}$ as the following.
\begin{eqnarray*}
D_{1} &=&C_{1} \setminus \{x_{j} | 1 \le j \le r-1 \},\\
D_{2} &=& \left(C_{2} \setminus \{y_{1}, y_{2}\} \right)
\cup \{x_{j} | 1 \le j \le r-2\}  \cup \{z_1, z_2\},\\
D_{3} &=& \left(C_{3} \setminus \{z_{1}, z_{2}\} \right)
\cup \{x_{r-1}\}  \cup \{y_{1}, y_{2}\}.
\end{eqnarray*}

We first show that it is a proper coloring of $K(2r+1,r)$. It is
clear that $D_{1}, D_{2}, D_{3}$ form a partition of the vertex set of
$K(2r+1,r)$. All vertices in $D_{1}$ contain the integer $1$, so
$D_{1}$ is an independent set of $K(2r+1,r)$. To show that $D_{2}$ is an
independent set, first we see that its subset 
$\left(C_{2} \setminus \{y_{1}, y_{2}\} \right)  \cup \{x_{j} | 1 \le j \le r-2\}$ 
is an independent set since all vertices contain the integer
$2$. Note that the induced subgraph of $K(2r+1,r)$ generated by
$C_{2}, C_{3}$ is a matching between two sets since it is isomorphic to $K(2r,r)$.
So the vertex $z_{1} \in C_{3}$ (resp. $z_{2} \in
C_{3}$) is only adjacent to vertex $y_{1} \in
C_{2}$ (resp. $y_{2} \in C_{2}$). Therefore, $z_{1},
z_{2}$ are not adjacent to any vertex in $C_{2} \setminus
\{y_{1}, y_{2}\}$. Moreover, $z_{1}, z_{2}$ are not adjacent to any
$x_{j}$ $(1 \le j \le r-2)$ since they have at least one common
integer $2r-1$. Hence, $D_{2}$ is an independent set. It remains to show that
$D_{3}$ is an independent set. It is clear that its subset
$(C_{3} \setminus \{z_{1},z_{2}\}) \cup \{y_{1}, y_{2}\}$ is an independent set since
$y_{1}, y_{2}$ are not adjacent to any vertex in $C_{3} \setminus \{z_{1},z_{2}\}$. 
The only vertex in $C_{3}$ which
$x_{r-1}$ is adjacent to is $z_{1}$ because they are disjoint. 
Hence $x_{r-1}$ is
not adjacent to any vertex in $C_{3} \setminus \{z_{1},z_{2}\}$. 
Also $x_{r-1}$ is not adjacent to either $y_{1}$ or $y_{2}$
because they have at least one common integer $r+1$. Therefore,
$D_3$ is also an independent set.


\begin{table}[ht] 
\caption{Occurrences of each integer $i$ in color classes $D_{1}, D_{2}, D_{3}$ of $K(2r+1,r)$} 
\centering \begin{tabular}{|c|ccc|ccc|ccc|c|} 
\hline 
$i$ &  	&$D_{1}$&		&	&$D_{2}$ &		&	& $D_{3}$ & 	&\text{Remarks}\\ 
\hline
\rule{0pt}{3ex}$1$&  	$\binom{2r}{r-1}$&$-$&$(r-1)$ 		&	 $0$& $+$ &$(r-2)$		& 	$0$&$+$&$1$		
& GROUP 1  \\

\rule{0pt}{3ex}$2$& 	$\binom{2r-1}{r-2}$&$-$&$(r-2)$ 		&	$\binom{2r-1}{r-1}$&$+$&$(r-4)$ 	& 	$0$&$+$&$2$ 
&  \\
\hline \hline

\rule{0pt}{3ex}$3$& 	$\binom{2r-1}{r-2}$&$-$&$1$ 		&	$\binom{2r-2}{r-2}$&$+$&$0$		 & 	
$\binom{2r-2}{r-1}$&$+$&$1$  &GROUP 2 \\
\hline\hline

\rule{0pt}{3ex}$4$& 	$\binom{2r-1}{r-2}$&$-$&$1$     		&	$\binom{2r-2}{r-2}$&$-$&$2$     		&
$\binom{2r-2}{r-1}$&$+$&$3$   &GROUP 3   \\

\rule{0pt}{3ex}$5$& 	$\binom{2r-1}{r-2}$&$-$&$2$     		&	$\binom{2r-2}{r-2}$&$-$&$1$     		&
$\binom{2r-2}{r-1}$&$+$&$3$   &   \\

\rule{0pt}{3ex}$6$&  	$\binom{2r-1}{r-2}$&$-$&$3$    			&	$\binom{2r-2}{r-2}$&$+$&$0$      		&
$\binom{2r-2}{r-1}$&$+$&$3$  &   \\

\vdots& 	&\vdots&	&    &\vdots&     & 	&\vdots&  & \\


$r-1$&  	$\binom{2r-1}{r-2}$&$-$&$(r-4)$  	&   	$\binom{2r-2}{r-2}$&$+$&$(r-7)$     		&
$\binom{2r-2}{r-1}$&$+$&$3$   &  \\

\rule{0pt}{3ex}$r$&  	$\binom{2r-1}{r-2}$&$-$&$(r-3)$   	&	$\binom{2r-2}{r-2}$&$+$&$(r-6)$     		&
$\binom{2r-2}{r-1}$&$+$&$3$   &  \\

\rule{0pt}{3ex}$r+1$&  	$\binom{2r-1}{r-2}$&$-$&$(r-2)$	&	$\binom{2r-2}{r-2}$&$+$&$(r-5)$     		&
$\binom{2r-2}{r-1}$&$+$&$3$   &  \\
\hline \hline

\rule{0pt}{3ex}$r+2$&  	$\binom{2r-1}{r-2}$&$-$&$1$	   	&	$\binom{2r-2}{r-2}$&$+$&$3$    		&
$\binom{2r-2}{r-1}$&$-$&$2$   &GROUP 4  \\

\rule{0pt}{3ex}$r+3$&  	$\binom{2r-1}{r-2}$&$-$&$2$	   	&	$\binom{2r-2}{r-2}$&$+$&$4$     		&
$\binom{2r-2}{r-1}$&$-$&$2$   &  \\

\rule{0pt}{3ex}$r+4$&  	$\binom{2r-1}{r-2}$&$-$&$3$   	&	$\binom{2r-2}{r-2}$&$+$&$5$    			&
$\binom{2r-2}{r-1}$&$-$&$2$   &  \\

\vdots& 	&\vdots&	&    &\vdots&     & 	&\vdots&  & \\

$2r-3$&  	$\binom{2r-1}{r-2}$&$-$&$(r-4)$   &	$\binom{2r-2}{r-2}$&$+$&$(r-2)$     		&
$\binom{2r-2}{r-1}$&$-$&$2$   &  \\

\rule{0pt}{3ex}$2r-2$&  	$\binom{2r-1}{r-2}$&$-$&$(r-3)$   &	$\binom{2r-2}{r-2}$&$+$&$(r-1)$     		&
$\binom{2r-2}{r-1}$&$-$&$2$   &  \\

\rule{0pt}{3ex}$2r-1$&  	$\binom{2r-1}{r-2}$&$-$&$(r-2)$   &	$\binom{2r-2}{r-2}$&$+$&$r$    		&
$\binom{2r-2}{r-1}$&$-$&$2$   &  \\
\hline \hline

\rule{0pt}{3ex}$2r$& 	$\binom{2r-1}{r-2}$&$+$&$0$   	&	$\binom{2r-2}{r-2}$&$+$&$2$     		&
$\binom{2r-2}{r-1}$&$-$&$2$   &GROUP 5  \\

\rule{0pt}{3ex}$2r+1$& 	$\binom{2r-1}{r-2}$&$+$&$0$   	&	$\binom{2r-2}{r-2}$&$+$&$0$    		&
$\binom{2r-2}{r-1}$&$+$&$0$   &  \\
\hline\end{tabular} 
\label{Dcolors} 
\end{table}
It remains to show that $\{D_{1}, D_{2}, D_{3}\}$ is also a distinguishing coloring of $K(2r+1,r)$. 
We first construct a table where row $i$ contains the number of occurrences 
of integer $i$ (for each $1 \le i \le 2r+1$) in vertices  $x_{j}$ ($1 \le j \le r-1$), $y_{1}, y_{2}$ 
and $z_{1}, z_{2}$, see Table \ref{vertices}. By Table \ref{Ccolors} and Table \ref{vertices}, 
we construct Table \ref{Dcolors} where row $i$
contains the number of occurrences of integer $i$ 
(for each $1 \le i \le 2r+1$) in color classes $D_{1}, D_{2}, D_{3}$.

We will show that all rows are pairwise different from each other, and so any
automorphism of $K(2r+1,r)$ which preserves the above color classes must be trivial.
The groups in Table \ref{Dcolors} are determined by $D_{3}$ column. 
Each of the  row $1$,  row $2$,  row $3$,  row $2r$, and  row $2r+1$ 
is distinguished by its unique entry in column $D_{3}$.  The remaining rows 
are divided into GROUP 3 and GROUP 4 by $D_{3}$ column. 
Rows in GROUP 3 are pairwise distinguished from each other
because of their entries in $D_{1}$ column, and rows in GROUP 4 are
pairwise distinguished from each other by the same reason. 
Hence, all rows are pairwise different from each other. 
It follows that the only automorphism which preserves color classes
must be trivial. Therefore, the proper $3$-coloring $\{D_{1}, D_{2},
D_{3}\}$ is also distinguishing. 
\end{proof}

\begin{theorem}\rm\label{T:K(n,r)}
Let $n$, $r$ be integers such that $n \ge 2r+1$ and $r \ge 3$. Then
$\chi_D(K(n,r))=\chi(K(n,r))=n-2r+2$.
\end{theorem}
\begin{proof} 
By induction on $n$. If $n=2r+1$, then by Theorem
\ref{T:K(2r+1,r)}, $\chi_D(K(2r+1,r))=\chi(K(2r+1,r))=3$ where $r
\ge 3$. Assume that $\chi_D(K(n',r))=\chi(K(n',r))=n'-2r+2$ for any
integer $2r+1 \le n'<n$ where $r \ge 3$. We will show that it is
true for $K(n,r)$ where $r \ge 3$. 

Let $H=K(n,r) - M_{\{n\}}$ be the induced subgraph 
of $K(n,r)$ obtained by deleting all vertices of $M_{\{n\}}$, the
maximum independent set of $K(n,r)$ with the intersection $\{n\}$.
Then $H$ is isomorphic to $K(n-1,r)$. By induction hypothesis, $H$
has a proper and distinguishing $(n-2r+1)$-coloring with  color
classes $D_{1}, D_{2}, \ldots, D_{n-2r+1}$ such that for each integer $i$ 
($1 \le i \le n-1$), the ordered $(n-2r+1)$-tuple of its number of occurrences 
in vertices of $D_{1}, D_{2}, \ldots, D_{n-2r+1}$ is unique.

\begin{table}[ht] 
\caption{Occurrences of each integer $i$ in color classes $D_{1}, D_{2}, D_{3}, \ldots, D_{n-2r+2}$ of $K(n,r)$} 
\centering 
\begin{tabular}{|c|c|c|c||c|c|c|c|c|} 
\hline 
$i$ 		&$D_{1}$		&$D_{2}$ 		& $D_{3}$  	&$D_{4}$ 		&$D_{5}$		&$\cdots$		&$D_{n-2r+1}$		&$D_{n-2r+2}$\\ 
\hline
\rule{0pt}{3ex}$1$	  	&$*$		&$*$		&$*$ 		&${2r \choose r-2}$			&${2r+1 \choose r-2}$			&$\cdots$			&${n-3 \choose r-2}$ &${n-2 \choose r-2}$ \\	

\rule{0pt}{3ex}$2$	  	&$*$		&$*$		&$*$ 		&${2r \choose r-2}$			&${2r+1 \choose r-2}$			&$\cdots$			&${n-3 \choose r-2}$ &${n-2 \choose r-2}$ \\	
\vdots	&$\vdots$		& $\vdots$		&$\vdots$	    	&\vdots		&\vdots     	&\vdots 		&\vdots			&\vdots \\

$2r+1$	&$*$		&$*$		&$*$		&${2r \choose r-2}$			&${2r+1 \choose r-2}$			&$\cdots$			&${n-3 \choose r-2}$ &${n-2 \choose r-2}$\\
\hline\hline
\rule{0pt}{3ex}$2r+2$	&$0$			&$0$			&$0$			&${2r+1 \choose r-1}$		&${2r+1 \choose r-2}$			&$\cdots$		&${n-3 \choose r-2}$        &${n-2 \choose r-2}$	\\
\hline

\rule{0pt}{3ex}$2r+3$	&$0$			&$0$			&$0$			&$0$						&${2r+2 \choose r-1}$ 			&$\cdots$		&${n-3 \choose r-2}$	&${n-2 \choose r-2}$	\\
\hline
\vdots	&\vdots		&\vdots		&\vdots	    	&\vdots		&\vdots     	&\vdots 		&\vdots			&\vdots \\
\hline
\rule{0pt}{3ex}$n-1$	&$0$			&$0$			&$0$			&$0$			&$0$			&$0$			&${n-2 \choose r-1}$	&${n-2 \choose r-2}$	\\
\hline
\rule{0pt}{3ex}$n$		&$0$			&$0$			&$0$			&$0$			&$0$			&$0$			&$0$				&${n-1 \choose r-1}$\\
\hline
\end{tabular} 
\label{K(n,r)} 
\end{table}


Let $D_{n-2r+2}=M_{\{n\}}$. Then $D_{n-2r+2}$ is an independent set of $K(n,r)$. 
It follows that $\{D_{i} | 1 \le i \le n-2r+2 \}$ is a proper coloring 
of $K(n,r)$.  Note that integer $n$ is the only integer that does not appear in 
any color classes $D_{i}$ for $1 \le i \le n-2r+1$, 
and appears ${n-1 \choose r-1}$ times in color class $D_{n-2r+2}$.
Hence, for integer $n$, the ordered $(n-2r+2)$-tuple for the number of its occurrences 
in vertices of  $D_{1}, D_{2}, \ldots, D_{n-2r+1}, D_{n-2r+2}$ is unique. 
By the induction hypothesis,  this is also true for each integer $i$ where $1 \le i \le n-1$, 
see Table \ref{K(n,r)}. If $\sigma$ is a nontrivial automorphism of $K(n,r)$ which
preserves color classes $D_{1}, D_{2}, \ldots, D_{n-2r+2}$, then
$\sigma$ must fix each integer $1, 2, \ldots, n$.  Therefore, $\sigma$ is trivial. 
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The first author's work was supported by the Van Vleck fund from Wesleyan University.
The authors thank the referee for many helpful suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
\begin{thebibliography}{10}
\bibitem{AB07}
M.~O. Albertson and D.~L. Boutin.
\newblock Using determining sets to distinguish Kneser graphs. 
\newblock {\em  Electron. J. Combin.},  
14(1): Research Paper 20, 2007.

\bibitem{AC96}
M.~O. Albertson and K.~L. Collins.
\newblock  Symmetry breaking in graphs.
\newblock {\em Electron. J. Combin.}, 
3(1):  Research Paper 18, 1996. 

\bibitem{ACD08}
V.~Arvind, C.~T. Cheng, and N.~R. Devanur.
\newblock On computing the distinguishing numbers of planar graphs and beyond: a counting approach.
\newblock {\em SIAM J. Discrete Math.},
 22(4): 1297--1324, 2008.

\bibitem{Ch08}
M.~Chan.
\newblock The distinguishing number of the augmented cube and hypercube powers.
\newblock {\em Discrete Math.},
308(11): 2330--2336, 2008.

\bibitem{CHK10} 
J.~O. Choi, S.~G. Hartke, and H.~Kaul.
\newblock Distinguishing chromatic number of cartesian products of graphs.
\newblock {\em SIAM J. Discrete Math.}, 
24(1): 82--100, 2010.

\bibitem{CHT09} 
K.~L. Collins, M.~Hovey, and A.~N. Trenk.
\newblock Bounds on the distinguishing chromatic number.
\newblock {\em Electron. J. Combin.},
16(1):  Research Paper 88, 2009.

\bibitem{CT06}
K.~L. Collins and A.~N. Trenk.
\newblock The distinguishing chromatic number.
\newblock {\em Electron. J. Combin.}, 
13(1):  Research Paper 16, 2006.

\bibitem{HT96}
G.~Hahn and C.~Tardif.
\newblock Graph homomorphisms: structure and symmetry.
\newblock {\em Graph symmetry (Montreal, PQ)},  pages 107--166,  1996.
{\em NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.}, 
497, Kluwer Acad. Publ., Dordrecht, 1997.

\bibitem{IJK08}
W.~Imrich, J.~Jerebic, and S.~Klav\v{z}ar.
\newblock The distinguishing number of Cartesian products of complete graphs. 
\newblock {\em European J. Combin.}, 
29(4):  922--929, 2008.


\bibitem{IK00} 
W.~Imrich and S.~Klav\v{z}ar.
\newblock   Product graphs, Structure and recognition.  
\newblock {\em Wiley-Interscience Series in Discrete Mathematics and
Optimization}, Wiley-Interscience, New York, 2000.

\bibitem{IKT07}
W.~Imrich, S.~Klav\v{z}ar, and V.~Trofimov. 
\newblock  Distinguishing infinite graphs. 
\newblock {\em Electron. J. Combin.}, 
14(1): Research Paper 36, 2007.

\bibitem{T04}
J.~Tymoczko.
\newblock Distinguishing numbers for graphs and groups. 
\newblock {\em Electron. J. Combin.},
11(1): Research paper 63,  2004.

\bibitem{KWZ06}
S.~Klav\v{z}ar,  T.~Wong, and X.~Zhu.
\newblock  Distinguishing labellings of group action on vector spaces and graphs.
\newblock {\em J. Algebra}, 
303(2): 626--641, 2006. 

\bibitem{R79}
F.~Rubin. 
\newblock   Problem 729 p. 128. 
\newblock {\em Journal of Recreational Mathematics}, 
11: 1979.

\bibitem{T07} 
D.~K. Tang.
\newblock The distinguishing chromatic number of the graph $C_n\circ I_m$.
\newblock {\em  M.A. dissertation}, Wesleyan University, Middletown, CT, 2007.

\bibitem{WJ08}
J.~Weigand and M.~S. Jacobson.
\newblock  Distinguishing and distinguishing chromatic numbers of generalized Petersen graphs. 
\newblock {\em AKCE Int. J. Graphs Comb.}, 
5(2): 199--211, 2008.

\bibitem{WaZh07} 
M.~E. Watkins and X.~Zhou.
\newblock Distinguishability of locally finite trees.
\newblock {\em Electron. J. Combin.},
14(1): Research paper 29,  2007.
\end{thebibliography}

\end{document}
