# edge covering

Let $G$ be a graph. An edge covering $C$ on $G$ is a subset of the vertices of $G$ such that each edge in $G$ is incident with at least one vertex in $C$.

For any graph, the vertex set is a trivial edge covering. Generally, we are more interested in minimal coverings. A minimal edge covering is simply an edge covering of the least possible .

Title edge covering EdgeCovering 2013-03-22 12:40:02 2013-03-22 12:40:02 vampyr (22) vampyr (22) 8 vampyr (22) Definition msc 05C70 Matching minimal edge covering