G-Отображающая функция

Материал из WEGA
Версия от 12:19, 3 июня 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ \,G }[/math]-Отображающая функция ([math]\displaystyle{ \,G }[/math]-Matching function) — для фиксированного графа [math]\displaystyle{ \,G }[/math] и любого графа [math]\displaystyle{ \,H }[/math] функция [math]\displaystyle{ \,\gamma_{G}(H), }[/math] определяемая как наибольшее целое [math]\displaystyle{ \,k }[/math] такое, что [math]\displaystyle{ \,kG }[/math] изоморфен подграфу графа [math]\displaystyle{ \,H. }[/math] Заметим, что [math]\displaystyle{ \,\gamma_{K_{2}}(H) }[/math] есть реберное число независимости.

Литература

  • [J. Graph Theory]