= Independent vertex cover
An <independent vertex cover> is a <vertex cover> that is also an <independent set>. Its complement is an <independent set> as well, since the cover condition forbids <edges> entirely in that complement. Thus such a cover is a side of a <bipartition> of the <graph>. This standard definition is stronger than <independent dominating set> on <graphs> without <isolated vertices>, and remains a different notion when <isolated vertices> are present. In a nonempty <simple graph>, two possibly repeated witnesses $x,y$ with $\neg E(x,y)$ and no <edge> outside $\{x,y\}$ express existence of an <independent vertex cover> of size at most two.
Back to article page
