In the mathematical discipline of graph theory, a covering (or cover) of a graph is a set of vertices (or edges) such that each edge (vertex) of the graph touches (is incident with) at least one element of the set.

It is of mathematical interest to find small coverings of graphs. The problem of finding the smallest vertex covering is called the vertex cover problem and is NP-complete.

Coverings with vertices and edges are related to independent sets and matchings, respectively.

Definition

A vertex covering of a graph G is a set of vertices V such that each edge of G is incident with at least one vertex in V. The set V is said to cover the edges of G. A minimum vertex covering is a vertex covering of smallest possible size. The vertex covering number $tau$ is the size of a minimum vertex covering.

Dually, an edge covering of a graph G is a set of edges E such that each vertex is incident with at least one edge in E, with comparable concepts of covering the vertices of G, minimum edge covering, and edge covering number Ω_E(G).

The term covering more frequently refers to a vertex covering rather than an edge covering.

Examples

• The vertex set of a graph covers its edge set, and in a graph with no degree-0 vertices, vice versa.
• The complete bipartite graph K_m,n has vertex covering number min(m, n) and edge covering number max(m, n).

Properties

• The number of vertices of a graph is equal to its vertex covering number plus the size of a maximum independent set (Gallai 1959).

References

• Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.