Saturación (teoría de grafos)

El siguiente teorema determina exactamente el número de saturación para grafos completos .

Teorema (Erdős, Hajnal y Moon, 1964). Para números enteros${\displaystyle n,r}$satisfactorio${\displaystyle 2\leq r\leq n}$,${\textstyle \operatorname {sat} (n,K_{r})=(r-2)(n-r+2)+{\binom {r-2}{2}}}$y la singularidad${\displaystyle K_{r}}$-gráfico saturado en${\displaystyle n}$vértices y${\displaystyle \operatorname {sat} (n,K_{r})}$los bordes son la unión del grafo de${\displaystyle K_{r-2}}$y el gráfico vacío${\displaystyle {\overline {K}}_{n-r+2}}$. ^{[ 2 ]}

De las definiciones se deduce que${\displaystyle \operatorname {sat} (n,H)\leq \operatorname {ex} (n,H)}$Sin embargo, en contraste con el número extremo, para un gráfico fijo${\displaystyle H}$, el número de saturación${\displaystyle \operatorname {sat} (n,H)}$siempre es como máximo lineal en${\displaystyle n}$.

Teorema (Kászonyi y Tuza, 1986). Para cualquier grafo fijo${\displaystyle H}$, si${\displaystyle H}$tiene un borde aislado, entonces${\displaystyle \operatorname {sat} (n,H)=c_{H}+o(1)}$por alguna constante${\displaystyle c_{H}}$y de otro modo,${\displaystyle \operatorname {sat} (n,H)=\Theta (n)}$. En particular,${\displaystyle \operatorname {sat} (n,H)=O(n)}$. ^{[ 4 ]}

Se conjetura que se cumple una forma más fuerte de estabilidad asintótica.

Conjetura (Tuza, 1986). Para cualquier grafo${\displaystyle H}$,${\textstyle \lim _{n\to \infty }{\frac {\operatorname {sat} (n,H)}{n}}}$existe. ^{[ 5 ] [ 6 ]}

Un estudio realizado por Currie, J. Faudree, R. Faudree y Schmitt describe el progreso en el problema de saturación de grafos y problemas relacionados. ^{[ 1 ]}