Domatic number: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Domatic number''' --- доматическое число. The '''domatic number''' <math>d(G)</math> (or <math>dom(G)</math>) of <math>G</math> is the maximum …») |
(нет различий)
|
Текущая версия от 17:03, 31 марта 2011
Domatic number --- доматическое число.
The domatic number [math]\displaystyle{ d(G) }[/math] (or [math]\displaystyle{ dom(G) }[/math]) of [math]\displaystyle{ G }[/math] is the maximum cardinality of a domatic partition of [math]\displaystyle{ G }[/math]. The domatic number is one of the numerous domination invariants. It was introduced by Cockayne and Hedetniemi in 1977. Clearly, any graph [math]\displaystyle{ G }[/math] satisfies [math]\displaystyle{ d(G) \leq \delta(G) + 1 }[/math] ([math]\displaystyle{ \delta(G) }[/math] is a minimal degree of [math]\displaystyle{ G }[/math]). Graphs for which [math]\displaystyle{ d(G) }[/math] achieves this upper bound [math]\displaystyle{ \delta(G) + 1 }[/math] are called domatically full.