Saturation (graph theory)

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

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

## 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=3382209"