%%%%%%%%%%%%%%%%%%%%%% file gc_template.tex %%%%%%%%%%%%%%%%%%%%%%% % % This is a template file for the Svgc class % % Copy it to a new file with a new name and use it as the basis % for your article % %%%%%%%%%%%%%%%%%%%%%%%% Springer-Verlag %%%%%%%%%%%%%%%%%%%%%%%%%% % % First comes an example EPS file -- just ignore it and % proceed on the \documentclass line %\begin{filecontents*}{example.eps} %%!PS-Adobe-3.0 EPSF-3.0 %%%BoundingBox: 19 19 221 221 %%%CreationDate: Mon Sep 29 1997 %%%Creator: programmed by hand (JK) %%%EndComments %gsave %newpath %20 20 moveto %20 220 lineto %220 220 lineto %220 20 lineto %closepath %2 setlinewidth %gsave %.4 setgray fill %grestore %stroke %grestore %\end{filecontents*} % % % %\documentclass[Svgc]{Svgc} % This results is missing periods in theorem numbers \documentclass[Svgc,numbook]{Svgc} % This seems to restore the missing periods % Remove any % below to load the required packages %\usepackage{latexsym} %\usepackage{graphics} %\usepackage{amsthm} \usepackage{stmaryrd} \usepackage{amssymb} \usepackage{amsmath} \usepackage{graphicx} % etc % % Insert the name of "your" journal with the command below: \journalname{Graphs and Combinatorics} % %%Authors' predefined commands \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{conj}[thm]{Conjecture} %\theoremstyle{definition} %incompatable with Svgc - use with \rm \newtheorem{defn}[thm]{Definition} %\theoremstyle{remark} %incompatable with Svg - use with \rm \newtheorem{rem}[thm]{Remark} \renewcommand{\le}{\leqslant} \renewcommand{\ge}{\geqslant} \newcommand{\F}{\mathbb{F}} \newcommand{\cart}{\boxempty} \renewcommand{\mod}[1]{\ (\text{mod }#1)} \newcommand{\suchthat}{\mid} \newcommand{\red}{\text{SR}} \renewcommand{\deg}{\textd} \newcommand{\idx}{\text{idx}} \newcommand{\defnum}{\mathop{\rm def}} \begin{document} % \title{Silver Cubes} %\subtitle{Insert your subtitle here, if you have one.} %\author{First author\inst{1}\and Second author\inst{2}% etc \author{Mohammad Ghebleh\inst{1}\thanks{\emph{Present address:} Mohammad's present address goes here.}% \and Luis A. Goddyn\inst{1}\thanks{This research was supported by a Canada NSERC Discovery Grant.}% \and Ebadollah S. Mahmoodian\inst{2}\thanks{Partially supported by the institutes CECM and IRMACS and the departments of Mathematics and Computing Science at Simon Fraser University. Grateful thanks are extended here and also to the Institute for Advanced Studies in Basic Sciences, Iran for support in the final stages of this paper.}% \and Maryam Verdian-Rizi\inst{1} % \thanks is optional - remove next line if not needed %\thanks{\emph{Present address:} Insert the address here if needed}% } % Do not remove %running header \titlerunning{Silver Cubes}% \authorrunning{M.~Ghebleh\inst{1} \and L.~Goddyn\inst{2} \and E.~Mahmoodian\inst{3} \and M.~Verdian-Rizi\inst{4}} % \offprints{Luis Goddyn} % Insert a name or remove this line % \institute{ Department of Mathematics, Simon Fraser University, Burnaby, BC\ \ V5A~1S6, Canada \and Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran} % % \maketitle % \begin{abstract} An $n\times n$ matrix $A$ is said to be \emph{silver} if, for $i=1,2,\ldots,n$, each symbol in $\{1,2,\ldots,2n-1\}$ appears either in the $i$th row or the $i$th column of~$A$. The 38th International Mathematical Olympiad asked whether a silver matrix exists with $n=1997$. More generally, a \emph{silver cube} is a triple $(K_n^d, I, c)$ where $I$ is a maximum independent set in a Cartesian power of the complete graph $K_n$, and $c:V(K_n^d)\rightarrow \{1,2,\dots,d(n-1)+1\}$ is a vertex colouring where, for $v \in I$, the closed neighbourhood $N[v]$ sees every colour. Silver cubes are related to codes, dominating sets, and those with $n$ a prime power are also related to finite geometry. We present here algebraic constructions, small examples, and a product construction. The nonexistence of silver cubes %for some $(n,d)$ is for $d=2$ and some values of $n$, is proved using bounds from coding theory. \end{abstract} % \begin{keyword} silver matrix, graph colouring, coding theory, domination in graphs, finite projective geometry \end{keyword} % \receive{December, 2002 (Date incorrect)} \finalreceive{December 22, 2002 (Date incorrect)} %\noindent\texttt{$\backslash$tensor\{S\}}\ creates $\tensor{S}$ and \texttt{$\backslash$vector\{S\}}\ creates $\vector{S}$.\\ %\noindent\texttt{$\backslash$qed}\ creates \qed \section{Introduction}\label{sec-intro} An $n\times n$ matrix $A$ is said to be \emph{silver} if, for every $i=1,2,\ldots,n$, each symbol in $\{1,2,\ldots,2n-1\}$ appears either in the $i$th row or the $i$th column of~$A$. A~problem of the 38th International Mathematical Olympiad in 1997 introduced this definition and asked to prove that no silver matrix of order~1997 exists. In~\cite{IMO97} the motivation behind this problem as well as a solution is presented: a silver matrix of order $n$ exists if and only if $n=1$ or $n$ is even. The \emph{Cartesian product} of two graphs $G$ and $H$, denoted by $G\cart H$, is the graph with vertex set $V(G)\times V(H)$ in which two vertices $(x,y)$ and $(x',y')$ are adjacent if and only if $x=x'$ and $yy'\in E(H)$, or $y=y'$ and $xx'\in E(G)$. An~$n\times n$ matrix $A$ can be thought of as a labeling of the vertices of~$K_n\cart K_n$, where $K_n$ is the complete graph of order $n$. If $V(K_n)=\{1,2,\ldots,n\}$, then $I=\{(i,i)\suchthat i=1,2,\ldots,n\}$ corresponds to the diagonal cells of~$A$. Thus, a silver matrix is a (proper) $(2n-1)$-colouring of $K_n\cart K_n$ such that for every $x\in I$, every colour appears either on~$x$ or on a neighbour of~$x$. \begin{defn} \rm Any maximum independent set of a graph is called a \emph{diagonal} of that graph. Let $c$ be a proper $(r+1)$-colouring of an $r$-regular graph~$G$. A~vertex $x$ in $G$ is said to be \emph{rainbow} with respect to $c$ if every colour appears in the \emph{closed neighbourhood} $N[x]=N(x)\cup\{x\}$. Given a diagonal $I$ of $G$, the colouring $c$ is said to be \emph{silver with respect to $I$} if every $x\in I$ is rainbow with respect to $c$. We say $G$ is \emph{silver} if it admits a silver colouring with respect to some diagonal. If all vertices of $G$ are rainbow, then $c$ is called a \emph{totally silver} colouring of~$G$ and $G$ is said to be \emph{totally silver}. \label{defn-silver} \end{defn} With our definition, silver matrices are closely related to \emph{defining sets} of graph colourings (cf. Section~\ref{sec-defset}). This helps justify our definition. %We denote the Cartesian power %$\overbrace{G\cart G\cart\cdots\cart G}^d$ by $G^d$. The \emph{Cartesian power} $G^d$ of a graph $G$ is the graph recursively defined by $G^1=G$, and $G^d = G^{d-1} \!\cart G$ for $d>1$. The graph $K_n^d$ is called a \emph{cube of side $n$ and dimension $d$} or an \emph{$(n,d)$-cube} for short. A silver colouring of an $(n,d)$-cube (with respect to some diagonal) is called a \emph{silver $(n,d)$-cube}. In this paper we study silver $(n,d)$-cubes. %the graphs $K_n^d$. These design-like objects exist for only certain pairs $(n,d)$. Although we know of no existing literature (for $d>2$), %these objects silver $(n,d)$-cubes are attractive, challenging to construct, and appear to be connected with classical combinatorics, including coding theory, projective geometry and dominating sets in graphs. %A silver colouring of $K_n^d$ is called a %\emph{silver cube of side $n$ and dimension~$d$}, or a %\emph{silver $(n,d)$-cube} for short. A \emph{silver $d$-cube} is %a silver cube of dimension~$d$. We summarize here the main results of this paper. \begin{enumerate} % %\item[(i)] If a silver $(m,d)$-cube and a silver $(n,d)$-cube exist, %then a silver $(mn,d)$-cube exists (with respect to some diagonal). \item[(i)] If the $(m,d)$-cube and the $(n,d)$-cube are silver, then the $(mn,d)$-cube is silver. % %\item[(ii)] For every $n=2^{r}3^{s}5^{t}7^{u}$ a silver $(n,3)$-cube exists. \item[(ii)] For every $n=2^{r}3^{s}5^{t}7^{u}$ the $(n,3)$-cube is silver. % %\item[(iii)] If $q$ is a prime power, then a silver %$(q,q^{t})$-cube and a totally silver %$(q,\frac{q^{t}-1}{q-1})$-cube exist for every $t\ge 1$. \item[(iii)] If $q$ is a prime power and $t\ge 1$, then the $(q,q^{t})$-cube is silver and the $(q,\frac{q^{t}-1}{q-1})$-cube is totally silver. % %\item[(iv)] If $p$ is a prime, then a silver $(p^r,p^s)$-cube %exists for every $r$ and $s$. \item[(iv)] If $p$ is a prime, then the $(p^r,p^s)$-cube is silver for every $r, s \ge 0$. % %\item[(v)] If $d=2^t-1$ or $d=2^t$ for some $t$, then a silver %$(2,d)$-cube exists. Moreover, if $d$ is odd, then every silver %$(2,d)$-cube is totally silver and these exist if and only if %$d=2^{t}-1$ for some~$t$. If $k\ge 1$ then no silver %$(2,4k+2)$-cube exists. \item[(v)] If $d=2^t-1$ or $d=2^t$ for some $t$, then the $(2,d)$-cube is silver. Moreover if $d$ is odd, then every silver $(2,d)$-cube is totally silver and these exist if and only if $d=2^{t}-1$ for some~$t$. If $k\ge 1$ then no silver $(2,4k+2)$-cube exists. % \end{enumerate} Claims (i) and (ii) are proved in Section~\ref{sec-product}. Claims (iii) and (iv) are proved in Sections~\ref{sec-q}. Claim (v) is proved in Section~\ref{sec-hypercube}. \section{Notation and motivation}\label{sec-notation} We often identify the vertices of $K_n^d$ with words of length $d$ from either the alphabet $S=\{0,1,\ldots,n-1\}$, or when $n$ is a prime power, with $d$-dimensional vectors over an $n$-element field $\F_n$. In symbols, $V(K_n^d)=S^d$ or $V(K_n^d)=\F_n^d$. We use bold face characters to emphasize that a variable is a word or a vector. The \emph{Hamming distance} of two words is the number of coordinates in which they differ. Two vertices of $K_n^d$ are adjacent if and only if they are at Hamming distance~$1$. Note that for every $k\in S$, the set % \[ I_k=\{\mathbf{x}=x_1\ldots x_d\in S^d\suchthat x_1+\cdots+x_d=k\mod{n}\} \] % is a diagonal of~$K_n^d$. We call $I_0$ the \emph{back-circulant diagonal} of $K_n^d$. This terminology is motivated by a bijective correspondence between diagonals of $K_n^3$ and Latin squares of order~$n$. Every diagonal of $K_n^d$ has cardinality~$n^{d-1}$. We use the following in Section~\ref{sec-hypercube}. \begin{prop} \label{prop-parity} For any silver $(n,d)$-cube with respect to a diagonal~$I$, %Let $c$ be a silver $(n,d)$-cube with respect to a diagonal~$I$. Then the number of times each colour appears on $I$ is congruent to $n^{d-1}$ modulo~$d$. \end{prop} % \begin{proof} %Let $c:V(K_n^d)\to\{0,1,\ldots,d(n-1)\}$ be silver with respect Let $c:V(K_n^d)\to\{0,1,\ldots,d(n-1)\}$ be a silver colouring with respect to~$I$. Let $i\in\{0,1,\ldots,d(n-1)\}$ be a colour. Every $\mathbf{v}\in I$ with $c(\mathbf{v})\not=i$ has a unique neighbour~$\mathbf{x}\notin I$ with~$c(\mathbf{x})=i$. On the other hand every vertex $\mathbf{x}$ of $K_n^d$ not in $I$ with $c(\mathbf{x})=i$ has exactly $d$ neighbours in~$I$. Therefore the vertices of~$I$ which have a colour other than~$i$ are partitioned into sets of size~$d$ according to their neighbours which have colour~$i$. This implies that $d$ divides $\lvert\{\mathbf{v}\in I\suchthat c(\mathbf{v})\not=i\}\rvert = n^{d-1}-\lvert\{\mathbf{v}\in I\suchthat c(\mathbf{v})=i\}\rvert$. \qed \end{proof} Once a diagonal~$I$ is specified, one can reduce the problem of finding a silver colouring of an $r$-regular graph $G$ to an ordinary vertex colouring problem as follows. Let $H$ be the graph obtained from $G$ by joining every two vertices which have a common neighbour in~$I$. Then by the definition of a silver colouring, $G$ has a silver colouring with respect to~$I$ if and only if $\chi(H)=r+1$, where $\chi(H)$ denotes the chromatic number of~$H$. On the other hand since $I$ is an independent set in $G$ and the neighbourhood of every $x\in I$ in $H$ is an $r$-clique, we have $\chi(H)=r+1$ if and only if $\chi(H-I)\le r+1$. We call the graph $H-I$ the \emph{silver reduction} of $G$ with respect to $I$ and denote it by~$\red(G,I)$. This proves the following. \begin{prop} Let $I$ be a diagonal of an $r$-regular graph $G$. Then $G$ has a silver colouring with respect to $I$ if and only if $\red(G,I)$ is $(r+1)$-colourable. \label{prop-reduction} \end{prop} This reduction is critical in accelerating computer searches for silver cubes. It is also used in Section~\ref{sec-hypercube} to prove the nonexistence of certain silver cubes. A~similar reduction can be carried out for totally silver colourings: The \emph{square} of a graph $G$, denoted by $G^{(2)}$, is the graph obtained from~$G$ by adding a new edge joining each pair of vertices at distance~$2$. The following is immediate from the definitions. \begin{prop} \label{prop-totSilver} An $r$-regular graph $G$ is totally silver if and only if $\chi(G^{(2)})=r+1$. \label{prop-G2} \end{prop} % This proposition shows a relation between our problem and the so-called hypercube colouring problems, namely colouring the graphs $Q_d^{(2)}$ and~$Q_d^{(3)}$. These problems, introduced in the study of scalability of optical networks~\cite{Wan,Zhou2}, are also of interest in coding theory. %Note that any %$n$-colouring of $K_n$ is an $(n,1)$-silver cube. Any proper colouring of $K_n$ is a silver $(n,1)$-cube. Silver $(n,2)$-cubes are silver matrices, which are studied in~\cite{IMO97}. In this paper we study silver cubes of dimension at least~$3$. The totally silver colouring problem is also related to domination in graphs. A set of vertices in a graph is a \emph{dominating set} if every vertex outside the set has a neighbour in the set. The {\em domatic number} problem \cite[\S 8.3]{MR1605684} is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. An easy upper bound on the domatic number of a graph $G$ is $\delta(G)+1$ where $\delta(G)$ is the minimum degree of~$G$. A graph $G$ with domatic number $\delta(G)+1$ is said to be {\em domatically full}. % \begin{prop} %A regular graph is totally silver if and only if it is domatically full. A regular graph has a totally silver colouring if and only if it is domatically full. \end{prop} % \begin{proof} % If %$G$ is totally silver, and $c$ is a totally silver colouring of $G$, then each colour class $c^{-1}(i)$ is a dominating set since every vertex with colour $j\not=i$, must be adjacent to a vertex with colour $i$ by definition. % %On the other hand, Conversely, if $V(G)=S_0\cup\ldots\cup S_r$ is a partition of $V(G)$ into dominating sets where $r=\delta(G)$, then every vertex in $S_i$ is adjacent to at least one vertex in each $S_j$ with $j\not=i$. Therefore if we define $c(x)=i$ for all $x\in S_i$, all the colours $0,1,\ldots,r$ appear in the closed neighbourhood of every vertex. Thus $c$ is a totally silver colouring of~$G$. \qed \end{proof} \section{A product construction}\label{sec-product} For any dimension $d$, the set of side lengths for which silver $d$-cubes exist is multiplicative. \begin{thm} \label{thm-product} %If a silver $(m,d)$-cube and a silver $(n,d)$-cube exist, then a silver %$(mn,d)$-cube exists. If the $(m,d)$-cube and the $(n,d)$-cube are silver, then the $(mn,d)$-cube is silver. \end{thm} Before presenting the general proof, we illustrate the special case $m=2$, $d=3$. That is we use the silver $(2,3)$-cube of Figure~\ref{fig-2cube} to double the side of any silver $(n,3)$-cube. \begin{figure}[ht] \begin{center} \includegraphics{fig-2.mps} \end{center} \caption{The unique silver $(2,3)$-cube. A diagonal is indicated by shading.} \label{fig-2cube} \end{figure} Let $A:V(K_n^{3})\to\{1,2,\ldots,3n-2\}$ be a silver colouring of $K_n^3$ with respect to a diagonal~$I$. We aim to produce a silver colouring $D$ of $K_{2n}^3$. For $i=0,1,2,3$, let $A_{i+1}$ be the colouring of $K_n^3$ obtained from $A$ by adding $ni$ to each colour~$k$, where $2n-1\le k\le 3n-2$. Let $C_{i+1}$ be a proper colouring of $K_n^3$ with the colours $\{ni+2n-1,\ldots,ni+3n-2\}$. Each of the eight blocks in Figure~\ref{fig-double} represents an $n\times n\times n$ subcube of the cube of side~$2n$. Let $D$ be the colouring of $K_{2n}^3$ in which each subcube is coloured according to its label in Figure~\ref{fig-double}. We claim that $D$ is a silver colouring. \begin{figure}[ht] \begin{center} %\begin{tabular}{ccc} %\includegraphics{fig-201.mps} %&& %\includegraphics{fig-202.mps} %\end{tabular} \includegraphics[height=2.5cm]{fig-203.eps} \end{center} \caption{Template for the doubling of a silver $3$-cube.} \label{fig-double} \end{figure} %Let $I_i$ be the set of vertices in Let $J_i$ be the set of vertices in the subcube coloured by $A_i$ which correspond to the diagonal~$I$ of~$A$. We claim that $D$ is silver with respect to the diagonal %$I_1\cup I_2\cup I_3\cup I_4$. Let $\mathbf{x}\in I_i$ for some $i=1,2,3,4$. Since $A$ $J_1\cup J_2\cup J_3\cup J_4$. Let $\mathbf{x}\in J_i$ for some $i=1,2,3,4$. Since $A$ is silver, the colours $1,2,\ldots,2n-2$ and the colours $n(i-1)+2n-1,\ldots,n(i-1)+3n-2$ all appear in the closed neighbourhood of $\mathbf{x}$ in the subcube coloured by $A_i$. On the other hand the neighbourhood of $\mathbf{x}$ in the subcube coloured by $C_j$ is an $n$-clique for $j\not=i$ and is empty for $j=i$. Since $C_j$ is a proper colouring of $K_n^3$, for every $j\not=i$, the colours $n(j-1)+2n-1,\ldots,n(j-1)+3n-2$ all appear in the neighbourhood of $\mathbf{x}$ in $C_j$. Therefore all the colours $1,2,\ldots,6n-2$ appear in~$N[\mathbf{x}]$. \begin{figure}[ht] \begin{center} \includegraphics[width=6.5cm]{fig-3.mps} \end{center} \caption{A silver $(3,3)$-cube with respect to the (shaded) back-circulant diagonal.} \label{fig-3cube} \end{figure} The silver $(4,3)$-cube and $(6,3)$-cube presented in Figures~\ref{fig-4cube} and~\ref{fig-6cube} are obtained by applying this doubling construction to the silver $3$-cubes of sides $2$ and $3$ presented in Figures~\ref{fig-2cube} and~\ref{fig-3cube}. \begin{figure}[ht] \begin{center} \includegraphics[width=10cm]{fig-4.mps} \end{center} \caption{A $(4,3)$-cube which is silver with respect to two inequivalent diagonals. One is shaded, the other is circled.} \label{fig-4cube} \end{figure} \begin{figure}[ht] \begin{center} \includegraphics[width=11cm]{fig-6.mps} \end{center} \caption{A silver $(6,3)$-cube obtained by doubling a silver $(3,3)$-cube.} \label{fig-6cube} \end{figure} Every diagonal $I$ of $K_n^{3}$ is equivalent to a Latin square $L$ of order~$n$ (specifically, $L_{ij}=k$ if and only if $(i,j,k)\in I$). For $n=1,2,3$, all Latin squares of order $n$ are equivalent (up to isomorphism of $K_n^3$). For $n=4,5$ there are exactly two such equivalence classes. % This raises the question of the existence of silver cubes with prespecified diagonals. For $n=4$, we see that the colouring of $K_4^3$ shown in Figure~\ref{fig-4cube} is silver with respect to two inequivalent diagonals, one indicated by a gray shade and the other by circles. % In Figures~\ref{fig-5cube-bc} and~\ref{fig-5cube-other} we present two silver $(5,3)$-cubes with respect to the two inequivalent diagonals of $K_5^3$. These silver cubes were found with the aid of Proposition~\ref{prop-reduction} and by using graph colouring programs of~\cite{culberson}. \begin{figure}[ht] \begin{center} \includegraphics[width=9cm]{fig-51.mps} \end{center} \caption{A silver $(5,3)$-cube with respect to the back-circulant diagonal~$I_0$.} \label{fig-5cube-bc} \end{figure} \begin{figure}[ht] \begin{center} \includegraphics[width=9cm]{fig-52.mps} \end{center} \caption{A silver $(5,3)$-cube with respect to a diagonal inequivalent to~$I_0$. } \label{fig-5cube-other} \end{figure} %The following is the smallest undecided case of the silver $3$-cube problem. A silver $(7,3)$-cube with respect to a back-circulant diagonal was found by Ventullo and Khodkar \cite{VK} during the revision of this paper. These examples and Theorem~\ref{thm-product} imply the following. \begin{cor} %There exists a silver $(n,3)$-cube for every positive side length $n$ %having no prime factor greater than $7$. The $(n,3)$-cube is silver for every positive side length $n$ having no prime factor greater than $7$. \end{cor} We do not know whether a silver $(11,3)$-cube exists. \begin{conj} The $(n,3)$-cube is silver for every side length $n \ge 1$, and with respect to any diagonal of $K_n^3$. \end{conj} %but it is reasonable to conjecture that a silver $(n,3)$-cube %exists for any side length $n \ge 1$, and with respect to %any diagonal of $K_n^3$. The following proof of Theorem~\ref{thm-product} is a straightforward generalization of the doubling construction discussed above. We partition the vertices of $G=K_{mn}^d$ into $m^d$ blocks of size $n^d$ indexed by the vertices of~$K_m^d$ and then colour the blocks according to the given silver cubes. %\begin{proof}[Proof of Theorem~\ref{thm-product}.] %This looks wierd \noindent\textit{Proof of Theorem~\ref{thm-product}.} %This hack is better We assume here that the vertex set of a complete graph $K_t$ is $\{0,1,\dots,t-1\}$. Let $G=K_{mn}^d$. For every $\mathbf{v}=v_1v_2\cdots v_d\in V(K_m^d)$ we let % \[ T_\mathbf{v}=\{x_1x_2\cdots x_d\in V(G)\suchthat nv_i\le x_i (d-1)(n-1). \end{cases} \] % We now define a colouring $D:V(G)\to \{1,2,\dots,d(nm-1)+1\}$. Given $\mathbf{x}\in V(G)$ with $\idx(\mathbf{x})=\mathbf{v}$, let % \begin{equation} \label{Ddef} D(\mathbf{x})=\begin{cases} A_\mathbf{v}(\,\varphi(\bf x)\,) & \text{if } \mathbf{v}\in J\\ C_\mathbf{v}(\,\varphi(\bf x)\,) & \text{if } \mathbf{v}\not\in J. \end{cases} \end{equation} % We claim that $D$ is a silver colouring of~$G$ with respect to the diagonal % \[ K=\bigcup_{\mathbf{v}\in J}\varphi_\mathbf{v}^{-1}(I). \] % To prove the claim, let $\mathbf{x}\in K$, $\mathbf{v}=\idx(\mathbf{x})$, and let $N[\mathbf{v}]$ be the closed neighbourhood of $\mathbf{v}$ in $K_m^d$. Then $\mathbf{v}\in J$ and $\varphi_\mathbf{v}(\mathbf{x})\in I$. For every $\mathbf{v}'\in N[\mathbf{v}]$ let $X_{\mathbf{v}'}=N_{G}[\mathbf{x}]\cap T_{\mathbf{v}'}$. By the definition we have % \[ D(X_{\mathbf{v}'})=\{nB(\mathbf{v}')+(d-1)(n-1)+i\suchthat 1\le i\le n\} \] % for $\mathbf{v}'\not=\mathbf{v}$, and % \[ D(X_\mathbf{v})= \{1,2,\ldots,(d-1)(n-1)\}\cup\{nB(\mathbf{v})+(d-1)(n-1)+i\suchthat 1\le i\le n\}. \] % Now since $\mathbf{v}\in J$, we have $\{B(\mathbf{v}')\suchthat \mathbf{v}'\in N[\mathbf{v}]\}=\{0,1,\ldots,d(m-1)\}$, thus % \[ D(N_G[\mathbf{x}])=\bigcup_{\mathbf{v}'\in N[\mathbf{v}]}D(X_{\mathbf{v}'})= \{1,2,\ldots,d(mn-1)+1\}. \] % Therefore $\mathbf{x}$ is rainbow with respect to~$D$. \qed %\end{proof} %Not needed with above hack \begin{rem} \rm The diagonal $K$ defined in the above proof is the (generalized) Kronecker product of $I$ and $J$. That is, $\mathbf x \in K$ if and only if, as vectors, $\mathbf x = \mathbf w + n\mathbf v$ for some $\mathbf w \in I$ and some $\mathbf v \in J$. Therefore $K$ is not necessarily equivalent to a back-circulant even if both $I$ and $J$ are back-circulants. \end{rem} \begin{rem} \rm The above proof remains valid if just before \eqref{Ddef}, for each $\mathbf{v}\in J$ we select an automorphism $\sigma_{\mathbf v}$ of $K_n^d$ and modify both $A_\mathbf{v}$ and its diagonal through the action of $\sigma_{\mathbf v}$. In this way we can obtain colourings $D$ which are silver with respect to inequivalent diagonals of $K_{mn}^d$. \end{rem} %\begin{rem} %If, in the above proof, we identify the diagonals $I$, $J$ and $K$ with their %$\{0,1\}$-characteristic cubes, then we have $K=I\otimes J$ where %`$\otimes$' is the Kronecker product. Therefore even if $I$ and $J$ are %both back-circulant, $K$ is not necessarily equivalent to the back-circulant %diagonal of $K_{mn}^d$. %\end{rem} % %\begin{rem} %The above proof remains valid if, for each $\mathbf{v}\in J$, %we independently apply an automorphism of $K_n^d$ to $A_\mathbf{v}$. %In this way different diagonals %$K$ of $K_{mn}^d$ can be obtained. %\end{rem} %\begin{cor} %For all nonnegative integers $r$, $s$ and $t$, %a silver $3$-cube of side %$2^r3^s5^t$ exists. %\end{cor} \section{Desarguesian silver cubes}\label{sec-q2} \label{sec-q} In this section we consider the question: for which pairs $(n,d)$ is $K_n^d$ totally silver? We first give a necessary condition, then we show that this necessary condition is sufficient when $n$ is a prime power by constructing a totally silver colouring. The construction uses perfect linear codes with suitable parameters. Finally, we use these totally silver colourings to construct some other silver cubes. % \begin{prop} \label{prop:totSilverArith} If $G$ is $r$-regular, then in every totally silver colouring of~$G$, each colour appears exactly $\frac{|V(G)|}{r+1}$ times. In particular, if a totally silver $(n,d)$-cube exists, then $n^d$ is divisible by $d(n-1)+1$. \end{prop} \begin{proof} Let $c$ be a totally silver colouring of $G$ and let $i$ be a colour. We count in two ways the pairs $(\mathbf{v},\mathbf{v}')$ where $\mathbf{v}\in V(G)$, $\mathbf{v}'\in N[\mathbf{v}]$ and $c(\mathbf{v}')=i$. Each $\mathbf{v}\in V(G)$ contributes one to the count, whereas each vertex $\mathbf{v}' \in c^{-1}(i)$ contributes $r+1$ to the count. Therefore $|V(G)| = (r+1) \, |c^{-1}(i)|$. \qed \end{proof} \begin{thm} \label{thm:projConstr} Let $q$ be a prime power. Then $K^d_q$ is totally silver if and only if $d = \frac{q^s-1}{q-1}$ for some positive integer $s$. \end{thm} \begin{proof} \newcommand{\spanof}[1]{\langle #1\rangle} Let $q=p^t$ where $p$ is a prime and $t$ a positive integer. Suppose $K^d_q$ has a totally silver colouring. By Proposition~\ref{prop:totSilverArith}, $d(p^t-1)+1$ divides $p^{td}$, so $d = \frac{p^k-1}{p^t-1} $ for some positive integer $k$, $t\le k\le td$. Since $d$ is an integer we have, by an elementary argument, that $t$ divides $k$. Therefore $d = \frac{q^s-1}{q-1}$ for some positive integer~$s$. For the converse, we note that for $d = \frac{q^s-1}{q-1}$, there exists a perfect linear code of length $d$ with minimum distance~$3$, namely the $(d,d-s)$~Hamming %code over $\F_q$~\cite[p. 193]{MS}. %code over $\F_q$~\cite[Ch.~7, \S 3]{MS}. code over $\F_q$~\cite[p.~191]{MS}. A totally silver colouring of $K_q^d$ is defined by cosets of such a code. Since each coset is a code of distance at least~$3$, the closed neighbourhood of each vertex intersects each coset in at most (hence exactly) one vertex. Therefore this colouring is totally silver. \qed \end{proof} Theorems~\ref{thm-product} and~\ref{thm:projConstr} give the following. \begin{cor} Let $q$ be a prime power and let $s\ge 0$, $t \ge 1$ be integers. Then a silver $(q^s,\frac{q^t-1}{q-1})$-cube exists. \end{cor} Starting with the construction of the proof of Theorem~\ref{thm:projConstr}, we may produce silver cubes of ``affine'' dimension. These cubes are not totally silver. \begin{thm} Let $q$ be a prime power and $s\ge 1$. Then there exists a silver $(q,q^{s})$-cube with respect to the back-circulant diagonal~$I_0$, such that all vertices in ~$I_0$ receive the same colour. \label{thm-qtos} \end{thm} % \begin{proof} Let $F = \F_q$ be a field of order $q$. Let $d = \frac{q^{s}-1}{q-1}$. By Theorem~\ref{thm:projConstr}, the graph $H=K_q^d$ has a totally silver colouring $c:V(H)\to\{1,2,\ldots,q^{s}\}$. Again we have identified $V(H)$ with the vector space $F^d$. Let $G=K_{q}^{q^{s}}$ where $V(G) = F^{q^s}$. Since %$q^{s} = (q-1)\frac{q^{s}-1}{q-1}+1$ $q^s = (q-1)d+1$, we may partition the coordinates of vectors $\mathbf{v} \in V(G)$ according to the pattern \[\mathbf{v} = (v_1,v_2,\dots ,v_{q^s}) =(\mathbf{x}_1,\mathbf{x}_2,\dots ,\mathbf{x}_{q-1},b)\] where $b \in F$ and each $\mathbf{x}_i \in V(H)$. We define two linear functions on $V(G)$, $\omega:V(G) \rightarrow F$ and $\mathbf{u}:V(G) \rightarrow V(H)$ by \begin{align*} \omega(\mathbf{v}) &= v_1+v_2+\cdots+v_{q^s} \\ \mathbf{u}(\mathbf{v}) &= \alpha_1\mathbf{x}_1+\alpha_2\mathbf{x}_2+\cdots +\alpha_{q-1}\mathbf{x}_{q-1}. \end{align*} Here $\{\alpha_1,\ldots,\alpha_{q-1}\}$ is an arbitrary fixed enumeration of $F^*=F\setminus\{0\}$. We aim to show that the function %\[\psi:V(G)\to\{\infty\}\cup(\{1,2,\ldots,q^{s}\}\times F^{*})\] \[A:V(G)\to\{\infty\}\cup(\{1,2,\ldots,q^{s}\}\times F^{*})\] % \[ %\psi(\mathbf{v})=\begin{cases} A(\mathbf{v})=\begin{cases} \infty&\text{if }\omega(\mathbf{v})=0\\ [\;c(\mathbf{u}(\mathbf{v}))\,,\;\omega(\mathbf{v})\;]&\text{if }\omega(\mathbf{v})\not=0 \end{cases} \] is a silver colouring of $G$ with respect to the back-circulant diagonal $I_0 = \{\mathbf{v}\in V(G) \suchthat \omega(\mathbf{v})=0\}$. % Let $\mathbf{v} \in V(G)\setminus I_0$ and $\mathbf{v'}\in V(G)$ be two vertices of~$G$ which differ in either one or two coordinates. Suppose, for contradiction, that %$\psi(\mathbf{v}) = \psi(\mathbf{v'})$. $A(\mathbf{v}) = A(\mathbf{v'})$. We immediately deduce $\mathbf{v'} \in V(G)\setminus I_0$, so \[ \omega(\mathbf{v}) = \omega(\mathbf{v'}) \qquad\text{and}\qquad c(\mathbf{u}(\mathbf{v})) = c(\mathbf{u}(\mathbf{v'})). \] Now $\mathbf{u}(\mathbf{v})$ and $\mathbf{u}(\mathbf{v'})$ are vertices of $H$ which are at distance at most $2$ in~$H$. As $c$ is a totally silver colouring of~$H$, the second equation implies % $\mathbf{u}(\mathbf{v}) = \mathbf{u}(\mathbf{v'})$. We define $ \mathbf{w} = (w_1, w_2,\dots, w_{q^s}) = \mathbf{v} - \mathbf{v'}$. The vector $\mathbf{w}$ has one or two nonzero entries, and satisfies \[ \omega(\mathbf{w}) = 0 \qquad \text{and} \qquad \mathbf{u}(\mathbf{w}) = (0,0,\dots,0). \] The first equation implies that $\mathbf{w}$ has exactly two nonzero entries, $w_k$, $w_\ell$, which satisfy \begin{equation} \label{eq-first} w_k + w_\ell = 0. \end{equation} The second equation implies that $1 \le k, \ell \le q^s-1$, and that $k-\ell$ is an integer multiple of %$\frac{q^s-1}{q-1}$. $d$. In particular, there exist field elements $\alpha_i$, $\alpha_j$ such that \[ \alpha_i w_k + \alpha_j w_\ell =0. \] Comparing with \eqref{eq-first}, we conclude that $\alpha_i = \alpha_j$. Therefore $k=\ell$, a contradiction. We conclude that %$\psi$ $A$ is a silver colouring with respect to $I_0$. \qed \end{proof} Applying Theorem~\ref{thm-product} gives the following. \begin{cor} Let $p$ be a prime and $s,t\ge 0$. Then a silver $(p^s,p^t)$-cube exists. \end{cor} \section{Hypercubes and binary codes} \label{sec-hypercube} Silver $(2,d)$-cubes are of special interest since $K_2^d$ is the hypercube~$Q_d$. Here we find some nonexistence results, a relationship to general binary codes, and we propose some conjectures. It is proved in~\cite{Wan} (see also \cite[Eq.~(2)]{KDP}) that $\chi(Q_d^{(2)})=d+1$ when $d+1$ is a power of~$2$. %In other words when $d+1$ is a power of~$2$, the hypercube $Q_d$ is totally silver. So by Proposition~\ref{prop-G2}, the hypercube $Q_d$ is totally silver when $d+1$ is a power of $2$. Zhou~\cite[Cor.~2.6]{Zhou1} extends this result by showing that every Cayley graph of degree $2^t-1$ and having a transitive Abelian group of automorphisms is totally silver. % From Theorems~\ref{thm:projConstr} and~\ref{thm-qtos} we have the following. % \begin{cor} \label{cor-2-tot} For all $t\ge 0$, the hypercube $Q_{2^t}$ is silver and the hypercube $Q_{2^{t+1}-1}$ is totally silver. \label{cor-totallysilverhypercube} \end{cor} Note that since $Q_d$ is bipartite, it has only two diagonals, namely its partite sets. The set of all vertices with even (resp.\ odd) Hamming weight is called the even (resp. odd) diagonal and denoted by~$I_0$ (resp.~$I_1$). In this section we present some nonexistence results for silver hypercubes. \begin{lem} If $d$ is odd, then every silver colouring of $Q_d$ is totally silver. \label{lem-oddsilverhypercube} \end{lem} % \begin{proof} Let $c:V(Q_d)\to\{0,1,\ldots,d\}$ be a silver colouring of $Q_d$ with respect to the diagonal $I$, and let $\mathbf{w}\not\in I$. We may assume $c(\mathbf{w})=0$. We aim to show $\mathbf{w}$ is rainbow with respect to~$c$. Let $G$ be the complete graph on the vertex set $\{1,2,\ldots,d\}$. We define the colourings $\psi_0:V(G)\to\{0,1,\ldots,d\}$ and $\psi_1:E(G)\to\{0,1,\ldots,d\}$ as follows. For every $i\in V(G)$, let $\mathbf{w}_i$ be the vertex of $Q_d$ obtained from $\mathbf{w}$ by flipping the $i$th coordinate and define $\psi_0(i)=c(\mathbf{w}_i)$. Note for every $i\in V(G)$ we have $\mathbf{w}_i\in I$. For each edge $e=\{i,j\}$ of $G$ let $\mathbf{w}_{ij}$ be the vertex of $Q_d$ obtained from $\mathbf{w}$ by flipping the $i$th and the $j$th coordinates and define $\psi_1(e)=c(\mathbf{w}_{ij})$. It remains to show $\psi_0$ is a proper vertex colouring of~$G$. We prove this in the following steps: % \begin{itemize} % \item For every $i$, we have $\psi_0(i)\not=0$ since $\mathbf{w}_i$ is adjacent to $\mathbf{w}$. %%----------------------------------- \item For every $e=\{i,j\}\in E(G)$, $\mathbf{w}$ and $\mathbf{w}_{ij}$ are both adjacent to the rainbow vertex $\mathbf{w}_i$. Thus $\psi_1(e)=c(\mathbf{w}_{ij})\not=c(\mathbf{w})=0$. %%----------------------------------- \item Let $e=\{i,j\}$ and $e'=\{i,k\}$ be adjacent edges of $G$. Since $\mathbf{w}_{ij}$ and $\mathbf{w}_{ik}$ are both adjacent to the rainbow vertex $\mathbf{w}_i$, we have $\psi_1(e)=c(\mathbf{w}_{ij})\not=c(\mathbf{w}_{ik})=\psi_1(e')$. Therefore $\psi_1$ is a proper edge $d$-colouring of $G$. %%----------------------------------- \item For every $i\in V(G)$ and $e=\{i,j\}\in E(G)$, since $\mathbf{w}_i$ and $\mathbf{w}_{ij}$ are adjacent in $Q_d$ we have $\psi_0(i)\not=\psi_1(e)$. Now since $\psi_1$ is a proper edge colouring of $G$, $\psi_0(i)$ is the unique element of $\{1,2,\ldots,d\}$ which is not in $\{\psi_1(e)\suchthat e\ \mbox{is adjacent to}\ i\}$. %%----------------------------------- \item Since $d$ is odd, every colour class $\psi_1^{-1}(k)$, $k \in \{1,2,\dots,d\}$, is a matching of size $\frac{d-1}2$ in~$G$. The unique vertex of $G$ which is unsaturated in this matching must receive colour $k$ in $\psi_0$. Therefore $\psi_0$ is a proper vertex colouring of~$G$. \qed \end{itemize} % \end{proof} We can now give a characterization of silver hypercubes of odd dimension. \begin{thm} If $d$ is odd then $Q_d$ is silver if and only if $d=2^{t}-1$ for some $t\ge 1$. \label{thm-totallysilverhypercube} \end{thm} % \begin{proof} By Corollary~\ref{cor-totallysilverhypercube} if $d=2^{t}-1$ for some $t\ge 1$, then $Q_d$ is totally silver. On the other hand if $d$ is odd and $Q_d$ is silver, then $Q_d$ is totally silver by Lemma~\ref{lem-oddsilverhypercube}. Now by Proposition~\ref{prop:totSilverArith}, $(d+1)\lvert 2^d$, thus $d+1$ is a power of~$2$. \qed \end{proof} Silver hypercubes of even dimension are more difficult to characterize. Although we do not have a complete characterization, we can obtain nonexistence results using bounds from coding theory. Let $G_d=\red(Q_d,I_1)$, as defined in Section~\ref{sec-notation}. Note that $V(G_d)=I_0$ is the set of words in $\{0,1\}^d$ having even Hamming weight. Two vertices of $G_d$ are adjacent if they have Hamming distance~$2$. Any two elements of an independent set $I$ of $G_d$ have Hamming distance at least~$4$. By suppressing a parity-check bit, we obtain from $I$ a corresponding binary code of length~$d-1$ and distance at least~$3$. This correspondence is bijective, therefore the maximum size of an independent set in $G_d$ equals $A(d-1,3)$. Here $A(d-1,3)$ is a \b{standard} notation for the maximum size of a general binary code of length~$d-1$ and distance~$3$. By Proposition~\ref{prop-reduction}, a silver colouring of $Q_d$ with respect to the diagonal $I_1$ corresponds to a partition of the vertices of $G_d$ into $d+1$ independent sets, and this corresponds to a partition of $\{0,1\}^{d-1}$ into binary codes of size at most~$A(d-1,3)$. We have proved the following. \begin{prop} If $Q_d$ is silver then $A(d-1,3)\ge\frac{2^{d-1}}{d+1}$. \label{prop-Ad3bound} \end{prop} The following result is attributed to R.\,J.~McEliece in~\cite[p.~545, Problem~(22)]{MS}. %in~\cite[Ch.~17, \S4, Problem (22)]{MS}. \begin{thm} If $d=4k+2$ for some $k\ge 1$, then $A(d-1,3)\le\frac{2^{d-1}}{d+2}$. \label{thm-McEliece} \end{thm} \begin{cor} If $d=4k+2$ for some $k\ge 1$, then $Q_d$ is not silver. \label{cor-Q4tplus2} \end{cor} In~\cite{A-11-3} it is shown that $A(11,3)=144$. Since $144<\frac{2^{11}}{13}$, Proposition~\ref{prop-Ad3bound} gives the following. \begin{cor} The hypercube $Q_{12}$ is not silver. \label{cor-Q12} \end{cor} In light of the above, we propose the following. \begin{conj} The hypercube $Q_d$ is silver if and only if $d=2^{t}-1$ or $d=2^{t}$ for some~$t\ge 0$. \label{conj-hypercube} \end{conj} %In view of Theorem~\ref{thm-totallysilverhypercube} and %Corollaries~\ref{cor-totallysilverhypercube}, \ref{cor-Q4tplus2} %and~\ref{cor-Q12}, it remains to settle the conjecture for %$d=4k$ where $k\ge 5$ and $k$ is not a power of~$2$. %We propose the following conjecture %regarding the size of general binary codes with minimum distance~$3$. \begin{conj} If $d$ is not a power of $2$, then $A(d-1,3)\le\frac{2^{d-1}}{d+1}$. \label{conj-coding} \end{conj} Conjecture~\ref{conj-coding} is stronger than Conjecture~\ref{conj-hypercube} by way of Corollary~\ref{cor-totallysilverhypercube}, Theorem~\ref{thm-totallysilverhypercube} and Proposition~\ref{prop-Ad3bound}. %An affirmative answer to this conjecture, would imply %Conjecture~\ref{conj-hypercube} by way of %Theorem~\ref{thm-totallysilverhypercube} and Proposition~\ref{prop-Ad3bound}. Conjecture~\ref{conj-coding} is affirmed in case $d$ is odd \cite[Proposition~3.1]{BHOS98}, and in the case $d\equiv 2$ modulo~$4$, by Theorem~\ref{thm-McEliece}. % Conjecture~\ref{conj-coding} also holds when Since $A(11,3)=144$, this conjecture also holds for $d=12$. %In the following we show that Conjecture~\ref{conj-coding} holds for odd~$d$. % %\begin{thm} {\em %\cite[Proposition~3.1]{BHOS98}} %If $d$ is odd, then $A(d-1,3)\le\frac{2^{d-1}}{d+1}$. %\end{thm} % %Note that equality holds in Conjecture~\ref{conj-coding} if and %only if $d+1$ is a power of~$2$. Hamming codes over $\F_2$ are perfect, so $A(d-1,3) = \frac{2^{d-1}}{d}$ when $d$ is a power of~$2$. %Based on the above results, the %Therefore the smallest $d$ for which Conjecture~\ref{conj-coding} is open is~$d=20$. Therefore it remains to settle Conjectures \ref{conj-coding} and \ref{conj-hypercube} for $d=4k$ where $k\ge 5$ and $k$ is not a power of~$2$. \section{Defining sets in graph colouring}\label{sec-defset} Let $c$ be a proper $k$-colouring of a graph $G$ %Let $G$ be a graph, $c$ a $k$-colouring of $G$ and let~$S\subseteq V(G)$. If $c$ is the only extension of $c\vert_S$ to a proper $k$-colouring of $G$, then $S$ is a \emph{defining set of~$c$}. The minimum size of a defining set among all $k$-colourings of $G$ is denoted by~$\defnum(G,k)$. The study of $\defnum(G,k)$ is nontrivial only for $\chi(G)\le k\le\Delta(G)+1$, since $\defnum(G,k)$ is not defined for $k<\chi(G)$, and since $\defnum(G,k)=|V(G)|$ when $k > \Delta(G)+1$. The case $k=\chi(G)$ is studied in~\cite{MNZ}. A more general survey of defining sets in combinatorics appears in~\cite{DefiningSetSurvey}. We show here %In the following a relationship between $\defnum(G,\Delta(G)+1)$ where $G=K_n^d$ and the existence of silver $(n,d)$-cubes. \begin{lem} {\em \cite{IMO97}} Let $S$ be a defining set of an $(r+1)$-colouring $c$ of an $r$-regular graph $G$. Then the complement of $S$ is an independent set in $G$. \label{lem-defset-indep} \end{lem} \begin{thm} A silver cube of side $n$ and dimension $d$ exists if and only if % \[ \defnum(K_n^d,d(n-1)+1)=n^d-n^{d-1}.\vspace{-2em} \] \label{thm-silver-cube-defnum} \end{thm} \begin{proof} The case $d=2$ of this argument appears in \cite{IMO97}. Let $c$ be a silver colouring with respect to a diagonal $I$ of $K_n^d$. Then the set $S$ of non-diagonal vertices is a defining set of $c$. Conversely, let $c$ be a proper $(d(n-1)+1)$-colouring of $K_n^d$ which admits a defining set $S$ of size $n^d - n^{d-1}$. By the above lemma, $V(K_n^d)\setminus S$ is an independent set of $K_n^d$. This independent set has cardinality $n^{d-1}$, so $V(K_n^d) \setminus S$ is a diagonal of $K_n^d$. %Thus For every $x\in V(K_n^d)\setminus S$, we have $\lvert c(N(x))\rvert=d(n-1)$. Therefore every $x\not\in S$ is rainbow with respect to~$c$. \qed \end{proof} Theorem~\ref{thm-silver-cube-defnum} and Lemma~\ref{lem-defset-indep} serve to further justify our choice of the definition of ``diagonal'' that we use in this paper. \begin{acknowledgement} We thank Mahdad Khatirinejad for referring us to Theorem~\ref{thm-McEliece}. \end{acknowledgement} \begin{thebibliography}{99} % % BibTeX users please use % and use \bibitem to create references. % %\bibitem{RefJ} % Format for Journal Reference %Author, Journal \textbf{Volume,} (year) page numbers. % Format for books %\bibitem{RefB} %Author, \textit{Book title} (Publisher, place year) page numbers % etc \bibitem{BHOS98} A.~E. Brouwer, H.~O. H{\"a}m{\"a}l{\"a}inen, P.~R.~J. {\"O}sterg{\aa}rd, N.~J.~A. Sloane, Bounds on mixed binary/ternary codes, IEEE Trans. Inform. Theory \textbf{44,} (1998) 140--161. \bibitem{culberson} J.~Culberson, \verb@http://web.cs.ualberta.ca/~joe/Coloring/@. \bibitem{DefiningSetSurvey} D.~Donovan, E.~S. Mahmoodian, C.~Ramsay, A.~P. Street, Defining sets in combinatorics: a survey, in \textit{Surveys in combinatorics, 2003 (Bangor)}, (Cambridge Univ. Press, Cambridge, 2003) London Math. Soc. Lecture Note Ser. \textbf{307,} 115--174. \bibitem{MR1605684} T.~W. Haynes, S.~T. Hedetniemi, P.~J. Slater, \textit{Fundamentals of domination in graphs}, (Marcel Dekker, New York, 1998). \bibitem{KDP} D.~S.~Kim, D.-Z.~Du, P.~Pardalos, A coloring problem on the $n$-cube Discrete Appl. Math. \textbf{103,} (2000) 307--311. \bibitem{MS} F.~J. MacWilliams, N.~J.~A. Sloane, \textit{The theory of error-correcting codes}, (North-Holland Publishing Co., Amsterdam, 1977). \bibitem{IMO97} M.~Mahdian, E.~S. Mahmoodian, The roots of an {IMO}97 problem, Bull. Inst. Combin. Appl. \textbf{28,} (2000) 48--54. \bibitem{MNZ} E.~S. Mahmoodian, R.~Naserasr, M.~Zaker, Defining sets in vertex colorings of graphs and Latin rectangles, 15th British Combinatorial Conference (Stirling, 1995). Discrete Math. \textbf{167/168,} (1997) 451--460. \bibitem{A-11-3} P.~R.~J.~{\"O}sterg{\aa}rd, T.~Baicheva, E.~Kolev, Optimal binary one-error-correcting codes of length $10$ have $72$ codewords, IEEE Trans. Inform. Theory \textbf{45,} (1999) 1229--1231. \bibitem{VK} K.~Ventullo, A.~Khodkar, A three dimensional silver cube of order seven, Bull.~Inst.~Combin.~Appl. (to appear). \bibitem{Wan} P. J. Wan, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network, J. Comb. Optim. \textbf{1,} (1997) 179--186. \bibitem{Zhou1} S.~Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Discrete Math. \textbf{19,} (2005) 985--1003. \bibitem{Zhou2} S.~Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theoret. Comput. Sci. \textbf{310,} (2004) 501--511. \end{thebibliography} \end{document} % end of file template.tex