Definition
Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C. The set C is said to cover the vertices of G. The following figure shows examples of edge coverings in two graphs.
A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings.
Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching M in which each vertex is incident with exactly one edge in M. A perfect matching is always a minimum edge covering.
Read more about this topic: Edge Cover
Famous quotes containing the word definition:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)