chapter  12
30 Pages

Matchings, Independence and Domination

Of the numerous problems concerning sets of edges or sets of vertices in graphs, many of these deal with the idea of independence (in which every two elements in the set are nonadjacent). Such a set of edges is a matching in a graph. The fact that two adjacent vertices u and v result in the edge uv gives rise to two other fundamental concepts in graph theory, namely covers and domination. These two concepts are also discussed in this chapter.