TOPICS
Search

Minimum Edge Cover

A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of G and is denoted rho(G).

Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.

Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).

A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.

If a graph G has no isolated points, then

nu(G)+rho(G)=|G|,

where nu(G) is the matching number and n=|G| is the vertex count of G (Gallai 1959, West 2000).

See also

Edge Cover, Minimal Edge Cover

Explore with Wolfram|Alpha

References

Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 178, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Cite this as:

Weisstein, Eric W. "Minimum Edge Cover." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimumEdgeCover.html

Subject classifications