FindEdgeCover

FindEdgeCover[g]

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

FindEdgeCover[{vw,…}]

uses rules vw to specify the graph g.

Details

  • 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 & Context

  • 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.

Examples

open allclose all

Basic Examples  (1)

Find an edge cover:

Show the cover:

Scope  (8)

FindEdgeCover works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

FindEdgeCover returns an empty result when no edge cover exists:

FindEdgeCover works with large graphs:

Properties & Relations  (5)

The edges in an edge cover are incident to every vertex:

Test whether a set of edges is an edge cover using EdgeCoverQ:

For a connected graph, the sum of the size of an independent edge set and an edge cover equals the vertex count:

The complete bipartite graph has edge covering number :

An edge cover of a StarGraph includes all its edges:

Wolfram Research (2010), FindEdgeCover, Wolfram Language function, https://reference.wolfram.com/language/ref/FindEdgeCover.html (updated 2015).

Text

Wolfram Research (2010), FindEdgeCover, Wolfram Language function, https://reference.wolfram.com/language/ref/FindEdgeCover.html (updated 2015).

CMS

Wolfram Language. 2010. "FindEdgeCover." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindEdgeCover.html.

APA

Wolfram Language. (2010). FindEdgeCover. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindEdgeCover.html

BibTeX

@misc{reference.wolfram_2024_findedgecover, author="Wolfram Research", title="{FindEdgeCover}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindEdgeCover.html}", note=[Accessed: 15-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findedgecover, organization={Wolfram Research}, title={FindEdgeCover}, year={2015}, url={https://reference.wolfram.com/language/ref/FindEdgeCover.html}, note=[Accessed: 15-November-2024 ]}