## Abstract

The Shannon capacity of a graph G is c(G) = sup_{d≥1}(α(G^{d})) ^{1/d}, where α(G) is the independence number of G. The Shannon capacity of the Kneser graph KG_{n,r} was determined by Lová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, KG_{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}) ≥ 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.

Original language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 20 |

Issue number | 2 |

Publication status | Published - May 17 2013 |

## Keywords

- Cube packing
- Shannon capacity
- Tabu search
- Zero-error capacity

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics