% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P27}{20(2)}{2013} \usepackage{amsmath} \usepackage{algorithmic} \usepackage{algorithm} \usepackage{amssymb} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{claim}{Claim} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \newenvironment{Proof}{\noindent\emph{Proof}}{\qed\medskip} \newcommand{\kg}[2]{\ensuremath{\mathrm{KG}_{#1,#2}}} \newcommand{\kgc}[2]{\ensuremath{\overline{\mathrm{KG}}_{#1,#2}}} \newcommand{\qed}{\hfill \ensuremath{\Box}} \usepackage{array} \usepackage{calc} \usepackage{enumerate} \newlength\celldim \newlength\fontheight \newlength\extraheight \newcounter{sqcolumns} \newcolumntype{S}{ @{} >{\centering \rule[-0.5\extraheight]{0pt}{\fontheight + \extraheight}% \begin{minipage}{\celldim}\centering} p{\celldim} <{\end{minipage}} @{} } \newcolumntype{Z}{ @{} >{\centering} p{\celldim} @{} } \newenvironment{squarecells}[1] {\setlength\celldim{2em}% \settoheight\fontheight{A}% \setlength\extraheight{\celldim - \fontheight}% \setcounter{sqcolumns}{#1 - 1}% \begin{tabular}{|S|*{\value{sqcolumns}}{Z|}}\hline} % squarecells tabular goes here {\end{tabular}} \newcommand\nl{\tabularnewline\hline} \begin{document} \title{On the Shannon Capacity of Triangular Graphs} \author{K Ashik Mathew\thanks{This work was supported in part by the Academy of Finland, Grant Number 132122.}\\ \and Patric R. J. \"{O}sterg\r{a}rd \and Alexandru Popa\\ \small Department of Communications and Networking, \\[-0.8ex] \small Aalto University School of Electrical Engineering, P.O.\ Box 13000\\[-0.8ex] \small 00076 Aalto, Finland\\ \small\tt \{ashik.kizhakkepallathu,patric.ostergard,alexandru.popa\}@aalto.fi } \renewcommand\footnotemark{} \date{\dateline{Mar 19, 2013}{Apr 29, 2013}{May 9, 2013}} \maketitle \begin{abstract} The Shannon capacity of a graph $G$ is %defined as $c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$ where $\alpha(G)$ is the independence number of $G$. The Shannon capacity of the Kneser graph $\kg{n}{r}$ was determined by Lov\'{a}sz in 1979, but little is known about the Shannon capacity of the complement of that graph when $r$ does not divide $n$. The complement of the Kneser graph, $\kgc{n}{2}$, is also called the triangular graph $T_n$. The graph $T_n$ has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(T_n) \geq c(C_n)$, and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discrete $d$-dimensional torus of width $n$ using two types of $d$-dimensional cubes of width $2$. Bounds on $c(T_n)$ obtained in this work include $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$. \end{abstract} Keywords: cube packing, Shannon capacity, tabu search, zero-error capacity \section{Introduction} \label{sec:intro} The Shannon capacity of a graph plays a central role in the study of the zero-error capacity of noisy communication channels \cite{KO98}. The \emph{Shannon capacity} of a graph $G$ is defined as $$c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$$ where $\alpha(G)$ is the independence number of $G$ and the graph strong product is assumed \cite{S56}. The problem of determining the Shannon capacity can be very challenging already for small graphs. In his celebrated paper of 1979, Lov\'{a}sz~\cite{Lova1979} proved that $c(C_5)=\sqrt 5$, where $C_n$ denotes the cycle with $n$ vertices, but the cases of $C_n$ with $n \geq 7$ and odd are still open \cite{Bohmanlimit1}. Lov\'{a}sz \cite{Lova1979} also determined the Shannon capacity of Kneser graphs. The \emph{Kneser graph} $\kg{n}{k}$ consists of one vertex for each $k$-element subset of an \mbox{$n$-set,} any two vertices being adjacent exactly when the corresponding subsets are disjoint. Specifically, $$c(\kg{n}{r})=\binom{n-1}{r-1}.$$ Also the Shannon capacity of the complement of the aforementioned graphs has been studied. The graph $\kgc{n}{2}$, which is the line graph of the complete graph $K_n$, is known as the \emph{triangular graph} and denoted by $T_n$. In fact, the problem of determining $c(C_n)$ and $c(T_n)$ are closely connected via the following two versions of a combinatorial packing problem \cite{brsch-hypergraphs}: Determining $\alpha(C_n^d)$ is equivalent to finding the largest packing of $d$-dimensional cubes of width $2$ in the $d$-dimensional discrete torus of width $n$. Determining $\alpha(T_n^d)$ is equivalent to finding the largest packing of \mbox{$d$-dimensional} cubes of width $2$ in the $d$-dimensional discrete torus of width $n$, where the sides of the cubes may consist of two unconnected parts of width 1. In the latter case, it does not matter whether one talks about a packing in a torus or a cube. That version can also be formulated as a packing problem in complete $d$-partite hypergraphs with $n$ vertices in each partite set \cite{brsch-hypergraphs}. Also note that the former version is a special case of the latter; indeed, $C_n$ is an induced subgraph of $T_n$. Optimal packings of the two types in the 2-dimensional torus of width 5 are shown in Fig.~\ref{fig:pack}. \begin{figure}[htbp] \begin{center} \begin{squarecells}{5} 1 & 1 & & 5 & 5 \nl 1 & 1 & 2 & 2 & \nl 3 & & 2 & 2 & 3 \nl 3 & 4 & 4 & & 3 \nl & 4 & 4 & 5 & 5 \nl \end{squarecells} \hspace*{5mm} \begin{squarecells}{5} 5 & & 2 & 2 & 5 \nl & 1 & 2 & 2 & 1 \nl 4 & 3 & 3 & 4 & \nl 4 & 1 & & 4 & 1 \nl 5 & 3 & 3 & & 5 \nl \end{squarecells} \end{center} \caption{Packing a torus with connected and unconnected cubes} \label{fig:pack} \end{figure} The problem of determining $\alpha(G^d)$ was studied in \cite{Baumertpacking} with $G = C_n$ for general values and specific small values of $n$ odd and $d$. A similar study will be carried out in the current paper when $G = T_n$. We start off in Section~\ref{sec:prel} by considering various analytical bounds, and thereafter discuss two computational methods based on local and exhaustive search. In particular, it is shown that $\alpha({T_5}^4) = 27$. Variants of the problems considered in this paper are discussed in Section~\ref{sec:otheratt}, and the new results obtained are presented in tables in Section~\ref{sec:results}. Among other things it is shown that $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$. \section{Bounds on Packings} \label{sec:prel} \subsection{Basic Bounds} In the study of $c(T_n)$, we define $H(d,n)$ (resp.\ $G(d,n)$) to be the number of $d$-dimensional unconnected (resp.\ connected) cubes of width $2$ that can be packed into the \mbox{$d$-dimensional} torus of width $n$. We define $G(0,n) = H(0,n) = 1$ for all $n \geq 2$. Obviously, $G(d,n) \leq H(d,n)$ and $c(T_n) \geq \sqrt[d]{H(d,n)}$. Moreover, $H(d,n) = (n/2)^d$ when $n$ is even, so we restrict to the case of $n$ odd in the sequel. For $d=1$ and $d=2$, the values of $H(d,n)$ are known \mbox{\cite[p.~42]{brsch-hypergraphs}}. \vspace{1mm} \begin{theorem} \label{thm:one} $H(1,n) = \left\lfloor \frac{n}{2} \right\rfloor$. \end{theorem} \vspace{0mm} \begin{theorem} \label{thm:two} $H(2,n) = \left\lfloor \frac{n}{2} \left\lfloor \frac{n}{2} \right\rfloor \right\rfloor$. \end{theorem} \vspace{1mm} The following two theorems give further bounds in the general case. The proofs are analogous to those for corresponding results on $G(d,n)$ in \cite[Lemmata 1 \& 2]{Baumertpacking}. \vspace{1mm} \begin{theorem} \label{thm:add} $H(d_1+d_2,n) \geq H(d_1,n)H(d_2,n)$. \end{theorem} \vspace{0mm} \begin{theorem} \label{thm:plusone} $H(d+1,n) \leq \left\lfloor \frac{n}{2}H(d,n) \right\rfloor$. \end{theorem} Using Theorems \ref{thm:one} and \ref{thm:plusone} we get that $H(d, n)\leq (\frac{n}{2})^d$, which further leads to the upper bound $c(T_n)\leq \frac{n}{2}$. This bound can also be obtained using techniques from \cite{Lova1979}. \vspace{1mm} The following theorem is proved by a construction that is not applicable to the case of $G(n,d)$. \vspace{1mm} \begin{theorem} \label{thm:new} $H(d,n+2) \geq \sum_{i=0}^{d}\binom{d}{i}H(i,n)$. \end{theorem} \vspace{1mm} \begin{Proof} Partition the coordinate values in each dimension of the torus into $A$ and $B$, where $|A|=n$ and $|B|=2$, and require that a side of a cube is either entirely in $A$ or in $B$. This divides the packing problem into subcases, which can be solved independently. If the number of dimensions with values in $A$ is $i$, then the instance to be solved is that of $H(i,n)$. Summing over all cases and recalling that $H(0,n)=1$ gives the result. \end{Proof} \subsection{Upper Bounds via Tabu Search} \label{sec:compmeth} Packings of cubes provide lower bounds on $G(d,n)$ and $H(d,n)$. We here use \emph{tabu search}, a stochastic local search method, in the search for good packings. Tabu search was introduced in 1986 by Glover and McMillan \cite{GloverM86}; for a more extensive treatment of the method, see \cite{TabuUG1993, hertz1991, TabuIndSet1990}. Two different frameworks can be used to search for the packings considered here. Either one may search for independent sets in certain graphs, or one may search for packings of cubes in a torus. We have chosen the latter approach, and run Algorithm~\ref{algorithm:ours} with an input of the number of cubes to pack, $k$, the dimension of the torus, $d$, and the width of the torus, $n$. The algorithm is restarted if it does not find a packing within a given time limit. \begin{algorithm}[H] \caption{$\mathit{Search}(k,d,n)$} \begin{algorithmic}[1] \STATE Generate a random packing $\mathcal{P}$ with $k$ cubes \WHILE{$\mathit{Overlap}(\mathcal{P}) > 0$} \STATE $\mathit{MinOverlap}\leftarrow \infty$ \FORALL{$\mathcal{P}'\in \mathit{Neighbourhood}(\mathcal{P})$} \IF{$\mathit{Overlap}(\mathcal{P}') \leq \mathit{MinOverlap}$ \& $!\mathit{Tabu}(\mathcal{P}')$} \STATE $\mathit{MinOverlap}\leftarrow \mathit{Overlap}(\mathcal{P}')$ \IF{$\mathit{Overlap}(\mathcal{P}') < \mathit{MinOverlap}$} \STATE $\mathit{BestNeighbour}\leftarrow \{\mathcal{P}'\}$ \ELSE \STATE $\mathit{BestNeighbour}\leftarrow \mathit{BestNeighbour} \cup \{\mathcal{P}'\}$ \ENDIF \ENDIF \ENDFOR \STATE $\mathcal{P}\leftarrow \mathit{RandomChoice(\mathit{BestNeighbour})}$ \STATE Update tabu list \ENDWHILE \end{algorithmic} \label{algorithm:ours} \end{algorithm} In Algorithm~\ref{algorithm:ours}, a \emph{solution} is a set of $k$ cubes. The function $Overlap(\mathcal{P})$ gives the total pairwise overlap of all cubes in a solution $\mathcal{P}$. We further define the neighborhood of a solution as the set of solutions that can be reached by replacing any one of the cubes in the solution by any other possible cube. Since there are $\binom{n}{2}^d$ possible cubes, the neighborhood has size $k\binom{n}{2}^d$. The tabu list is implemented in such a way that a new cube in the solution may not be part of the next $T$ changes, where typically $T \leq 10$. Using Algorithm~\ref{algorithm:ours}, we were able to find a packing proving that $H(3,7) \geq 35$ (which, in fact, coincides with the best known upper bound and is therefore the exact value of $H(3,7)$). Another result obtained by Algorithm~\ref{algorithm:ours} is $H(3,13) \geq 248$. To obtain that result we did not start the search from a random packing but from a packing attaining $G(3,13) \geq 247$ and described in \cite[Theorem 6]{Baumertpacking}, with one additional random cube. %Also this packing is listed in the (separately downloadable) Appendix. \subsection{Bounds via Exhaustive Search} Exhaustive computer search can be used to find and prove optimality of combinatorial objects. We shall here illustrate how exhaustive search can be used to prove $H(4,5)=27$, improving on the earlier result of $25\leq H(4,5) \leq 29$ obtained by Brouwer and Schrijver \cite{brsch-hypergraphs}. The concept of symmetry plays a central role in the study of combinatorial objects. We say that two packings of unconnected cubes are \emph{isomorphic} if one can be obtained from the other by a permutation of the sides of the cubes together with permutations of the $n$ coordinate values for each side. A mapping of this type from a packing onto itself is an \emph{automorphism}, and the set of all automorphisms of a packing forms a group, the \emph{automorphism group} of the packing. To determine whether packings are isomorphic and to find the automorphism group, we transform packings into graphs and use the graph isomorphism program \emph{nauty} \cite{Nau90}. The mapping is as follows: Suppose that the packing has $k$ unconnected cubes $\{C_1,C_2,\ldots,C_k\}$, where the cube $C_i$ is presented as $\{a_{i,1,0},a_{i,1,1}\} \times \{a_{i,2,0},a_{i,2,1}\} \times \cdots \times \{a_{i,d,0},a_{i,d,1}\}$ with $0\leq a_{i,j,k} \leq n-1$. Corresponding to such a packing we generate a graph with vertex set $V_0\cup V_1\cup V_2 \cup \cdots \cup V_d$, where $V_0 = \{v^0_1, v^0_2,\ldots,v^0_k\}$ and $V_i = \{v^i_0, v^i_1,\ldots,v^i_{n-1}\}$ for $1 \leq i \leq d$. For any $i$, $1\leq i\leq k$ and $j$, $1 \leq j \leq d$, we add edges $\{v^0_i,v^j_{a_{i,j,0}}\}$ and $\{v^0_i,v^j_{a_{i,j,1}}\}$. Moreover, edges are added so that for every $i$, $1 \leq i \leq d$, the subgraph induced by $V_i$ is complete. As the problem of finding packings of cubes can be phrased in the framework of finding independent sets (or cliques) in a particular graph, the \emph{Cliquer} software \cite{cliquerweb} can be used to settle small instances. In this way, a total of $864000$ different packings attending $H(3,5)=12$ can be found. However, there are only 2 isomorphism classes of such packings. %which are listed in the Appendix. The automorphism groups of these packings have orders 16 and 48, and the result can be validated by the orbit-stabilizer theorem as \[ \frac{3!(5!)^3}{16}+\frac{3!(5!)^3}{48}=864000. \] \begin{theorem} \label{thm:27} $H(4,5)=27$. \end{theorem} \begin{Proof} Assume that $H(4,5) \geq 28$. The proof of Theorem~\ref{thm:plusone}, which shows that $H(3,5) \geq 12$, relies on the fact that we get five 3-dimensional packings for the five different possibilities of fixing one dimension and at least one of these packings must be of size at least $\lceil 28\cdot 2/5\rceil = 12$. Assume that there is a packing of the $4$-dimensional torus of width $5$ with 28 unconnected cubes of side $2$. Without loss of generality, we may fix the value of of the first dimension to 0 and use one of the two nonisomorphic solutions attaining $H(3,5)=12$. Out of the $5\cdot 864000$ possibilities for fixing and placing a 3-dimensional packing of size 12 in the second dimension, only $4320$ coincide in the 2-dimensional intersection of the 3-dimensional subcubes. Cliquer is finally used to try to extend the 4320 cases to a packing with 28 unconnected cubes of side 2. No solutions are found, implying that $H(4,5) < 28$. Several packings of size 27 were found. %one of which is listed in the Appendix. So $H(4,5) = 27$. \end{Proof} \section{Variants of the Problem} \label{sec:otheratt} The width of any torus considered so far in this paper is the same in all dimensions. Obviously, one can generalize this setting and consider tori with non-uniform widths. The widths of the cubes to be packed may as well be non-uniform and differ from 2. Beineke \cite{BeinekeSurvey69} proved that the maximum number of unconnected $k \times l$ cubes (the direction of which matters) that can be packed in an $m \times n$ torus is $$\min\left\{\left\lfloor\frac{m}{k}\left\lfloor\frac{n}{l}\right\rfloor\right\rfloor, \left\lfloor\frac{n}{l}\left\lfloor\frac{m}{k}\right\rfloor\right\rfloor\right\}.$$ Indeed, packings of $4\times 2$ cubes in the $n \times n$ torus play a central role in \cite[Theorem 6]{Baumertpacking}. Results for higher dimension and various situations can be found in \cite{StrongProduct1974, V98}. A further study of these cases might lead to results that could improve Theorems~\ref{thm:new}. One may also consider covering versions of all these packing problems, cf.\ \cite{OR03}. \section{Results} \label{sec:results} Best known bounds on $H(d,n)$ for $1 \leq d \leq 4$ and $5 \leq n \leq 21$ odd are shown in Table~\ref{tab:bounds} (trivially $H(d,1) = 0$ and $H(d,3) = 1$ for any $d$). The exact values for $d=1$ and $d=2$ follow from Theorems~\ref{thm:one} and \ref{thm:two}, respectively, and are left unmarked. Only one key is shown for bounds that can be obtained in several ways. Packings attaining $H(3,5)=12$, $H(3,7) = 35$, $H(3,13) \geq 248$, and $H(4,5)=27$ are provided electronically in a supplementary file. For comparison, a table of best known bounds on $G(d,n)$ for $1 \leq d \leq 5$ and $5 \leq n \leq 21$ odd are shown in Table~\ref{tab:boundsg}. In this table, only the bounds that have been improved since \cite{Baumertpacking} have a key. \vspace{3mm} \noindent Key to Tables \ref{tab:bounds} and \ref{tab:boundsg}.\\ \begin{tabular}{ll} %\multicolumn{2}{@{}l}{Unmarked bounds are from Theorems \ref{thm:one} and \ref{thm:two}.}\\ %\multicolumn{2}{@{}l}{Bounds:}\\ $^a$ & Brouwer and Schrijver \cite{brsch-hypergraphs}\\ $^b$ & Vesel and \v{Z}erovnik \cite{VZ02}\\ $^c$ & Baumert \emph{et al.} \cite{Baumertpacking}\\ $^d$ & Natarajan \cite{nat-thesis}\\ $^e$ & Bohman, Holzman, and Natarajan \cite{Bohman1}\\ %$^f$ & $G(d,n) \leq 5^{d/2}$ \cite{Lova1979}\\ %$^p$ & Theorem~\ref{thm:add}\\ $^q$ & Theorem~\ref{thm:plusone}\\ $^r$ & Theorem~\ref{thm:new}\\ $^s$ & Tabu search, see supplementary file\\ $^t$ & Exhaustive search, Theorem~\ref{thm:27} and supplementary file\\ %\multicolumn{2}{@{}l}{Upper bounds:}\\ \end{tabular} %\vspace{5mm} \begin{table}[htb] \begin{center} \caption{Bounds on $H(d,n)$ for $1 \leq d \leq 4$ and $5 \leq n \leq 21$} \label{tab:bounds} \begin{tabular}{ccccc}\\\hline $n\backslash d$&1&2&3&4\\ \hline $5$ & $2$ & $5$ & $^a12^a$ & $^t27^t$\\% &$^r60$--$62^q$\\ $7$ & $3$ &$10$ & $^s35^q$ & $^r114$--$122^q$\\ $9$ & $4$ &$18$ & $^c81^q$ & $^r327$--$364^q$\\ $11$ & $5$ &$27$ & $^c148^q$ & $^r776$--$814^q$\\ $13$ & $6$ &$39$ & $^s248$--$253^q$ & $^r1551$--$1644^q$\\ $15$ & $7$ &$52$ & $^r384$--$390^q$ &$^r2802$--$2925^q$\\ $17$ & $8$ &$68$ & $^c578^q$ & $^c4913^q$\\ $19$ & $9$ &$85$ & $^c807^q$ & $^c7666^q$\\ $21$ & $10$ &$105$ &$^d1092$--$1102$ &$^r11441$--$11571^q$\\\hline \end{tabular} \end{center} \end{table} \begin{table}[htb] \begin{center} \caption{Bounds on $G(d,n)$ for $1 \leq d \leq 4$ and $5 \leq n \leq 21$} \label{tab:boundsg} \begin{tabular}{ccccc}\\\hline $n\backslash d$&1&2&3&4\\ \hline $5$ & $2$ & $5$ & $10$ & $25$\\% & $50$--$55^f$\\ $7$ & $3$ &$10$ & $33$ & $^b108$--$115$\\ $9$ & $4$ &$18$ & $81$ & $324$--$363$\\ $11$ & $5$ &$27$ & $148$ & $740$--$814$\\ $13$ & $6$ &$39$ & $247^e$ & $1521$--$1605$\\ $15$ & $7$ &$52$ & $380$--$390$ & $2704$--$2925$\\ $17$ & $8$ &$68$ & $578$ & $4913$\\ $19$ & $9$ &$85$ & $807$ & $7666$\\ $21$ & $10$ &$105$ & $1092^d$ &$11025$--$11466^c$\\\hline \end{tabular} \end{center} \end{table} \vspace{5mm} The new results in the current work lead to several new bounds on the Shannon capacity of $T_n$. %\vspace{5mm} \begin{theorem} $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$. \end{theorem} %\subsection*{Acknowledgements} % %The authors thank the referee for pointing out the connection between %Kneser graphs and triangular graphs. % %\section*{References} %\vspace{1cm} \begin{thebibliography}{19} \bibitem{Baumertpacking} L. D. Baumert, R. J. McEliece, E. Rodemich, H. C. Rumsey Jr., R. Stanley, and H. Taylor, A combinatorial packing problem, In: Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970, Computers in Algebra and Number Theory, G. Birkhoff and M. Hall Jr. (Eds.), Amer. Math. Soc., Providence, 1971, pp. 97--108. \bibitem{BeinekeSurvey69} L. W. Beineke, A survey of packings and coverings of graphs, In: The Many Facets of Graph Theory, G. Chartrand, S. Kapoor (Eds.), volume 110 of Lecture Notes in Mathematics, Springer Berlin, 1969, pp. 45--53. \bibitem{Bohmanlimit1} T. Bohman, A limit theorem for the Shannon capacities of odd cycles I, Proc. Amer. Math. Soc. 131 (2003) 3559--3569. \bibitem{Bohman1} T. Bohman, R. Holzman, V. Natarajan, On the independence numbers of the cubes of odd cycles, preprint. \bibitem{brsch-hypergraphs} A. E. Brouwer, A. Schrijver, Uniform hypergraphs, In: Packing and Covering in Combinatorics, A. Schrijver (Ed.), Math. Centre Tracts No. 106, Mathematisch Centrum, Amsterdam, 1979, pp. 39--73. \bibitem{TabuIndSet1990} C. Friden, A. Hertz, D. de Werra, Tabaris: an exact algorithm based on tabu search for finding a maximum independent set in a graph, Comput. Oper. Res. 17 (1990) 437--445. \bibitem{GloverM86} F. Glover, C. McMillan, The general employee scheduling problem: an integration of MS and AI, Comput. Oper. Res. 13 (1986) 563--573. \bibitem{TabuUG1993} F. Glover, E. Taillard, D. de Werra, A user's guide to tabu search, Ann. Oper. Res. 41 (1993) 3--28. \bibitem{hertz1991} A. Hertz, Tabu search for large scale timetabling problems, European J. Oper. Res. 54 (1991) 39--47. \bibitem{KO98} J. K\"orner, A. Orlitsky, Zero-error information theory, IEEE Trans. Inform. Theory 44 (1998) 2207--2229. \bibitem{Lova1979} L. Lov{\'a}sz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1--7. \bibitem{Nau90} B. D. McKay, nauty User's Guide (version 1.5), Technical report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990. \bibitem{nat-thesis} V. Natarajan, Independent Sets in Powers of Odd Cycles and the Global Min-Cut Problem, Ph.D. thesis, Carnegie-Mellon University, 2007. \bibitem{cliquerweb} S. Niskanen, P. R. J. \"{O}sterg\r{a}rd, Cliquer User's Guide (version 1.0), Technical report T48, Commun. Lab., Helsinki Univ. Technol., Espoo, 2003. \bibitem{OR03} P. R. J. \"{O}sterg\r{a}rd, T. Riihonen, A covering problem for tori, Ann. Comb. 7 (2003) 357--363. \bibitem{S56} C. E. Shannon, The zero-error capacity of a noisy channel, IRE Trans. Inform. Theory 2 (1956) 8--19. \bibitem{StrongProduct1974} E. Sonnemann, O. Krafft, Independence numbers of product graphs, J. Combin. Theory Ser. B 17 (1974) 133--142. \bibitem{V98} A. Vesel, The independence number of the strong product of cycles, Comput. Math. Appl. 36, no.7 (1998) 9--21. \bibitem{VZ02} A. Vesel, J. \v{Z}erovnik, Improved lower bound on the Shannon capacity of $C_7$, Inform. Process. Lett. 81 (2002) 277--282. \end{thebibliography} \end{document}