Title :
A nontrivial lower bound on the Shannon capacities of the complements of odd cycles
Author :
Bohman, Tom ; Holzman, Ron
Author_Institution :
Dept. of Math. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
fDate :
3/1/2003 12:00:00 AM
Abstract :
This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that α(C~2n+3(2n))≥2(2n)+1. It follows that for n≥0 we have Θ(C~2n+3)>2, where Θ(G) denotes the Shannon (1956) capacity of graph G.
Keywords :
channel capacity; graph theory; Shannon capacities; memoryless communication channel; nontrivial lower bound; odd cycle complements; Communication channels; Information theory; Mathematics; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2002.808128
