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 incidentPlanetmathPlanetmathPlanetmath 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
Canonical name EdgeCovering
Date of creation 2013-03-22 12:40:02
Last modified on 2013-03-22 12:40:02
Owner vampyr (22)
Last modified by vampyr (22)
Numerical id 8
Author vampyr (22)
Entry type Definition
Classification msc 05C70
Related topic Matching
Defines minimal edge covering