K-Binding number

Материал из WikiGrapp
Версия от 17:15, 22 февраля 2011; Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Binding number''' --- <math>k</math>-связывающее число. The '''<math>k</math>-binding number''' of <math>G</math> is defined to b…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ k }[/math]-Binding number --- [math]\displaystyle{ k }[/math]-связывающее число.

The [math]\displaystyle{ k }[/math]-binding number of [math]\displaystyle{ G }[/math] is defined to be

[math]\displaystyle{ bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} \left\{\frac{|\Gamma^{k-1}(X)|}{|X|}\right\}, }[/math]

where

[math]\displaystyle{ \delta^{k}(G) = \{X: \; \emptyset \neq X \subseteq V(G)\mbox{ and } \Gamma^{k}(X) \neq V(G)\}. }[/math]

Let [math]\displaystyle{ k \geq 2 }[/math]. The following two properties are obvious.

1. Let [math]\displaystyle{ G }[/math] be a graph with [math]\displaystyle{ n }[/math] vertices. If [math]\displaystyle{ diam(G) \leq k-1 }[/math], then [math]\displaystyle{ bind^{k}(G) = n-1 }[/math].

2. If a graph [math]\displaystyle{ G }[/math] has at least one isolated vertex, then [math]\displaystyle{ bind^{k}(G) = 0 }[/math].