yields True if the edge list elist is an edge cover of the graph g and False otherwise.
- 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.
Examplesopen allclose all
Basic Examples (2)
EdgeCoverQ gives False for expressions that are not graphs:
EdgeCoverQ works with large graphs:
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).
Wolfram Language. 2010. "EdgeCoverQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/EdgeCoverQ.html.
Wolfram Language. (2010). EdgeCoverQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/EdgeCoverQ.html