Covering (graph theory)

Covering (graph theory)

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 au 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Covering graph — In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Intersection number (graph theory) — In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover… …   Wikipedia

  • Independent set (graph theory) — The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices …   Wikipedia

  • König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia

  • Covering — may refer to: Mathematics In topology: Covering map, a function from one space to another with uniform local neighborhoods Cover (topology), a system of (usually, open or closed) sets whose union is a given topological space Lebesgue covering… …   Wikipedia

  • Covering space — A covering map satisfies the local triviality condition. Intuitively, such maps locally project a stack of pancakes above an open region, U, onto U. In mathematics, more specifically algebraic topology, a covering map is a continuous surjective… …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Graph property — In graph theory a graph property is any inherently graph theoretical property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”