A Remark on \(q\)-Dominating Cycles

Lutz Volkmann1
1 Lehrstuhl II fir Mathematik, RWTH Aachen, 52056 Aachen, Germany

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 \geq 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.