Minimum Edge Cover Task
Jump to navigation
Jump to search
A Minimum Edge Cover Task is an Edge Covering Task that produces a minimum edge cover for a graph.
- See: Edge Cover, Covering Task, Edge Covering.
References
2012
- http://mathworld.wolfram.com/MinimumEdgeCover.html
- A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of of a minimum edge cover of a graph is known as the edge cover number of G and is denoted rho(G).
A minimum edge cover of a graph can be computed in Mathematica with FindEdgeCover[g]. There is currently no Mathematica function to compute all minimum edge covers of a graph.
If a graph G has no isolated points, then :</math>\nu(G)+\rho(G)=|G|,</math> where nu(G) is the matching number and n=|G| is the vertex count of G
- A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of of a minimum edge cover of a graph is known as the edge cover number of G and is denoted rho(G).
2000
- (West, 2000).
1959
- (Gallai, 1959).