Cycles within specified distance from each vertex. (Q1427481): Difference between revisions

Let \(f\) be a nonnegative integer-valued function defined on the vertex set of a graph \(G\). A cycle \(C\) in \(G\) is an \(f\)-dominating cycle if for each vertex \(x\) of \(G\), \(d_G(x,C) \leq f(x)\), where \(d\) is the distance function. A set \(S\) of vertices is \(f\)-stable if \(d_G(u,v) \geq f(u)+f(v)\) for any distinct vertices \(u\) and \(v\) of \(S\). Now let \(G\) be a \(k\)-connected graph (\(k \geq 2\)). If the largest \(f+1\)-stable set is no larger than \(k\), the authors show that \(G\) has an \(f\)-dominating cycle. Here \((f+1)(v)=f(v)+1\). This theorem generalizes results by Chvátal-Erdős on dominating cycles and results by Dirac on cycles through specified vertices.