Saturation (graph theory)

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Saturation" graph theory – news · newspapers · books · scholar · JSTOR (April 2024)

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

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

See also[edit]

• Hall's marriage theorem
• Bipartite matching

References[edit]

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e