N-Расширяемый граф

[math]\displaystyle{ n }[/math]-Расширяемый граф ([math]\displaystyle{ n }[/math]-Extendable graph) - Пусть [math]\displaystyle{ G }[/math] --- конечный, связный, простой [math]\displaystyle{ p }[/math]-вершинный граф, [math]\displaystyle{ n }[/math] --- положительное целое число, удовлетворяющее условию [math]\displaystyle{ 1 \leq n \leq (p/2)-1 }[/math]. [math]\displaystyle{ G }[/math] называется [math]\displaystyle{ 0 }[/math]-расширяемым, если [math]\displaystyle{ G }[/math] имеет совершенное паросочетание. [math]\displaystyle{ G }[/math] называется [math]\displaystyle{ n }[/math]-расширяемым, если [math]\displaystyle{ G }[/math] имеет паросочетание размера [math]\displaystyle{ n }[/math] и каждое паросочетаниие размера [math]\displaystyle{ n }[/math] в [math]\displaystyle{ G }[/math] расширяется до совершенного паросочетания. Наибольшее целое [math]\displaystyle{ n }[/math], для которого граф является [math]\displaystyle{ n }[/math]-расширяемым, называется числом расширяемости и обозначается ext[math]\displaystyle{ (G) }[/math].

Литература

[Discrete Math.]