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]-расширяемым, называется числом расширяемости и обозначается [math]\displaystyle{ \,ext(G) }[/math].

Литература

• [Discrete Math.]