% 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}

  
