Saturation (graph theory)

Given a graph H, another graph G is H-saturated if G does not contain a (not necessarily induced) copy of H, but adding any edge to G it does. The function sat(n,H) is the minimum number of edges an H-saturated graph G on n vertices can have.[1]

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

## See also

* Hall's marriage theorem
* Bipartite matching

## References

1. ↑ For some results, see https://faculty.math.illinois.edu/~west/regs/saturate.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Saturation (graph theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Saturation_(graph_theory)&oldid=228001"