This MedLibrary.org supplementary page on Edge covering number is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:
Related Sponsors
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.
Contents |
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 τ 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 Km,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.
Wikipedia content modification information:
- This page was last modified on 3 August 2008, at 21:31.
Wikipedia Authorship and Review
Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.
Wikipedia Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Edge covering number".
The URL for this specific entry is:
All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.