On the Independence Numbers of the Cubes of Odd Cycles

Tom Bohman, Ron Holzman, Venkatesh Natarajan

Abstract


We give an upper bound on the independence number of the cube of the odd cycle $C_{8n+5}$. The best known lower bound is conjectured to be the truth; we prove the conjecture in the case $8n+5$ prime and, within $2$, for general $n$.

Keywords


Graph power; Shannon capacity; Odd Cycles; Independence number

Full Text: PDF