A sufficient condition for dominating cycles (Q1096645)

A cycle C of G is called a dominating cycle if every vertex of G is adjacent to at least one vector of C. Let \(R_ m(v)=\{u\in V(G):\) \(d(u,v)\leq m\}\). A cycle is called an m-dominating cycle if \(R_ m(v)\cap V(C)\geq n-2k\). \textit{B. N. Clark, C. J. Colbourn} and \textit{P. Erdős} [A conjecture on dominating cycles, Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf. Boca Raton/Fla. 1985, Congr. Numerantium 47, 189-197 (1985; Zbl 0622.05042)] conjectured: for a k- connected graph, \(k\geq 2\), on n vertices, if every \(k+1\) independent vertices \(x_ i\) (0\(\leq i\leq k)\) with \(R_ m(x_ i)\cap R_ m(x_ j)=\phi\) (0\(\leq i\neq j\leq k)\) satisfy the inequality \(\sum^{k}_{i=0}| R_ m(x_ i)| \geq n-2k\), then G has an m- dominating cycle. In this article the authors prove the conjecture in the case \(m=1\) and give an example showing that n-2k cannot be replace with n-2k-1. They also point out that \textit{P. Fraisse} \([D_{\lambda}\)-cycles and their applications for Hamiltonian graphs, preprint] has independently proved the conjecture in this case.