- 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.
Introduced in 2010Updated in 2014