On the Shannon capacity of triangular graphs

K. Ashik Mathew, Patric R.J. Östergård, Alexandru Popa

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The Shannon capacity of a graph G is c(G) = supd≥1(α(Gd)) 1/d, where α(G) is the independence number of G. The Shannon capacity of the Kneser graph KGn,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, KGn,2, is also called the triangular graph Tn. The graph Tn has the n-cycle Cn as an induced subgraph, whereby c(Tn) ≥ c(Cn), 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(Tn) obtained in this work include.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Issue number2
Publication statusPublished - May 17 2013


  • 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

Fingerprint Dive into the research topics of 'On the Shannon capacity of triangular graphs'. Together they form a unique fingerprint.

Cite this