Induced Subgraphs of the Power of a Cycle

Abstract

In this article, it is shown that if G is an induced subgraph of the dth power of a cycle of length n, and G has minimum degree $d + k$, then G has at least $[ (d + k)/2d ]n$ vertices. This answers a problem of Kézdy.