2
$\begingroup$

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) 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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Where, by the "complement" of a cycle $C$ in a graph $G$, you really mean the graph $G-V(C)$. Did I guess right? $\endgroup$
    – bof
    Commented Dec 17, 2014 at 21:04
  • $\begingroup$ sure, that is right. $\endgroup$
    – Dima Pasechnik
    Commented Dec 17, 2014 at 21:06

1 Answer 1

Reset to default
0
$\begingroup$

We have written our argument up here: https://arxiv.org/abs/1412.0514

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .