EdgeCoverQ

EdgeCoverQ[g,elist]

yields True if the edge list elist is an edge cover of the graph g and False otherwise.

Details

  • An edge cover is a set of edges that is incident to every vertex.
  • EdgeCoverQ works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Background & Context

  • EdgeCoverQ checks if a given edge list is an edge cover of a given graph. An edge cover is a set of graph edges that are incident to every vertex of a graph (i.e. their endpoints "cover" the vertices of the graph). Edge covers have applications in social networks, biology, and social sciences.
  • An edge cover having the smallest possible number of edges for a given graph is known as a minimum edge cover and can be found using FindEdgeCover. Application of EdgeCoverQ to all possible edge subsets of a graph can be used to enumerate all edge covers, and application to subsets of size equal to that of the smallest edge cover can be used to enumerate all minimum edge covers.
  • VertexCoverQ applies the analogous concept to vertices.

Examples

open allclose all

Basic Examples  (2)

Test whether a set of edges is an edge cover of a complete graph:

Not all sets of edges are edge covers in a graph:

Scope  (6)

Test undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

EdgeCoverQ gives False for expressions that are not graphs:

EdgeCoverQ works with large graphs:

Applications  (2)

Enumerate all edge covers:

Enumerate all subsets of edges and select the covers:

Highlight covers:

Enumerate all minimal edge covers:

Find the length of a minimal edge cover:

Enumerate all edge subsets of length 3 and select the covers:

Highlight minimal covers:

Properties & Relations  (4)

For a graph without isolated vertices, the EdgeList is an edge cover:

A smallest edge cover can be found using FindEdgeCover:

The complete bipartite graph has edge cover of size :

For a connected graph, the total size of an independent edge set and an edge cover equals the number of vertices:

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

Text

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

CMS

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

APA

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

BibTeX

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

BibLaTeX

@online{reference.wolfram_2024_edgecoverq, organization={Wolfram Research}, title={EdgeCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/EdgeCoverQ.html}, note=[Accessed: 18-November-2024 ]}