FindEdgeCover

FindEdgeCover[g]
finds an edge cover of the graph g with a minimum number of edges.

DetailsDetails

  • An edge cover is a set of edges that is incident to every vertex.
  • FindEdgeCover returns a list of edges.
  • FindEdgeCover will return an empty list if no edge cover is found.
  • FindEdgeCover works with undirected graphs, directed graphs, weighted graphs, multigraphs and mixed graphs.

Background
Background

  • FindEdgeCover finds a single minimum edge cover of a graph and returns the result as an edge list. Here, an edge cover is a set of edges for which at least one edge endpoint is incident to every vertex in a graph. A minimum edge cover is an edge cover having the smallest possible number of edges. Minimum edge covers have applications in social networks, biology, and social sciences.
  • The size of (i.e. the number of edges in) a minimum edge cover of a graph is known as its edge cover number and is denoted . An edge cover can be found in polynomial time.
  • EdgeCoverQ can be used to test if a given edge set is a (not necessarily minimum) edge cover. Application of EdgeCoverQ to all possible edge subsets of a graph can therefore be used to enumerate all edge covers, and application to subsets of size equal to the edge cover number can be used to enumerate all minimum edge covers. FindVertexCover applies the same concept to vertices.
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)