FACTOID # 29: 73.3% of America's gross operating surplus in motion picture and sound recording industries comes from California.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

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

## Contents

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 Gm,n has ωV(Gm,n) = min{m,n} and ωE(Gm,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.

Results from FactBites:

 Graph Clustering for Very Large Topic Maps (3396 words) The sequence 1,a,2,b,3,c,4 is a path of length 3 of the graph in figureFigure 2. The graph in figureFigure 4 is a spanning tree of the graph in figureFigure 2. We saw in the section presenting the graph theory that a hypergraph can be represented by a graph whose set of vertices is the union of the vertices and the hyperedges' sets of the hypergraph, and the set of edges is defined by the relation of incidence between vertices and hyperedges of the hypergraph.
 DIMACS Workshop on Geometric Graph Theory (5604 words) Graphs with a cyclic ordering on the vertices are known as `convex geometric graphs'; they model the combinatorial structure of systems of sides and diagonals in a convex polygon, and can thus be interpreted as geometric graphs whose vertex set is in convex position. A geometric graph is a graph drawn in the plane with straight line segments as edges connecting vertices that are assumed to be in general position. The fundamental question of extremal graph theory is to determine the maximum number ex(n, H) of edges in an H-free graph on n vertices, where H is a class of so-called forbidden subgraphs.
More results at FactBites »

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Press Releases |  Feeds | Contact