Saturation (graph theory)

From Wikipedia, the free encyclopedia

Let G(V,E) be a graph and M a matching in G. A vertex v\in V(G) is said to be saturated by M if there is an edge in M incident to v. A vertex v\in V(G) with no such edge is said to be unsaturated by M. We also say that M saturates v.

[edit] See also


This article incorporates material from saturate on PlanetMath, which is licensed under the GFDL.