A Remark on $q$-Dominating Cycles

Abstract

A cycle $C$ of a graph $G$ is called a $q$-dominating cycle if every vertex of $G$ which is not contained in $C$ is adjacent to at least $q$ vertices of $C$. Let $G$ be a $k$-connected graph with $k\ge 2$. We present a sufficient condition, in terms of the degree sum of $k+1$ independent vertices, for $G$ to have a $qg$-dominating cycle. This is an extension of a 1987 result by J.A. Bondy and G. Fan. Furthermore, examples will show that the given condition is best possible.