Covering (graph theory)

In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph.

We are especially interested in finding small sets with this property. The problem of finding the smallest vertex covering is called the vertex cover problem and is NP-complete.

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

Definition

A vertex covering for a graph <math>G<math> is a set of vertices <math>V<math> so that every edge of <math>G<math> is adjacent to at least one vertex in <math>V<math>. The minimum vertex covering the smallest vertex cover. We say <math>V<math> covers the edges of the graph. The vertex covering number <math>\omega_V(G)<math> for a graph <math>G<math> is the size of the minimum vertex covering

An edge covering for a graph <math>G<math> is a set of edges <math>E<math> so that every vertex of <math>G<math> is adjacent to at least one edge in <math>E<math>. The minimum edge covering the smallest edge cover. We say <math>E<math> covers the vertices of the graph. The edge covering number <math>\omega_E(G)<math> for a graph <math>G<math> is the size of the minimum edge covering.

When speaking about covering we usually refer to vertex covering.

Examples

• For any graph <math>G<math> the set of its vertices (edges) is trivially a vertex covering (edge covering)
• A complete bipartite graph <math>G_{m,n}<math> has <math>\omega_V(G_{m,n})=\min\lbrace m,n \rbrace<math> and <math>\omega_E(G_{m,n})=\max \lbrace m,n \rbrace<math>

Properties

• For any graph <math>G:=(V,E)<math> : <math>\omega_V(G)<math> + maximum independent-set = <math>\|V\|<math> (Tibor Gallai 1959)

References

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