Independent Edge Set

An independent edge set (also called a matching) of a graph G is a subset of the edges such that no two edges in the subset share a vertex of G (Skiena 1990, p. 219). The counts of independent edge sets of size k in a graph are encoded through its matching-generating polynomial.

The number of independent edge sets in a graph is sometimes called the Hosoya index.

An independent edge set of maximum size is called a maximum independent edge set, and an independent edge set that cannot be expanded to another independent edge set by addition of any other edge in the graph is called a maximal independent edge set.

A maximum independent edge set can be computed in the Wolfram Language using FindIndependentEdgeSet[g].

The size of the largest independent edge set (i.e., of any maximum independent edge set) in a graph is known as its matching (or edge independence) number.

See also

Hosoya Index, Independent Set, Independent Vertex Set, Matching Number, Matching-Generating Polynomial, Maximal Independent Edge Set, Maximum Independent Edge Set

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Independent Edge Set." From MathWorld--A Wolfram Web Resource.

Subject classifications