Covering (graph theory)
From Wikipedia, the free encyclopedia
In the mathematical discipline of graph theory, a covering (or cover) of a graph is a set of vertices (or edges) such that the elements of the set are close (incident) to all edges (or vertices) of the graph.
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 closely related to independent sets and matchings.
Contents |
[edit] Definition
A vertex covering for 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 ΩV(G) is the size of a minimum vertex covering.
Dually, an edge covering for a graph G is a set of edges E such that each vertex is incident with at least one edge in E. The set E is said to cover the vertices of the graph. A minimum edge covering is an edge covering of smallest possible size. The edge covering number ΩE(G) is the size of a minimum edge covering.
The term covering more frequently refers to a vertex covering rather than an edge covering.
[edit] Examples
- The vertex set of a graph covers its edge set, and in a graph with degree-0 vertices, vice versa.
- The complete bipartite graph Km,n has vertex covering number min(m, n) and edge covering number max(m, n).
[edit] 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).
[edit] References
- Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.
