Число вершинного покриття
розмір найменшого вершинного покриття графа
Число вершинного покриття графа — розмір найменшого вершинного покриття в ньому.
Оскільки задача вершинного покриття є NP-повною, то невідомі алгоритми визначення числа вершинного покриття в довільному графі, що працюють за поліноміальний час.
У будь-якому графі число вершинного покриття пов'язане з числом незалежності першою тотожністю Галлаї: , більш того, доповнення до найменшого вершинного покриття є найбільшою незалежною множиною вершин.
У будь-якому графі також виконується нерівність , де — число парування графа . У двочастковому графі , внаслідок теореми Кеніга, . Тому в двочасткових графах задача визначення розв'язується за поліноміальний час.
Посилання
ред.- László Lovász, Michael D. Plummer[en]. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.