= Connected vertex cover
A <vertex cover> $C$ whose induced <subgraph> $G[C]$ is connected. The optimization problem minimizes $|C|$ subject to both conditions. A <graph> with edges in two distinct <connected components of a graph> has no connected vertex cover: covering each of these <edges> requires selected <vertices> in different components. Isolated <vertices> can be ignored when exactly one component contains all the <edges>. The edge-free case depends on whether the empty solution is admitted.
Back to article page
