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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

  • [Discrete Math.]