A cycle $C$ in a connected graph $G$ is called *dominating* if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 ([Disc. Math. v.43, 281-96](http://dx.doi.org/10.1016/0012-365X(83)90165-6)) a general result that in particular implies that a connected $2K\_2$-free $G$ (i.e. $G$ does not contain a induced subgraph which is the disjoint union of two edges) admits such a cycle, unless $G$ is a tree (in the latter case the cycle collapses to a vertex or to an edge). His proof is not algorithmic. 


In fact, it's not hard to give an efficient algorithm for finding such a cycle in a connected $2K\_2$-free $G$. Is this known? (It could be an exercise in a book, if you ask me). Also, I wonder if more general statements from [loc.cit.] are known to allow efficient algorithmic versions. 



finding dominating cycles in $2K_2$-free graphs
We have written our argument up here: <https://arxiv.org/abs/1412.0514>


