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. Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ...
A graph diagram of a graph with 6 vertices and 7 edges. ...
A graph with 6 vertices (nodes) and 7 edges. ...
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. In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karps 21 NP-complete problems. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
Coverings with vertices and edges are closely related to independent sets and matchings. In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ...
Dheeraj Gedam This article is about mathematical matchings. ...
## Definition
A **vertex covering** for a graph *G* is a set of vertices *V* so that every edge of *G* is adjacent to at least one vertex in *V*. The **minimum vertex covering** the smallest vertex cover. We say *V* *covers* the edges of the graph. The **vertex covering number** ω_{V}(*G*) for a graph *G* is the size of the minimum vertex covering This article just presents the basic definitions. ...
This article just presents the basic definitions. ...
A graph with 6 vertices (nodes) and 7 edges. ...
An **edge covering** for a graph *G* is a set of edges *E* so that every vertex of *G* is adjacent to at least one edge in *E*. The **minimum edge covering** the smallest edge cover. We say *E* *covers* the vertices of the graph. The **edge covering number** ω_{E}(*G*) for a graph *G* is the size of the minimum edge covering. When speaking about **covering** we usually refer to vertex covering.
## Examples - For any graph
*G* the set of its vertices (edges) is trivially a vertex covering (edge covering) - A complete bipartite graph
*G*_{m,n} has ω_{V}(*G*_{m,n}) = min{*m*,*n*} and ω_{E}(*G*_{m,n}) = max{*m*,*n*} In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ...
## Properties In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ...
Tibor Gallai (1912–1992) was a Hungarian mathematician. ...
## References - Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math.
**2**, 133-138, 1959. |