Minimum Edge Cover Task

From GM-RKB
(Redirected from Minimum Edge Covering 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.



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

2000

  • (West, 2000).

1959

  • (Gallai, 1959).