Edge cover

An edge cover of a graph is a set of edges in which every vertex is incident to at least one selected edge. A minimum edge cover has the fewest edges among all edge covers.

Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Edge covers are defined using the vertices and edges of a graph.
Minimum edge cover: A minimum edge cover is an edge cover with the smallest possible number of edges. The central optimization problem is minimizing the number of selected edges.
Bipartite graph: A bipartite graph has vertices divided into two sets, with every edge joining vertices from different sets. Bipartite edge-cover problems can be solved through maximum bipartite matching.
Edge dominating set: An edge-dominating set is a set of edges adjacent to every edge outside the set. It targets all edges, whereas an edge cover targets all vertices.
Vertex: A vertex is a point in a graph that may be joined to other vertices by edges. An edge cover must include an edge incident to every vertex.
Maximum matching: A maximum matching is a matching containing as many edges as any matching in the graph. Starting from one, add an incident edge for each still-uncovered vertex to obtain a minimum edge cover.
Assignment problem: The assignment problem seeks a minimum-cost one-to-one allocation between two sets of items. Bipartite matching methods related to edge covers also underpin assignment optimization.
Dominating set: A dominating set is a set of vertices such that every vertex outside it has a neighbor in it. It covers vertices by neighborhood, not by direct incidence to selected edges.
Matching: A matching is a set of edges that share no endpoints. Maximum matchings determine the size and construction of minimum edge covers.
Matching number: The matching number of a graph is the size of its largest matching. For a graph without isolated vertices, the minimum edge-cover size equals the vertex count minus this number.

Linked from 1 page