K-Stability

[math]\displaystyle{ k }[/math]-Stability --- [math]\displaystyle{ k }[/math]-устойчивость.

A property [math]\displaystyle{ P }[/math] defined on all graphs of order [math]\displaystyle{ n }[/math] is said to be [math]\displaystyle{ k }[/math]-stable, if for any graph of order [math]\displaystyle{ n }[/math] that does not satisfy [math]\displaystyle{ P }[/math] the fact that [math]\displaystyle{ uv }[/math] is not an edge of [math]\displaystyle{ G }[/math] and that [math]\displaystyle{ G+uv }[/math] satisfies [math]\displaystyle{ P }[/math] implies [math]\displaystyle{ d_{G}(u) + d_{G}(v) \lt k }[/math]. Every property is [math]\displaystyle{ (2n-3) }[/math]-stable and every [math]\displaystyle{ k }[/math]-stable property is [math]\displaystyle{ (k+1) }[/math]-stable. We denote by [math]\displaystyle{ s(P) }[/math] the smallest integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ P }[/math] is [math]\displaystyle{ k }[/math]-stable and call it the stability of [math]\displaystyle{ P }[/math]. This number usually depends on [math]\displaystyle{ n }[/math] and is at most [math]\displaystyle{ 2n-3 }[/math].