  We consider a graphical approach to index coding. While cycles have been
shown to provide coding gain, only disjoint cycles and cliques (a specific type
of overlapping cycles) have been exploited in existing literature. In this
paper, we define a more general form of overlapping cycles, called the
interlinked-cycle (IC) structure, that generalizes cycles and cliques. We
propose a scheme, called the interlinked-cycle-cover (ICC) scheme, that
leverages IC structures in digraphs to construct scalar linear index codes. We
characterize a class of infinitely many digraphs where our proposed scheme is
optimal over all linear and non-linear index codes. Consequently, for this
class of digraphs, we indirectly prove that scalar linear index codes are
optimal. Furthermore, we show that the ICC scheme can outperform all existing
graph-based schemes (including partial-clique-cover and
fractional-local-chromatic number schemes), and a random-coding scheme (namely,
composite coding) for certain graphs.
